The famous painter Mel Borp is working on a brilliant series of paintings that introduce a new experi- mental 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 T0,0. After that, he created T1,1, the basis for his other works (see Figure 1). Figure 1. Early work: T0,0 (left) and T1,1 (right). Then he decided to take his experimenting one step further, and he painted T1,2 and T3,2. Compare Figure 1 and Figure 2 to fully appreciate the remarkable progression in his work. Figure 2. Advanced work: T1,2 (left) and T3,2 (right). Note that the shape of the painting can be deduced from its title, Tp,q, as follows: • T0,0 is a single triangle (see Figure 1); • T1,1 consists of a smaller, inverted triangle placed inside T0,0 , so that the result consists of four smaller triangles (see Figure 1); • if p > 0 and q > 1, then the painting looks like Tp,q−1, except that an inverted triangle has been placed inside the bottom-right triangle of Tp,q−1, splitting it into four smaller triangles (compare for example T1,1 and T1,2 );
2/3 • if p > 1 and q > 0, the painting looks like Tp−1,q , except that an inverted triangle has been placed inside the bottom-left triangle of Tp−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 T10,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 T1,2 (see Figure 3): 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 Figure 3. T1,2. 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. Tp,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 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 Tp,q in the right order, in the format (startX,startY )(endX,endY ) followed by a newline. The output for each test case must be followed by an empty line. Sample Input 2 0011 1 2 512 1024 Sample Output (1,1)(0,0) (0,0)(2,0)
3/3 (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)