시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

To test the functionality of his newly-purchased plotter, Byteasar decided to plot a few bytecurves. A bytecurve of order n consists of 2n 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 Ln of length 2n - 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°.

L1 consists of a single letter L (left turn) and L2 consists of three letters LLR, indicating two left turns followed by one right turn. Inductively, Ln is generated from Ln-1 in the following way: separate all letters in Ln-1 with spaces and place an additional space in front and at the end of Ln-1. Then, in the newly-created spaces, place alternating letters L and R, beginning with L. For example, L3 is generated as follows: L2 = LLR →  L L R LLRLLRR = L3. Similarly, L4 = 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 Ln and m indicates that there are m query points. The next m lines each contain two integers, xi and yi (-109xi, yi ≤ 109), 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 ki, specifying the number of visits the pen makes to the query point (xi, yi); followed by ki 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.

예제 입력 1

4 3
-3 -1
1 1
-1 0

예제 출력 1

2 7 11
1 1
0

노트

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