Suppose that you are organizing a tournament with \(n = 2^k\) players. On the first round, the first player will play against the second player, the third player against the forth, the fifth against the sixth and so on.

On the second round, this process is repeated again with the winners of the first round. So that the winner of the first match plays against the winner of the second match and so on.

This process is repeated \(k\) times until only one person is left. The following figure illustrates one possible outcome of this process with \(n = 8 = 2^3\).

The bottom level of the tree shows the first round pairings. The subsequent levels corresponds to the other rounds of the tournament. The root shows the winner.

Given the number of a player \(1 \leq p \leq n\) and a round \(1 \leq r \leq k\), what is the set of possible adversaries of player \(p\) on round \(r\)?

Examples:

1. If \(p = 3\) and \(r = 1\) then the set of possible oponents is \(\{4\}\).
2. If \(p = 7\) and \(r = 2\) then the set of possible oponents is \(\{5, 6\}\).
3. If \(p = 2\) and \(r = 3\) then the set of possible oponents is \(\{5, 6, 7, 8\}\).

Note: The set of possible opponents is always a continuous range so it is totally identified by its minimum and maximum elements. In the above examples the ranges are \([4, 4]\), \([5, 6]\) and \([5, 8]\).

Input

• A line with an integer \(n\) giving the number of players.
• A line with an integer \(q\) giving the number of queries.
• \(q\) lines each with two integers \(p_i\) and \(r_i\) giving a player and a round, respectively.

Output

• \(q\) lines, one for each for each query \(p_i, r_i\) with two integers \(a_i\) and \(b_i\) giving the range of possible opponents of player \(p_i\) at round \(r_i\) is \([a_i, b_i]\).

Limits

• \(2 \leq n \leq 2^{18}\)
• \(1 \leq q \leq 10^5\)
• \(1 \leq r_i \leq k\) where \(n = 2^k\)
• \(1 \leq p_i \leq n\)

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2