Главная улица Бертауна представляет собой прямую, на которой расположено 109 автобусных остановок. Остановки пронумерованы целыми числами от 1 до 109 в порядке следования. В городе ходит n автобусов. Каждый день i-ый автобус едет от остановки с номером si до остановки с номером fi (si < fi), останавливаясь на всех промежуточных остановках, и возвращается назад только ночью. Автобус начинает движение в момент времени ti, и едет настолько быстро, что заканчивает движение в тот же момент времени ti. Времена ti различны для всех автобусов. Автобусы имеют бесконечную вместимость.
В Бертауне живет m человек. Сегодня i-ому человеку нужно доехать от остановки с номером li до остановки с номером ri (li < ri); i-ый житель приходит на свою начальную остановку (li) в момент времени bi. Каждый человек, с одной стороны, хочет добраться как можно быстрее, и с другой стороны, категорически не согласен ехать с пересадками. Более формально: i-ый человек выбирает автобус j, с минимальным временем tj, такой что sj ≤ li, ri ≤ fj и bi ≤ tj.
Ваша задача — определить для каждого жителя, сможет ли он доехать сегодня днем, и если сможет, найти номер автобуса, на котором он поедет.
Выходные данные
В первой строке выведите через пробел m целых чисел: i-ое число должно быть равно либо -1, если i-ый человек не сможет доехать, либо номеру автобуса, на котором i-ый человек поедет. Автобусы нумеруются целыми числами от 1 до n в том порядке, в котором они заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 10 10
5 6 2
6 7 3
5 7 4
5 7 1
1 2 1
1 10 11
|
4 1 -1
|
|
2
|
1 1
1 1000000000 1000000000
1 1000000000 1000000000
|
1
|