#5459. 「ROI 2012 Day 2」马赛克

题目描述

译自 $ROI$ $2012$ $Day2$ $T1.$ Мозаика

$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$。

样例

输入

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

输出

0 0
4 2

数据范围与提示

详细子任务附加限制及分值如下表所示：