Главная улица Бертауна представляет собой прямую, на которой расположено 10⁹ автобусных остановок. Остановки пронумерованы целыми числами от 1 до 10⁹ в порядке следования. В городе ходит n автобусов. Каждый день i-ый автобус едет от остановки с номером s_i до остановки с номером f_i (s_i < f_i), останавливаясь на всех промежуточных остановках, и возвращается назад только ночью. Автобус начинает движение в момент времени t_i, и едет настолько быстро, что заканчивает движение в тот же момент времени t_i. Времена t_i различны для всех автобусов. Автобусы имеют бесконечную вместимость.

В Бертауне живет m человек. Сегодня i-ому человеку нужно доехать от остановки с номером l_i до остановки с номером r_i (l_i < r_i); i-ый житель приходит на свою начальную остановку (l_i) в момент времени b_i. Каждый человек, с одной стороны, хочет добраться как можно быстрее, и с другой стороны, категорически не согласен ехать с пересадками. Более формально: i-ый человек выбирает автобус j, с минимальным временем t_j, такой что s_j ≤ l_i, r_i ≤ f_j и b_i ≤ t_j.

Ваша задача — определить для каждого жителя, сможет ли он доехать сегодня днем, и если сможет, найти номер автобуса, на котором он поедет.