Background

Translation source: loj #5459. 「ROI 2012 Day 2」Mosaic.

Problem Description

All magnetic mosaic elements made by ABBYY are rectangles. Two elements can be connected only if they share at least one dimension (length, width, or both). Magnetic elements cannot be rotated or flipped. If two mosaic elements cannot be connected, they are called an inharmonious pair. For example, $1 \times 2$ and $2 \times 3$ form an inharmonious pair, while $2 \times 3$ and $1 \times 3$, or $2 \times 3$ and $2 \times 3$, are harmonious pairs.

ABBYY’s designers placed all mosaic elements in a single line, but did not connect them. We call a consecutive segment of elements in the line a set. They chose some sets to create an art installation, and need to determine whether each set contains an inharmonious pair of elements.

You need to write a program that, for each query segment of consecutive elements, finds the indices of two elements that form an inharmonious pair, or reports that no such pair exists in the segment.

Input Format

The first line of the input contains an integer $N$ $(2 \leq N \leq 100000)$, the number of mosaic elements.

The next $N$ lines each contain two integers $A_i$ and $B_i$ $(1 \leq A_i, B_i \leq 10^{9}, 1 \leq i \leq N)$, representing the length and width of the $i$-th mosaic element.

The $(N + 2)$-th line contains an integer $K$ $(1 \leq K \leq 100000)$, the number of sets to be checked for inharmonious pairs.

The next $K$ lines each contain two integers $N_1$ and $N_2$ $(1 \leq N_1 < N_2 \leq N)$, the indices of the first and last elements of a set, within which you need to find an inharmonious pair.

Output Format

The output should contain $K$ lines. Each line contains two integers separated by a space, the indices of two mosaic elements that form an inharmonious pair in the corresponding set. If multiple answers exist, you may output any one. If there is no inharmonious pair in the set, output 0 0.

4
2 2
1 2
1 3
2 3
2
2 3
2 4

0 0
4 2

Hint

Detailed additional constraints and scores for subtasks are shown in the table below.

Translated by ChatGPT 5