Problem D. Hand copy

Problem

Although Stephen is working in an IT company, sometimes he needs to do some boring and time consuming jobs. Today, he needs to copy some circuit design from another company. However, due to the policy of that company, bringing soft-copy outside is not allowed. Therefore, he needs to copy the circuit design by hand.

Each circuit can be formulated into a list of rectangle. Each rectangle is denoted by two points - lower left and upper right coordinates. So, all Stephen needs to do is to copy the coordinates by hand. But you know, copying a list of coordinates by hand is super time consuming. Therefore, he is suggested to parse the coordinates to "writable form" using the following method before hand copy.

1. instead of copying lower left (x1,y1) and upper right coordinates (x2,y2), he is suggested to copy the lower left coordinates and the width and height of the rectangle, i.e.,(x,y,w,h)

2. He discovered that most of the rectangles' x / y / w / h in circuit design are the same. So if we write each rectangle in a line and sort the list of 4 numbers in some order, then you will discover that many numbers in line i is the same as the corresponding number in line i-1. In this case, he will not copy the exactly number, he will copy a symbol "*" only.

Here is an example, Original
x1y1x2y2
0070200
70130170200
170130240330


After step 1,
xywh
0070200
7013010070
17013070200


After step 2 with sorting order w then h then y then x,
xywh
0070200
170130**
70*10070


Then, Stephen will copy these parsed numbers instead of the original ones. You know, hand copy is very slow. So, Stephen wants to find a best sorting order in order to minimize the number of digits to copy. In the above case, he doesn't need to copy 3 + 2 + 3 = 8 digits. If two sorting orders are tie, he favors x then y then w then h. That means if both x > w > y > h and x > y > h > w can gives optimal solution, then he will choose x > y > h > w.

Input

The input file consists of several cases. Each case starts with a number n which is the number of rectangles in the circuit. It is followed by n lines. Each line has 4 numbers: x, y, w, h respectively. Process until the end of file.

Output

Output the parsed form of each test case. Print a new line after each test case.

Sample input

3
0 0 70 200
70 130 170 200
170 130 70 200
3
0 20 1 21
20 20 30 30
20 0 25 5

Sample output

0 0 70 200
170 130 * *
70 * 170 *
0 20 1 21
20 0 25 5
* 20 30 30
Remarks:
1. 0 is one digit.
2. This is a real problem Stephen has to face in Taiwan. =.="