Problem A

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

Figure 1: Early work: T_0,0 (left) and T_1,1 (right).

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

Figure 2: Advanced work: T_1,2 (left) and T_3,2 (right).

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

• T_0,0 is a single triangle (see Figure 1);
• T_1,1 consists of a smaller, inverted triangle placed inside T_0,0, so that the result consists of four smaller triangles (see Figure 1);
• if p > 0 and q > 1, then the painting looks like T_p,q-1, except that an inverted triangle has been placed inside the bottom-right triangle of T_p,q-1, splitting it into four smaller triangles (compare for example T_1,1 and T_1,2);
• if p > 1 and q > 0, the painting looks like T_p-1,q, except that an inverted triangle has been placed inside the bottom-left triangle of T_p-1,q, splitting it into four smaller triangles;
• other values of p and q: it is not a valid title of a painting.

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 T_10,10, 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 T_1,2 (see Figure 3):

Figure 3: T_1,2.

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. T_p,q is the title of the painting and (x,y) are the coordinates of the top of the top triangle. Further, p,q <= 10 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 T_p,q in the right order, in the format

(startX, startY)(endX, endY)

Example Input

2
0 0 1 1
1 2 512 1024

Example Output

(1,1)(0,0)
(0,0)(2,0)
(2,0)(1,1)

(512,1024)(0,0)
(0,0)(512,0)
(512,0)(256,512)
(256,512)(768,512)
(768,512)(512,0)
(512,0)(768,0)
(768,0)(640,256)
(640,256)(896,256)
(896,256)(768,0)
(768,0)(1024,0)
(1024,0)(512,1024)