Friends

$n$ of Amin's friends gathered at his place to celebrate his birthday. They decided to gather in a row to make a toast to his health. Let's number them in this row from $1$ to $n$.

Among these friends, there are those who know each other and those who don't. Amin's friends' middle school $(a_i)$ and university $(b_i)$ are specified. If two people have different middle schools and different universities, they don't know each other. From a mathematical point of view, Amin's friends with number $i$ and number $j$ don't know each other if the conditions $a_i\ne a_j$ and $b_i\ne b_j$ are met.

And Amin, even though it's his birthday, still has strange thoughts and questions coming to his mind. "I wonder if there are two friends in the row from number $l$ to number $r$ (including $l$ and $r$) who don't know each other? 🤔"

Answer the questions that come to Amin's mind.

Input

The first line contains a single integer $n(2\le n\le 10^5)$, and in each of the following $n$ lines, there are two integers $a_i$ and $b_i(1\le a_i,b_i\le 10^9,1\le i\le n)$. The next line specifies the number of queries $q(1\le q\le 10^5)$ that Amin came up with. Each of the next $q$ lines specifies queries, namely two integers $l_j$ and $r_j(1\le l_j<r_j\le n)$.

Output

For each query, output two integers on a new line: the numbers of any two of Amin's friends who don't know each other in the specified range, and output $00$ if there are no such two friends. If there are multiple correct answers, any of them can be output.

Examples

Scoring

This problem consists of $4$ subtasks. Points for a subtask are awarded only if all the tests associated with that subtask are passed successfully.

1. ($20$ points): $n,q\le 100$;

2. ($30$ points): $n,q\le 1000$;

3. ($20$ points): $n,q\le 5000$;

4. ($30$ points): $noadditionalconstraints$;