은나무

겨울 숲에 있는 은나무는 루트가 정해진 트리이며, 다음 성질에 따라 유일하게 정해진다.

1. 모든 노드는 흰색 또는 파란색이고, 루트 노드는 흰색이다.
2. 모든 흰색 노드는 파란색 자식 $K$개와 흰색 자식 $0$개 또는 $K+1$개를 가진다.
3. 흰색 자식이 없는 모든 흰색 노드의 깊이는 $H$로 같다. 흰색 노드의 깊이는 루트에서 해당 노드까지의 경로에 있는 흰색 노드의 개수이다.
4. 모든 파란색 노드는 자식이 없고, 서로 다른 양의 정수인 키(key)를 가진다. 은나무의 파란색 노드 개수가 $M$개라면, 파란색 노드들의 키 값은 $1$부터 $M$까지이다.
5. 모든 흰색 노드의 파란색 자식 노드들이 가지는 키는 오름차순이다. 흰색 자식이 있을 경우, 자식들을 흰색-파란색-흰색-파란색-$\cdots$-흰색 순서로 번갈아 놓았을 때 흰색 자식의 서브트리에 있는 키들과 파란색 자식의 키들이 오름차순이 된다.

구체적으로, 흰색 자식들을 순서대로 $c_0, c_1, \cdots, c_K$라 하고, 파란색 자식이 가진 키 값을 순서대로 $x_1 < x_2 < \cdots < x_K$라 하자. $c_i$를 루트로 하는 서브트리에 있는 모든 키는 $x_i$보다 크고 $x_{i+1}$보다 작다. $y_i$를 흰색 자식 $c_i$를 루트로 하는 서브트리에 있는 임의의 키라고 하면 $y_0 < x_1 < y_1 < x_2 < \cdots < x_K < y_K$가 성립한다.

위의 그림은 $K = 2$, $H = 3$일 때 만들어지는 은나무이다.

두 키의 쌍이 주어졌을 때, 각 키를 담고 있는 두 파란색 노드를 연결하는 경로의 길이는 얼마인가?

첫 줄에 정수 $K$ ($1 \leq K \leq 50$), $H$ ($1 \leq H \leq 50$), $Q$ ($1 \leq Q \leq 200,000$)이 주어진다. $K$는 흰색 노드 하나가 갖는 파란색 자식의 개수, $H$는 은나무의 높이, $Q$는 쿼리의 개수이다. 이 때, 트리에 존재하는 키의 개수는 $10^{18}$을 넘지 않는다.

다음 $Q$개의 줄에 각 줄마다 두 정수 $A$, $B$ ($1 \leq A \leq B \leq 10^{18}$)가 주어진다.

각각의 쿼리에 대해, 두 정수를 담고 있는 두 파란색 노드를 연결하는 경로의 길이를 출력한다. 해당하는 파란색 노드가 은나무 내에 존재하지 않으면 $-1$을 출력한다.