Выбор фотоаппарата

Господин Чудак выбирает цифровой фотоаппарат. Он изучает предложения магазинов и время от времени делает временный выбор. При каждом временном выборе он знает все предложения, с которыми уже ознакомился, но не знает предложений, которые увидит в будущем.

По представления господина Чудака, любой цифровой фотоаппарат можно полностью описать двумя свойствами: количеством пикселов и кратностью оптического зума. Для каждого из этих свойств он считает, что чем больше, тем лучше. Господин Чудак боится приобрести устаревший фотоаппарат; поэтому он никогда не выберет аппарат, зная о другом аппарате, строго лушему по одному из свойств и не худшему по другому. Среди всех фотоаппаратов, которые господин Чудак не считает устаревшими, он выбирает самый дешёвый. Если есть разные не устаревшие аппараты одинаковой минимальной стоимости, он выбирает среди них самое старое предложение.

Входные данные

Первая строка входных данных содержит количество тестовых случаев. Первая строка каждого тестового примера содержит общее количество действий 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") стаёт самым дешёвым серед не устаревших.