시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1235 251 186 23.574%

문제

각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.

트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.

아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.

노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다.

다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

출력

총 Q개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.

예제 입력 1

7 2 3
1 2
2 1
4 7

예제 출력 1

1
1
4

예제 입력 2

9 3 3
8 9
5 7
8 4

예제 출력 2

2
2
3
W3sicHJvYmxlbV9pZCI6IjExODEyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiS1x1YzljNCBcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMwMSBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjNzkwXHVjMmRkXHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBLXHVhYzFjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBLXHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IEtcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHViMjk0ICZxdW90O1x1YzgwMVx1Yzc0MCBcdWM1ZDBcdWIxMDhcdWM5YzAmcXVvdDsgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTBcdWIyZTQuICZxdW90O1x1YzgwMVx1Yzc0MCBcdWM1ZDBcdWIxMDhcdWM5YzAmcXVvdDsgXHViYzI5XHViYzk1XHVjNzc0XHViNzgwLCBcdWM3NzRcdWM4MDQgXHVhZTRhXHVjNzc0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWNjNDRcdWM2YjQgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZTRhXHVjNzc0XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1Yzc3NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZTRhXHVjNzc0XHVjNzU4IFx1YjE3OFx1YjRkY1x1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWNkOTRcdWFjMDAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YjE3OFx1YjRkYyA5XHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgM1x1YzljNCBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMTgxMlwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjRweDsgd2lkdGg6MTg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMTc4XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YjE3OFx1YjRkYyB4XHVjNjQwJm5ic3A7eSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOICgxICZsZTsmbmJzcDtOICZsZTsgMTA8c3VwPjE1PFwvc3VwPilcdWFjZmMgSyAoMSAmbGU7IEsgJmxlOyAxIDAwMCksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxNzhcdWI0ZGMgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOCBRICgxICZsZTsgUSAmbGU7IDEwMCAwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWIxNzhcdWI0ZGMgeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB4LCB5ICZsZTsgTiwgeCAmbmU7IHkpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjQ1MCBcdWIxNzhcdWI0ZGMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE4MTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDSEVXQkFDQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSB0cmVlIG9mIG9yZGVyIEsgd2l0aCBOIG5vZGVzIG9yLCBpbiBvdGhlciB3b3JkcywgZWFjaCBub2RlIGNhbiBoYXZlIGF0IG1vc3QgSyBjaGlsZHJlbi4gVGhlIHRyZWUgaXMgY29uc3RydWN0ZWQgc28gaXQmcnNxdW87cyBvZiB0aGUgJnF1b3Q7bG93ZXN0IGVuZXJneSZxdW90OzogdGhlIG5vZGVzIGFyZSBwbGFjZWQgaW4gYSBuZXcgZGVwdGggb2YgdGhlIHRyZWUgb25seSB3aGVuIGFsbCB0aGUgcGxhY2VzIChmcm9tIGxlZnQgdG8gcmlnaHQpIGluIHRoZSBwcmV2aW91cyBkZXB0aCBoYXZlIGJlZW4gZmlsbGVkLiBUaGlzIGlzIGFsc28gdGhlIG9yZGVyIG9mIGVudW1lcmF0aW5nIHRoZSBub2Rlcywgc3RhcnRpbmcgd2l0aCAxLiBJbWFnZSBkZXBpY3RzIGFuIGV4YW1wbGUgb2YgYSB0cmVlIG9mIG9yZGVyIDMgd2l0aCA5IG5vZGVzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMTgxMlwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjRweDsgd2lkdGg6MTg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IG5lZWQgdG8gb3V0cHV0IGFuc3dlcnMgdG8gUSBxdWVyaWVzIGluIHRoZSBmb3JtIG9mIHggeSwgd2hlcmUgdGhlIGFuc3dlciBpcyB0aGUgbWluaW1hbCBudW1iZXIgb2Ygc3RlcHMgbmVlZGVkIHRvIGdldCBmcm9tIG5vZGUgeCB0byBub2RlIHkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlcnMgTiAoMSAmbGU7Jm5ic3A7TiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pLCBLICgxICZsZTsgSyAmbGU7IDEgMDAwKSBpIFEgKDEgJmxlOyBRICZsZTsgMTAwIDAwMCkgZnJvbSB0aGUgdGFzay4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIFEgbGluZXMgY29udGFpbnMgcGFpcnMgeHkgKDEgJmxlOyB4LCB5ICZsZTsgTiwgeCAmbmU7IHkpIGZyb20gdGhlIHRhc2suPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IFEgbGluZXMsIGVhY2ggbGluZSBjb250YWluaW5nIHRoZSBhbnN3ZXIgdG8gYSBxdWVyeSBmcm9tIHRoZSB0YXNrLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBleGFtcGxlOiBZb3UgYXJlIGdpdmVuIGEgY29tcGxldGUgYmluYXJ5IHRyZWUuIE5vZGUgMiBpcyBhIGRpcmVjdCBjaGlsZCBvZiBub2RlIDEgc28gdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlbSBpcyBleGFjdGx5IDEuIE5vZGVzIDQgYW5kIDcgYXJlIG9uIGNvbXBsZXRlIG9wcG9zaXRlIHNpZGVzIG9mIHRoZSB0cmVlLCBzbyB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGVtIGlzIDQ6IDQgJnJhcnI7IDIgJnJhcnI7IDEgJnJhcnI7IDMgJnJhcnI7IDcuPFwvcD5cclxuXHJcbjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIHNlY29uZCBleGFtcGxlOiBUaGlzIGV4YW1wbGUgY29ycmVzcG9uZHMgdG8gdGhlIGltYWdlLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d