Друзья

$n$ друзей Амина собрались у него дома, чтобы отпраздновать его день рождения. Они решились собраться в ряд чтобы сказать тост за его здоровье. Пронумеруем их в этом ряду от $1$ до $n$.

Среди этих друзей есть те, кто знает друг друга, и те, кто не знает. Указаны средняя школа $(a_i)$ и университет $(b_i)$, которые посещают друзья Амина. Если у двух людей разные средние школы и разные университеты, они не знают друг друга. С математической точки зрения, друзья Амина с номером $i$ и номером $j$ не знают друг друга, если выполняются условия $a_i\ne a_j$ и $b_i\ne b_j$.

А Амин, хоть у него и день рождения, все равно приходит ему в голову странные мысли и вопросы. “Интересно, есть ли в ряду от номера $l$ до номера $r$ двое друзей (включая $l$ и $r$), которые не знают друг друга? 🤔”

Ответьте на вопросы, которые приходят в голову Амина.

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

В первой строке задано одно целое число $n(2\le n\le 10^5)$, а в каждой из следующих $n$ строк — по два целых числа $a_i$ и $b_i(1\le a_i,b_i\le 10^9,1\le i\le n)$. В следующей строке указано количество запросов $q(1\le q\le 10^5)$, которые придумал Амин. В каждой из следующих $q$ строк заданы запросы, а именно два целых числа $l_j$ и $r_j(1\le l_j<r_j\le n)$.

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

Для каждого запроса выведите два целых числа с новой строки: номера любых двух друзей Амина, которые не знают друг друга в заданном диапазоне, и выведите $00$, если таких двух друзей нет. Если правильных ответов несколько, можно вывести любой из них.

Примеры

Оценивание

Данная задача состоит из $4$-х подзадач. Баллы за подзадачу начисляются только в случае успешного прохождения всех тестов, связанных с этой подзадачой.

1. ($20$ баллов): $n,q\le 100$;

2. ($30$ баллов): $n,q\le 1000$;

3. ($20$ баллов): $n,q\le 5000$;

4. ($30$ баллов): $нетдополнительныхограничений$;