Ball Trajectory on a Hilbert Curve

Consider an integer (n) (with (n\ge1)) that defines a Hilbert curve and a square of size (2^{n+1}\times2^{n+1}) with its bottom–left corner at ((0,0)) and its top–right corner at ((2^{n+1},2^{n+1})). The Hilbert curve is drawn inside the square by taking the standard Hilbert curve of order (n) (which is defined on a (2^n\times2^n) grid) and mapping every grid–point ((x,y)) to ((2x+1,2y+1)). In other words, the (n)th–order curve consists of (2^{2n}) points and its consecutive points are connected by line segments. In addition, the boundary of the square forms four extra segments. A ball (modeled as a point) starts at ((1,0)) with an initial velocity (\boldsymbol{v}=(1,1)). Whenever the ball collides with either one of the boundary segments or any segment of the Hilbert curve, it bounces off following a perfectly elastic collision – that is, the component of its velocity perpendicular to the obstacle is reversed while the parallel component remains unchanged. It is guaranteed that the ball never collides exactly at a corner (so that at every collision the ball hits a face).

You are given (m) queries. For each query, compute the position of the ball after (t_i) seconds.

All formulas are given in (\LaTeX) format.

inputFormat

The first line contains two integers (n) and (m), where (n) (with (n\ge1)) is the order of the Hilbert curve and (m) is the number of queries. Each of the following (m) lines contains an integer (t_i) representing the time in seconds.

outputFormat

For each query, output two integers representing the coordinates (in units) of the ball after (t_i) seconds.

sample

1 3
1
2
3

2 1
3 2
2 3