/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題
整数 N が与えられます。下図のような、無限に伸びる完全 N 分木を考えます。
図: N = 3 の場合の無限に伸びる完全 N 分木
図で示されているように、各頂点には重複しない正の整数の番号が付いており、どの正の整数に対してもそれを頂点番号として持つ頂点が存在します。木の根の頂点番号は 1 です。その他の頂点には、上の段にある頂点ほど小さな番号が付けられています。同じ段にある頂点には、左に位置するほど小さな番号が付けられています。
この木に関して、以下の形式の Q 個の問いに答えてください。i 番目の問い (1 ≤ i ≤ Q) は次の通りです。
- 頂点 v_i と w_i の最近共通祖先（注釈を参照）の頂点番号を求めよ。
注釈
- 根付き木において、頂点 v と w の 最近共通祖先 とは、頂点 v と w のいずれの祖先でもある頂点のうち、最も根から遠いもののことです。ここで、頂点の祖先にはその頂点自身も含まれるものとします。例えば、問題文中で図示された木において、頂点 5 と 7 の最近共通祖先は頂点 2、頂点 8 と 11 の最近共通祖先は頂点 1、頂点 3 と 9 の最近共通祖先は頂点 3 です。
制約
- 1 ≤ N ≤ 10^9
- 1 ≤ Q ≤ 10^5
- 1 ≤ v_i < w_i ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N Q v_1 w_1 : v_Q w_Q
出力
Q 行出力せよ。i 行目 (1 ≤ i ≤ Q) に頂点 v_i と w_i の最近共通祖先の頂点番号を出力すること。
入力例 1
3 3 5 7 8 11 3 9
出力例 1
2 1 3
このケースでの問いは、注釈セクションで示した例に対応します。
入力例 2
100000 2 1 2 3 4
出力例 2
1 1
Score : 100 points
Problem Statement
You are given an integer N. Consider an infinite N-ary tree as shown below:
Figure: an infinite N-ary tree for the case N = 3
As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.
Regarding this tree, process Q queries. The i-th query is as follows:
- Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.
Notes
- In a rooted tree, the lowest common ancestor (LCA) of Vertex v and w is the farthest vertex from the root that is an ancestor of both Vertex v and w. Here, a vertex is considered to be an ancestor of itself. For example, in the tree shown in Problem Statement, the LCA of Vertex 5 and 7 is Vertex 2, the LCA of Vertex 8 and 11 is Vertex 1, and the LCA of Vertex 3 and 9 is Vertex 3.
Constraints
- 1 ≤ N ≤ 10^9
- 1 ≤ Q ≤ 10^5
- 1 ≤ v_i < w_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N Q v_1 w_1 : v_Q w_Q
Output
Print Q lines. The i-th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i.
Sample Input 1
3 3 5 7 8 11 3 9
Sample Output 1
2 1 3
The queries in this case correspond to the examples shown in Notes.
Sample Input 2
100000 2 1 2 3 4
Sample Output 2
1 1