Plotter

To test his newly bought plotter, Byteasar decides to draw a few bytecurves.

A bytecurve of order $n$ consists of $2^n$ segments, each of length $\sqrt{2}$. The very first segment joins the points $(0, 0)$ and $(1, 1)$. The bytecurve of order $n$ is described by a word $L_n$ of length $2^n - 1$ over the two-letter alphabet $\{L, R\}$. The $i$-th letter tells the pen, right after the $i$-th segment has been drawn, to turn by $90°$ and continue at a right angle either to the left (letter $L$) or to the right (letter $R$) before drawing the next segment.

$L_1$ is the single letter $L$ (one left turn), and $L_2 = LLR$ (two left turns followed by one right turn). In general, $L_n$ is built from $L_{n-1}$ like this: write the letters of $L_{n-1}$ separated by single spaces and add one extra space before the first letter and one after the last, then fill the newly created gaps from left to right with the alternating letters $L, R, L, R, \dots$ starting with $L$. For example,

$L_2 = LLR \;\longrightarrow\; \_\,L\,\_\,L\,\_\,R\,\_ \;\longrightarrow\; LLRLLRR = L_3,$

and in the same way $L_4 = LLRLLRRLLLRRLRR$ (drawn in the figure below).

Drawing one segment takes exactly one second, and the pen starts at $(0, 0)$ at time $0$. While the plotter works, Byteasar wonders: for a given point $(x, y)$, at which moments is the pen located there? For example, on the order-$4$ bytecurve above the pen is at $(-3, -1)$ after $7$ seconds and again after $11$ seconds. Answer Byteasar's question.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$): the curve is $L_n$ and there are $m$ query points. Each of the next $m$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), the coordinates of the $i$-th query point. A query point need not lie on the curve, and no point appears twice in the input.

Print $m$ lines, one per query in order. For the $i$-th query print a nonnegative integer $k_i$, the number of times the pen is at $(x_i, y_i)$ while the order-$n$ curve is drawn (the starting position at time $0$ counts as a visit), followed by those $k_i$ visit times in increasing order, in seconds since drawing began. Separate all numbers on a line by single spaces, with no leading or trailing space.

If you enjoyed this problem, try the harder variant that asks the same question under tighter limits.