大师援助中心新年已经到来,这意味着是时候推出新功能了!
现在为学生提供远程学习课程,总共提供 $$$n$$$ 课程。对于第 $$$i$$$ 远程学习课程,学生可以获得从 $$$x_i$$$ 到 $$$y_i$$$ 的成绩。
但是,并非所有课程都可供每个学生使用。具体来说,第 $$$j$$$ 学生只接受编号从 $$$l_j$$$ 到 $$$r_j$$$ 的课程,这意味着编号为 $$$l_j, l_j + 1, \ldots, r_j$$$ 的远程学习课程。
远程学习课程的创建者决定以特殊方式确定最终成绩。让第 $$$j$$$ 学生的远程学习课程成绩为 $$$c_{l_j}, c_{l_j + 1}, \ldots, c_{r_j}$$$。那么他们的最终成绩将等于 $$$c_{l_j}$$$ $$$|$$$ $$$c_{l_j + 1}$$$ $$$|$$$ $$$\ldots$$$ $$$|$$$ $$$c_{r_j}$$$,其中 $$$|$$$ 表示按位 OR 运算。
由于解决远程学习课程的聊天机器人坏了,学生们请求您的帮助。对于每个 $$$q$$$ 学生,告诉他们他们可以获得的最高最终成绩。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 远程学习课程的数量。
以下 $$$n$$$ 行中的每一行都包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i \le y_i < 2^{30}$$$) — 第 $$$i$$$ 课程可以获得的最低和最高成绩。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — 学生人数。
以下 $$$q$$$ 行中的每一行都包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — 第 $$$j$$$ 学生可以访问的最小和最大课程编号。
保证所有测试用例的 $$$n$$$ 总和以及所有测试用例的 $$$q$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 个整数,其中第 $$$j$$$ 个整数是第 $$$j$$$ 个学生可以获得的最高最终成绩。
示例
输入 #1
3 2 0 1 3 4 3 1 1 1 2 2 2 4 1 7 1 7 3 10 2 2 5 1 3 3 4 2 3 1 4 1 2 6 1 2 2 2 0 1 1 1 3 3 0 0 4 3 4 5 5 2 5 1 2
输出 #1
1 5 4 15 11 15 15 7 1 3 3 3
注意
在第一个测试用例中:
1. 第一个学生的最高成绩为 $$$1$$$:在第一门远程学习课程中,他将获得 $$$1$$$ 成绩。 因此,最终成绩为$$$1$$$。
2. 第二个学生的最高成绩为 $$$5$$$:在第一门远程学习课程中,他将获得 $$$1$$$ 成绩。 在第二个远程学习课程中,他将获得 $$$4$$$ 的成绩。 因此,最终成绩为$$$1$$$ $$$|$$$ $$$4$$$ $$$=$$$ $$$5$$$。
3. 第三名学生的最高成绩为 $$$4$$$:在第二个远程学习课程中,他将获得 $$$4$$$ 成绩。 因此,最终成绩为$$$4$$$。
在第二个测试用例中:
1. 第一个学生的最高成绩为 $$$15$$$:在第一个远程学习课程中,他将获得 $$$7$$$ 成绩。 在第二个远程学习课程中,他将获得 $$$4$$$ 的成绩。 在第三门远程学习课程中,他将获得 $$$8$$$ 的成绩。 因此,最终成绩为$$$7$$$ $$$|$$$ $$$4$$$ $$$|$$$ $$$8$$$ $$$=$$$ $$$15$$$。
2. 第二个学生的最高成绩为 $$$11$$$:在第三个远程学习课程中,他将获得 $$$9$$$ 成绩。 在第四个远程学习课程中,他将获得 $$$2$$$ 的成绩。 因此,最终成绩为$$$9$$$ $$$|$$$ $$$2$$$ $$$=$$$ $$$11$$$。