[Problem B | 1995 Western Europe problem set | Ed's programming contest problem archive | my home page]

Western European Regional

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.

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.

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

(followed by a newline. The output for each test case must be followed by an empty line.startX,startY)(endX,endY)

2 0 0 1 1 1 2 512 1024

(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)

This page maintained by Ed Karrels.

Last updated January 3, 1998