Вибір фотоапарату

Пан Дивак вибирає цифровий фотоапарат. Він вивчає пропозиції магазинів і час від часу робить тимчасовий вибір. При кожному тимчасовому виборі, він знає всі пропозиції, з якими вже ознайомився, але не знає пропозицій, які побачить у майбутньому.

За уявленнями пана Дивака, будь-який цифровий фотоапарат можна цілком описати двома властивостями: кількістю пікселів та кратністю оптичного зума. Для кожної з цих властивостей, він вважає, що чим більше, тим краще. Пан Дивак боїться купити застарілий фотоапарат; тому, він ніколи не вибере апарат, знаючи про інший апарат, строго кращий за однією з властивостей і не гірший за іншою. Серед усіх фотоапаратів, які пан Дивак не вважає застарілими, він вибирає найдешевший. Якщо є різні не застарілі апарати однакової мінімальної вартості, він вибирає серед них найдавнішу пропозицію.

Вхідні дані

Перший рядок вхідних даних містить кількість тестових прикладів. Перший рядок кожного тестового прикладу містить загальну кількість дій n (1 ≤ n ≤ 10^5). Кожна дія — або нова пропозиція фотоапарату, або тимчасовий вибір. Кожна пропозиція позначається великою латинською літерою "P", потім кількістю пікселів, кратністю зума та вартістю. Кожен тимчасовий вибір позначається великою латинською літерою "С". Кожна дія зазначена в окремому рядку, дані всередині рядків відокремлені одинарними пропусками.

Кількості пікселів є цілими числами в межах 10^3 ≤ p_i ≤ 10^9. Кратності зума є дробовими числами в межах 1 ≤ z_i ≤ 100, не більш ніж з 6 знаками після десяткової крапки. Вартості є цілими числами в межах 1 ≤ c_i ≤ 10^6. Розмір вхідних даних менший 16 Мб.

Вихідні дані

Для кожного тимчасового вибору, Ваша програма повинна вивести номер тієї дії, коли був запропонований нині вибраний фотоапарат. Якщо зробити вибір згідно описаних правил неможливо, результатом відповідного запиту має бути "–1" (без лапок). Усі результати, що стосуються одного тестового прикладу, слід виводити в один рядок, розділяючи одинарними пропусками. Результати послідовних тестових прикладів повинні слідувати в послідовних рядках.

Приклади

Примітка

Перший рядок результату порожній, тому що перший тестовий приклад не містить дій "C". Для першого вибору другого тестового прикладу, апарат з пропозиції 1 ("1200000 1 40") застарілий, тому 2 ("7200000 5 100") найкращий бо єдиний. Для 2-ї дії "C" той самий вибір, бо так дешевше, ніж 4 ("9600000 3 200"). Для 3-ї, 6 ("7200000 12 220") робить 2 ("7200000 5 100") застарілим, і 4 ("9600000 3 200") стає найдешевшим серед не застарілих.