Bobo 被困在一个奇特的一天无限循环中！每一天恰好有 $k$ 个小时，且每天都有 $n$ 个任务需要 Bobo 完成。

• 每天的第 $i$ 个任务在第 $a_i$ 个小时开始时到达，需要 $b_i$ 个小时的连续工作才能完成。
• Bobo 工作勤奋且总是遵循严格的准则：只要有未完成的任务，Bobo 就会处理最早到达的那个未完成任务。

在第一天的开始，Bobo 手头没有任何任务。

你的任务是帮助 Bobo 回答 $q$ 个询问。对于第 $i$ 个询问，给定任务到达的天数 $x_i$ 以及该天到达的任务索引 $y_i$。你的目标是确定 Bobo 完成第 $x_i$ 天第 $y_i$ 个任务的具体天数和小时数。

输入格式

第一行包含三个空格分隔的整数 $n$ ($1 \le n \le 10^5$)，$k$ ($1 \le k \le 10^8$) 和 $q$ ($1 \le q \le 10^5$)。

接下来的 $n$ 行，每行包含两个空格分隔的整数，其中第 $i$ 行包含 $a_i$ ($1 \le a_i \le k$) 和 $b_i$ ($1 \le b_i \le k$)。保证 $a_i$ 严格单调递增。

随后 $q$ 行，每行包含两个空格分隔的整数，其中第 $i$ 行包含 $x_i$ ($1 \le x_i \le 5 \times 10^5$) 和 $y_i$ ($1 \le y_i \le n$)。

输出格式

输出 $q$ 行，其中第 $i$ 行输出两个空格分隔的整数 $d_i$ 和 $h_i$，表示第 $i$ 个询问对应的任务在第 $d_i$ 天的第 $h_i$ 个小时完成。

样例

样例输入 1

2 5 6
1 1
4 3
1 1
1 2
2 1
2 2
3 1
3 2

样例输出 1

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

样例输入 2

3 10 5
2 4
3 1
10 7
2 2
7 1
4 3
5 2
28 3

样例输出 2

3 1
8 10
6 2
6 7
34 10