配点 : $100$ 点

問題

整数 $N$ が与えられます。下図のような、無限に伸びる完全 $N$ 分木を考えます。

図: $N = 3$ の場合の無限に伸びる完全 $N$ 分木

図で示されているように、各頂点には重複しない正の整数の番号が付いており、どの正の整数に対してもそれを頂点番号として持つ頂点が存在します。木の根の頂点番号は $1$ です。その他の頂点には、上の段にある頂点ほど小さな番号が付けられています。同じ段にある頂点には、左に位置するほど小さな番号が付けられています。

この木に関して、以下の形式の $Q$ 個の問いに答えてください。$i$ 番目の問い $(1 \leq i \leq Q)$ は次の通りです。

• 頂点 $v_i$ と $w_i$ の最近共通祖先（注釈を参照）の頂点番号を求めよ。

注釈

• 根付き木において、頂点 $v$ と $w$ の 最近共通祖先 とは、頂点 $v$ と $w$ のいずれの祖先でもある頂点のうち、最も根から遠いもののことです。ここで、頂点の祖先にはその頂点自身も含まれるものとします。例えば、問題文中で図示された木において、頂点 $5$ と $7$ の最近共通祖先は頂点 $2$、頂点 $8$ と $11$ の最近共通祖先は頂点 $1$、頂点 $3$ と $9$ の最近共通祖先は頂点 $3$ です。

制約

• $1 \leq N \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq v_i < w_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$v_1$ $w_1$

$:$

$v_Q$ $w_Q$

出力

$Q$ 行出力せよ。$i$ 行目 $(1 \leq i \leq Q)$ に頂点 $v_i$ と $w_i$ の最近共通祖先の頂点番号を出力すること。

3 3
5 7
8 11
3 9

2
1
3

このケースでの問いは、注釈セクションで示した例に対応します。

100000 2
1 2
3 4

1
1