Задача D. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

Формат входного файла

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

Примеры тестов

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Разбор

Если m_j > m_i, p_j > p_i, t_j > t_i, то будем говорить, что j-ый преподаватель сильнее i-ого. Упорядочим всех преподавателей по неубыванию m_i. Теперь для каждого i-го преподавателя (индекс указан уже в новом упорядочении) сильнее его могут быть только преподаватели с номерами j ≥ i₀, где i₀ — наименьший индекс больший i, для которого m_i0 > m_i.

Будем перебирать преподавателей по убыванию i и для каждого отвечать на вопрос: "существует ли преподаватель сильнее его?". Будем поддерживать структуру данных, ключами в которой будут являться параметры p, а значениями параметры t. При уменьшении i индекс i₀ неувеличивается. Если индекс i₀ уменьшился, то добавим всех преподавателей с индексами между старым и новым значениями i₀ (включая последнее) в нашу структуру. Таким образом, структура данных будет содержать второй и третий параметры всех преподавателей, которые могут быть сильнее i-го.

Для того чтобы определить, присутствует ли в нашей структуре преподаватель сильнее i-го, необходимо выяснить, какое максимальное значение (назовём его t_max) принимает параметр t для ключей p, которые строго больше нашего p_i. Если t_max > t_i, значит существует преподаватель, у которого первый параметр больше (потому что информация о нём находится в нашей структуре данных), второй параметр больше (потому что он удовлетворяет нашему запросу), и третий параметр больше (потому что его третий параметр и есть t_max).

В качестве структуры данных, с помощью которой можно ответить на подобный запрос (найти максимум значений на отрезке ключей), может выступить дерево интервалов.