Problem Description

Given an integer $ N $, consider an infinitely growing perfect $ N $-ary tree as shown in the figure below.

As illustrated, each vertex is labeled with a unique positive integer, and for any positive integer, there exists a vertex with that number as its vertex label. The root of the tree is labeled with $ 1 $. Other vertices are labeled with smaller numbers the higher they are in the tree. Within the same level, vertices are labeled with smaller numbers the further left they are.

For this tree, answer $ Q $ queries of the following form: For the $ i $-th query $(1 \leq i \leq Q)$, determine the lowest common ancestor (see notes) of vertices $ v_i $ and $ w_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ v_1 $ $ w_1 $ $ : $ $ v_Q $ $ w_Q $

Output Format

Output $ Q $ lines. The $ i $-th line $(1 \leq i \leq Q)$ should contain the vertex number of the lowest common ancestor of vertices $ v_i $ and $ w_i $.

Sample Input and Output

Sample Input #1

3 3
5 7
8 11
3 9

Sample Output #1

2
1
3

Sample Input #2

100000 2
1 2
3 4

Sample Output #2

1
1

Notes/Hints

Notes

• In a rooted tree, the lowest common ancestor of vertices $ v $ and $ w $ is the vertex furthest from the root that is an ancestor of both $ v $ and $ w $. Here, a vertex is considered an ancestor of itself. For example, in the tree illustrated in the problem, the lowest common ancestor of vertices $ 5 $ and $ 7 $ is vertex $ 2 $, the lowest common ancestor of vertices $ 8 $ and $ 11 $ is vertex $ 1 $, and the lowest common ancestor of vertices $ 3 $ and $ 9 $ is vertex $ 3 $.

Constraints

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

Sample Explanation 1

The queries in this case correspond to the examples provided in the notes section.

见题面 Input 部分

见题面 Output 部分