时间限制： 5.0 秒

空间限制： 512 MB

题目描述

在一所魔法学校中，有许多的学生，每个学生有一个学号（从 $1$ 开始,用连续的正整数编号）。

每天，这所学校的校长会向一些学生发送一条短信（具体来说，在第 $i$ 天，校长会向学号在区间 $[L_i,R_i]$ 内的学生发送一条短信，每天的 $L_i$ 和 $R_i$ 可能不同）；从第 $1$ 天开始，一共持续 $n$ 天。

现在，学校的教导主任想要知道，在第 $A_i$ 天到第 $B_i$ 天（包含第 $A_i$ 天和第 $B_i$ 天），哪个学生收到的短信数量最多，最多数量是多少。

由于教导主任太忙了，所以现在麻烦你帮他找到答案。

输入格式

从标准输入读入数据。

输入文件第一行一个正整数 $n$，表示校长连续 $n$ 天向学生发送短信。

接下来 $n$ 行，每行两个正整数 $L_i,R_i$，表示第 $i$ 天校长向学号在区间 $[L_i,R_i]$ 内的同学发一条短信。

接下来一行一个正整数 $m$，表示教导主任有 $m$ 个询问。

接下来 $m$ 行，每行两个正整数 $A_i,B_i$，表示询问第 $A_i$ 天到第 $B_i$ 天（包含第 $A_i$ 天和第 $B_i$ 天），哪个学生收到的短信数量最多，最多数量是多少。

输出格式

输出到标准输出。

输出文件共 $m$ 行，每行输出空格隔开的两个正整数表示对应的教导主任询问的答案。

每行的第一个数表示收到最多短信的学生的学号，如果有多个学生均收到了最多数量的短信，你只需要输出他们之中最小的学号。

每行的第二个数表示该学生在第 $A_i$ 天到第 $B_i$ 天（包含第 $A_i$ 天和第 $B_i$ 天）一共收到了多少条短信。

5
1 5
1 3
3 5
2 2
4 10
3
1 1
1 3
3 4

1 1
3 3
2 1

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于 $30\%$ 的数据，$1 \le n \le 5 \times 10^2$，$1 \le L_i \le R_i \le 5 \times 10^2$，$1 \le m \le 5 \times 10^2$。

对于 $70\%$ 的数据，$1 \le n \le 5 \times 10^3$，$1 \le L_i \le R_i \le 5 \times 10^3$，$1 \le m \le 5 \times 10^3$。

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^4$，$1 \le L_i \le R_i \le 5 \times 10^4$，$1 \le m \le 5 \times 10^4$，$1 \le A_i \le B_i \le n$。