모자이크

ABBYY사의 자석 모자이크의 모든 조각은 직사각형이다. 두 조각은 길이, 너비, 또는 둘 다가 일치하면 연결할 수 있다. 자석 조각은 회전하거나 뒤집을 수 없다. 연결할 수 없는 모자이크 조각 쌍을 부조화 쌍이라고 하자. 예를 들어 $1 \times 2$와 $2 \times 3$은 부조화 쌍이고, $2 \times 3$과 $1 \times 3$, 또는 $2 \times 3$과 $2 \times 3$은 조화 쌍이다.

ABBYY의 디자이너들은 모자이크의 모든 조각을 서로 연결하지 않고 한 줄로 나열했다. 이 줄에서 연속으로 놓인 여러 조각을 묶음이라고 하자. 디자이너들은 인스톨레이션을 만들기 위해 남겨 두려는 여러 묶음을 골랐다. 각 묶음마다 그 안에 부조화 쌍이 있는지 알아내야 한다.

여러 묶음에 대해, 연속으로 놓인 모자이크 조각 중 부조화 쌍을 이루는 조각의 번호를 찾거나 그러한 쌍이 없다고 알려 주는 프로그램을 작성해야 한다.

첫째 줄에 모자이크를 이루는 조각의 수 $N$이 주어진다 ($2 \le N \le 100\,000$). 다음 $N$개 줄에 $i$번째 모자이크 조각의 길이와 너비를 나타내는 두 정수 $A_i$와 $B_i$가 주어진다 ($1 \le A_i, B_i \le 10^9$, $1 \le i \le N$).

$N+2$번째 줄에 부조화 조각 두 개의 번호를 찾아야 하는 묶음의 수 $K$가 주어진다 ($1 \le K \le 100\,000$). 다음 $K$개 줄에 부조화 조각 두 개를 찾아야 하는 묶음의 첫 번째 조각 번호와 마지막 조각 번호 $N_1$, $N_2$가 주어진다 ($1 \le N_1 < N_2 \le N$).

출력 파일은 $K$개 줄로 이루어져야 하며, 각 줄에는 해당 묶음에서 부조화 쌍을 이루는 모자이크 조각 두 개의 번호가 공백으로 구분되어 있어야 한다. 답이 여러 개면 그중 아무거나 출력해도 된다. 묶음에 부조화 쌍이 없으면 해당 줄에 0 0을 출력한다.