Choosing a Camera

Mr. Oddball is in the market for a digital camera. He reviews various store offers and occasionally makes a tentative selection. With each tentative selection, he is aware of all the offers he has seen so far but has no knowledge of future offers.

In Mr. Oddball's opinion, a digital camera can be completely characterized by two attributes: the number of pixels and the optical zoom factor. For both attributes, he believes that more is better. Mr. Oddball is wary of purchasing an outdated camera; hence, he will never choose a camera if he knows of another camera that is strictly better in one attribute and at least as good in the other. Among all the cameras that Mr. Oddball does not consider outdated, he selects the least expensive one. If there are multiple non-outdated cameras with the same minimum cost, he opts for the earliest offer among them.

Input

The first line of the input contains the number of test cases. The first line of each test case specifies the total number of actions n (1 ≤ n ≤ 10^5). Each action is either a new camera offer or a tentative selection. Each offer is indicated by the capital letter "P", followed by the number of pixels, zoom factor, and cost. Each tentative selection is indicated by the capital letter "C". Each action is presented on a separate line, with data within the lines separated by single spaces.

The number of pixels is an integer within 10^3 ≤ p_i ≤ 10^9. The zoom factors are fractional numbers within 1 ≤ z_i ≤ 100, with up to 6 decimal places. Costs are integers within 1 ≤ c_i ≤ 10^6. The input data size is less than 16 MB.

Output

For each tentative selection, your program should output the action number when the currently chosen camera was offered. If it is impossible to make a selection according to the described rules, the result of the corresponding query should be "–1" (without quotes). All results related to one test case should be output on one line, separated by single spaces. Results of consecutive test cases should appear on consecutive lines.

Examples

Note

The first line of the result is empty because the first test case contains no "C" actions. For the first selection of the second test case, the camera from offer 1 ("1200000 1 40") is outdated, so 2 ("7200000 5 100") is the best as it is the only one. For the 2-nd "C" action, the same choice is made because it is cheaper than 4 ("9600000 3 200"). For the 3-rd, 6 ("7200000 12 220") makes 2 ("7200000 5 100") outdated, and 4 ("9600000 3 200") becomes the cheapest among non-outdated ones.