The latest fashion among the residents of Byteotia is a rather original game called Hilbert billiards.
The table for this game has dimensions $2^{n+1} \times 2^{n+1}$, and the number $n$ is called the size of the table. Barriers forming a Hilbert curve of order $n$ are placed on the table. The figure below shows the tables for $n = 1, 2, 3$.
The bottom-left corner of the table has coordinates $(0, 0)$, the bottom-right has coordinates $(2^{n+1}, 0)$, and the top-right has coordinates $(2^{n+1}, 2^{n+1})$. The Hilbert curve of order 1 forming the barriers of a table of size 1 is shown in the left figure. A Hilbert curve forming the barriers of a table of size $n$ (for $n \ge 2$) consists of four curves of order $n-1$ placed in the four quadrants of the table, plus three additional connecting barriers of length 2 (see the figure). The curve in the bottom-left corner is rotated $90^\circ$ clockwise, while the curve in the bottom-right corner is rotated $90^\circ$ counter-clockwise.
A ball starts from the point with coordinates $(1, 0)$ with an initial velocity vector $(1, 1)$. During its movement, it bounces perfectly elastically off the barriers forming the Hilbert curve and the sides of the table. For simplicity, we assume that the ball has negligible size. You must determine the coordinates of the point where the ball will be after $t$ units of time. The figure shows the beginning of the ball's path in red for a table of size $n = 3$; for example, after $t = 42$ units of time, the ball will be at the point with coordinates $(3, 14)$.
Input
The first line of input contains two integers $n$ and $z$ ($1 \le n \le 30$, $1 \le z \le 100\,000$), representing the size of the table and the number of queries, respectively.
The next $z$ lines contain the queries in increasing order: the $i$-th of these lines contains an integer $t_i$, representing the number of time units for the $i$-th query ($0 < t_1 < t_2 < \dots < t_z < 2^{2(n+1)}$).
Output
Output exactly $z$ lines, which are the answers to the successive queries from the input: the $i$-th line should contain two integers separated by a single space, representing the coordinates of the point where the ball will be after $t_i$ units of time.
Examples
Input 1
3 2 1 42
Output 1
2 1 3 14