Mosaic

All pieces of the ABBYY magnetic mosaic are rectangular. Two pieces can be joined only if at least one of their dimensions matches: length, width, or both. Magnetic pieces cannot be rotated or flipped. A pair of mosaic pieces that cannot be joined is called inharmonious. For example, the pair $1 \times 2$ and $2 \times 3$ is inharmonious, while the pairs $2 \times 3$ and $1 \times 3$, and $2 \times 3$ and $2 \times 3$, are harmonious.

The designers at ABBYY laid out all mosaic pieces in a row without joining them. A set is several consecutive pieces in this row. They chose several sets of pieces that they want to keep for an installation. For each such set they need to determine whether it contains an inharmonious pair of pieces.

Write a program that, for various sets of consecutive mosaic pieces, determines the indices of the pieces forming an inharmonious pair, or reports that no such pair exists.

The first line of the input file contains a single number $N$, the number of pieces in the mosaic ($2 \le N \le 100\,000$). The next $N$ lines contain two integers $A_i$ and $B_i$ each, the length and width of the $i$-th mosaic piece ($1 \le A_i, B_i \le 10^9$, $1 \le i \le N$).

The $(N+2)$-th line contains a single integer $K$, the number of sets in which the indices of two inharmonious pieces must be determined ($1 \le K \le 100\,000$). The next $K$ lines contain pairs of integers $N_1$ and $N_2$, the indices of the first and last pieces of a set in which two inharmonious mosaic pieces must be found ($1 \le N_1 < N_2 \le N$).

The output file must contain $K$ lines, each with two space-separated numbers: the indices of the mosaic pieces forming an inharmonious pair in the corresponding set. If there are several answers, output any of them. If a set has no inharmonious pair, output 0 0 on the corresponding line.