Memory limit: 32 MB
To test the functionality of his newly-purchased plotter, Byteasar decided to plot a few bytecurves. A bytecurve of order consists of segments of length each. The first of them connects the points with coordinates and . A bytecurve of order can be described with a word of length based on a two-letter alphabet . The word's -th letter indicates that, after -th segment has been printed, the pen turns and moves orthogonally to the left (letter ) or to the right (letter ) to print the next segment. In other words, the pen changes its direction to the left or to the right by .
consists of a single letter (left turn) and consists of three letters , indicating two left turns followed by one right turn. Inductively, is generated from in the following way: separate all letters in with spaces and place an additional space in front and at the end of . Then, in the newly-created spaces, place alternating letters and , beginning with . For example, is generated as follows: Similarly, (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 on the plane, when will the pen be positioned at that point? For example, for the bytecurve of order in the above figure, the pen will be at point 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, and (), where indicates that the bytecurve is described by and indicates that there are query points. The next lines each contain two integers, and (), indicating the coordinates of the -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 lines containing answers to the consecutive queries. Each answer consists of a nonnegative integer , specifying the number of visits the pen makes to the query point ; followed by 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.
For the input data:
4 3 -3 -1 1 1 -1 0
the correct result is:
2 7 11 1 1 0
Task author: Tomasz Idziaszek.
If you found this task amusing, try its harder version, Trails, also from PA 2011.<Submit a solution> [0/10]