26216번 - 은나무

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

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$)이 주어진다. 이 때, 트리에 존재하는 키의 개수는 $10^{18}$을 넘지 않는다.

다음 $Q$개의 줄에 걸쳐 각 줄에 쿼리가 두 정수 $A$, $B$ ($1 \leq A \leq B \leq 10^{18}$)의 형태로 주어진다.

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