8277번 - Plotter 다국어

To test the functionality of his newly-purchased plotter, Byteasar decided to plot a few bytecurves. A bytecurve of order n consists of 2ⁿ segments of length √2 each. The first of them connects the points with coordinates (0, 0) and (1, 1). A bytecurve of order n can be described with a word L_n of length 2ⁿ - 1 based on a two-letter alphabet {L, R}. The word's i-th letter indicates that, after i-th segment has been printed, the pen turns and moves orthogonally to the left (letter L) or to the right (letter R) to print the next segment. In other words, the pen changes its direction to the left or to the right by 90°.

L₁ consists of a single letter L (left turn) and L₂ consists of three letters LLR, indicating two left turns followed by one right turn. Inductively, L_n is generated from L_n-1 in the following way: separate all letters in L_n-1 with spaces and place an additional space in front and at the end of L_n-1. Then, in the newly-created spaces, place alternating letters L and R, beginning with L. For example, L₃ is generated as follows: L₂ = LLR → L L R → LLRLLRR = L₃. Similarly, L₄ = LLRLLRRLLLRRLRR (see the figure below).

It takes exactly one second to draw one segment of the bytecurve. While waiting for the plotter to complete printing, Byteasar ponders the following question: given a point (x, y) on the plane, when will the pen be positioned at that point? For example, for the bytecurve of order 4 in the above figure, the pen will be at point (-3, -1) seven seconds after the beginning of plotting, and again eleven seconds after the beginning of plotting. Your task is to answer Byteasar's question.

The first line of the input contains two integers, n and m (1 ≤ n, m ≤ 2000), where n indicates that the bytecurve is described by L_n and m indicates that there are m query points. The next m lines each contain two integers, x_i and y_i (-10⁹ ≤ x_i, y_i ≤ 10⁹), indicating the coordinates of the i-th query point. Note that the coordinates in any particular input line are not guaranteed to represent a point on the bytecurve. Moreover, no point appears more than once in the input file.

The output consists of m lines containing answers to the consecutive queries. Each answer consists of a nonnegative integer k_i, specifying the number of visits the pen makes to the query point (x_i, y_i); followed by k_i nonnegative integers indicating the times of those visits in increasing order, in seconds since the beginning of plotting. Numbers should be separated by single spaces, and there should be no spaces at the beginning or end of a line.

If you found this task amusing, try its harder version, Trails, also from PA 2011.