Друзі

$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$ балів): $немаєдодатковихобмежень$;