ACM International Collegiate Programming Contest 1995
Northwestern European Regionals

Problem A

 Modern Art 

The famous painter Mel Borp is working on a brilliant series of paintings that introduce a new experimental style of Modern Art. At first glance, these paintings look deceptively simple, since they consist only of triangles of different sizes that seem to be stacked on top of each other. Painting these works, however, takes an astonishing amount of consideration, calculation, and precision since all triangles are painted without taking the brush off the canvas. How exactly Mel paints his works is a well-kept secret.

Recently, he started on the first painting of his new series. It was a single triangle, titled tex2html_wrap_inline176 . After that, he created tex2html_wrap_inline178 , the basis for his other works (see Figure 1).

Figure: Early work: tex2html_wrap_inline176 (left) and tex2html_wrap_inline178 (right).

Then he decided to take his experimenting one step further, and he painted tex2html_wrap_inline184 and tex2html_wrap_inline186 . Compare Figure 1 and Figure 2 to fully appreciate the remarkable progression in his work.

Figure: Advanced work: tex2html_wrap_inline184 (left) and tex2html_wrap_inline186 (right).

Note that the shape of the painting can be deduced from its title, tex2html_wrap_inline192 , as follows:

The triangles of a painting look all the same (each triangle is an isosceles triangle with two sides of the same length), but their height and width depend on the size of the canvas Mel used.

Mel wanted to end the series with tex2html_wrap_inline224 , the most complex painting he thought he would be able to paint. But no matter how many times he tried, he could not get it right. Now he is desperate, and he hopes you can help him by writing a program that prints, in order, the starting and ending coordinates of the lines Mel has to paint. Of course, you will need to know how Mel paints his works, so we will now reveal his secret technique.

As an example, take a look at tex2html_wrap_inline184 (see Figure 3):

Figure: tex2html_wrap_inline184 .

Mel always starts at the top of the top triangle, drawing a line straight to the lower-left corner of the lower left triangle (in this example, 1-2), continuing with a line to the lower-right corner of that triangle (in this example, 2-3). Next, he works his way up by drawing a line to the top of that triangle (in this example, 3-4). Now he has either reached the starting point again (finishing yet another masterpiece) or he has reached the lower-left corner of another triangle (in this example, 1-4-5). In the latter case, he continues by drawing the bottom line of that triangle (4-5) and after that he starts working on the triangle or triangles that is or are located underneath the lower-right corner of that triangle, in the same way. So he continues with (5-3), (3-6), (6-7), (7-8), (8-6), (6-9), and (9-1) as the finishing touch.

Input Specification

The first line of the input contains the number of test cases. Each test case consists of one line containing four non-negative integers p, q, x, and y, separated by spaces. tex2html_wrap_inline192 is the title of the painting and (x,y) are the coordinates of the top of the top triangle. Further, tex2html_wrap_inline242 and x,y < 32768. All triangles have a nonzero area.

Output Specification

For every test case, the output contains the pairs of (x,y) integer coordinates of the starting and ending points of all lines Mel has to draw for the painting tex2html_wrap_inline192 in the right order, in the format


followed by a newline. The output for each test case must be followed by an empty line.

Sample Input

0 0 1 1
1 2 512 1024

Sample Output