P15298 [ROI 2012 Day 2] mosaic 马赛克

翻译来源：[loj #5459. 「ROI 2012 Day 2」马赛克](https://loj.ac/p/5459)。

ABBYY 公司的所有磁性马赛克元素均为矩形。只有当两个元素至少有一个尺寸（长度、宽度或两者）相同时，才能将它们连接在一起。磁性元素不可旋转或翻转。如果两个马赛克元素无法连接，则称它们为**不和谐对**。例如，$1 \times 2$ 和 $2 \times 3$ 是一对不和谐对，而 $2 \times 3$ 和 $1 \times 3$ 或 $2 \times 3$ 和 $2 \times 3$ 则是和谐对。 ABBYY 的设计师将所有马赛克元素排成一行，但未将它们连接在一起。我们将一行中连续的若干元素称为一个**集合**。他们选择了一些集合用于创建艺术装置，并需要确定每个集合中是否存在不和谐对的元素。 你需要编写一个程序，对于不同连续元素集合，确定构成不和谐对的元素编号，或者报告该集合中不存在这样的对。

输入文件的第一行包含一个整数 $N$ $(2 \leq N \leq 100000)$，表示马赛克元素的数量。 接下来的 $N$ 行，每行包含两个整数 $A_i$ 和 $B_i$ $(1 \leq A_i, B_i \leq 10^{9}, 1 \leq i \leq N)$，分别表示第 $i$ 个马赛克元素的长度和宽度。 第 $(N + 2)$ 行包含一个整数 $K$ $(1 \leq K \leq 100000)$，表示需要检查不和谐对的集合数量。 接下来的 $K$ 行，每行包含两个整数 $N_1$ 和 $N_2$ $(1 \leq N_1 < N_2 \leq N)$，分别表示每个集合的第一个和最后一个元素的编号，需要在该集合中查找不和谐对。

输出文件应包含 $K$ 行，每行包含两个以空格分隔的整数，表示对应集合中构成不和谐对的马赛克元素编号。如果存在多个解，可以输出任意一个。如果集合中不存在不和谐对，则在对应行输出 `0 0`。

详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | | :----: | :--: | :---------------------------------: | | $1$ | $20$ | 马赛克元素数量 $N \leq 100$，集合数量 $K \leq 100$ | | $2$ | $30$ | 马赛克元素数量 $N \leq 1000$，集合数量 $K \leq 1000$ | | $3$ | $20$ | 马赛克元素数量 $N \leq 5000$，集合数量 $K \leq 5000$ | | $4$ | $30$ | 马赛克元素数量 $N \leq 100000$，集合数量 $K \leq 100000$ |