Choosing a camera

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Mr. Strange is choosing a compact digital photo camera. He looks at various shops offers and sometimes makes temporary choices. At each temporary choice, he knows about all offers he already saw, but doesn’t know about those he will see in the future.
According to Mr. Strange, any digital camera is fully described by two properties: the number of pixels and the optical zoom ratio. For each property, he thinks that the more is the better. Mr. Strange is afraid to buy an outdated camera, so he never chooses a camera, if he knows about another camera, which is strictly better by any one property and not worse by another. Among all cameras Mr. Strange does not consider outdated, he chooses the cheapest one; if there are different non-outdated cameras with equal minimal cost, he chooses among them the oldest offer.

Input

The first line of input contains the number of the test cases. The first line of each test case contains total number n (1 ≤ n ≤ 105) of actions. Each action can be either a new camera offer or a temporary choice. Each offer is denoted by big letter P, then camera’s number of pixels, zoom ratio and cost. Each temporary choice is denoted by big letter С. Each action is denoted in separate line, data inside lines are separated by single spaces. Numbers of pixels are integers in the range 103 ≤ pi ≤ 109. Zoom ration is a floating-point number in the range 1 ≤ zi ≤ 100, with no more than 6 digits after decimal point. Costs are integers in the range 1 ≤ ci ≤ 106. Size of the input is less than 16 Mb.

Output

For each temporary choice action, your program should output the number of the action when the currently chosen camera was offered. If no choice can be done according to the rules, the query result should be –1. All results inside each test case should be written in the same line and separated by single spaces. Results for consecutive test cases should be in consecutive lines.

Sample Input

2
1
P 9600000 7 72
7
P 1200000 1 40
P 7200000 5 100
C
P 9600000 3 200
C
P 7200000 12 220
C

Sample Output

2 2 4

Submit

Source: South Eastern European Regional Contest 2011