Choosing a Camera#2566
Mr. Oddball is choosing a digital camera. He studies store offers and occasionally makes a tentative selection. At each tentative selection, he knows all the offers he has seen so far, but does not know about any future offers.
In Mr. Oddball's view, any digital camera can be fully described by two properties: the number of pixels and the optical zoom factor. For each of these properties, the more, the better. Mr. Oddball is afraid to buy an outdated camera; therefore, he will never choose a camera if he knows of another camera that is strictly better in one property and no worse in the other. Among all cameras that Mr. Oddball does not consider outdated, he picks the cheapest one. If there are several non-outdated cameras with the same minimal price, he chooses the earliest offer among them.
The first line of input contains the number of test cases. The first line of each test case contains the total number of operations (1 \leq n \leq 10^5). Each operation is either a new camera offer or a tentative selection. Each offer is indicated by the capital letter "P", then the number of pixels, the zoom factor, and the cost. Each tentative selection is indicated by the capital letter "C". Each operation is given on a separate line, and data within a line is separated by single spaces.
The number of pixels is an integer in the range 10^3 \leq p_i \leq 10^9. The zoom factors are fractional numbers in the range 1 \leq z_i \leq 100, with at most 6 digits after the decimal point. Costs are integers in the range 1 \leq c_i \leq 10^6. The total input size is less than 16 MB.
For each tentative selection, your program should output the number of the operation when the currently chosen camera was offered. If making a choice according to the described rules is impossible, the result of that query should be "–1" (without quotes). All results for one test case should be output on a single line, separated by single spaces. The results of consecutive test cases should appear on consecutive lines.
Example 1
The first result line is empty because the first test case contains no "C" operations. For the first selection in the second test case, offer 1 ("1200000 1 40") is outdated, so 2 ("7200000 5 100") is the best, as it is the only one. For the 2nd "C" operation, the same choice is made, since it is cheaper than 4 ("9600000 3 200"). For the 3rd, 6 ("7200000 12 220") makes 2 ("7200000 5 100") outdated, and 4 ("9600000 3 200") becomes the cheapest among non-outdated cameras.