← 返回题目列表

Codeforces · 1935/E

E. MAC 远程学习课程

中文机器翻译题面 查看原题

大师援助中心新年已经到来,这意味着是时候推出新功能了!

现在为学生提供远程学习课程,总共提供 $$$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$$$。