CF1935E Distance Learning Courses in MAC

新年到来了，Master's Assistance Center 也迎来了新功能！ 现在学生们可以参加远程学习课程，总共有 $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} \mid c_{l_j + 1} \mid \ldots \mid c_{r_j}$，其中 $\mid$ 表示[按位或](https://en.wikipedia.org/wiki/Bitwise_operation#OR)运算。 由于用于解决远程课程的聊天机器人坏了，学生们请求你的帮助。对于每个学生，请告诉他们能够获得的最大最终成绩。

每个测试包含多组测试数据。第一行包含一个整数 $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. 第一个学生的最大成绩为 $1$： - 在第一门远程课程中，他可以获得 $1$ 分。 - 因此，最终成绩为 $1$。 2. 第二个学生的最大成绩为 $5$： - 在第一门远程课程中，他可以获得 $1$ 分。 - 在第二门远程课程中，他可以获得 $4$ 分。 - 因此，最终成绩为 $1 \mid 4 = 5$。 3. 第三个学生的最大成绩为 $4$： - 在第二门远程课程中，他可以获得 $4$ 分。 - 因此，最终成绩为 $4$。 在第二个测试数据中： 1. 第一个学生的最大成绩为 $15$： - 在第一门远程课程中，他可以获得 $7$ 分。 - 在第二门远程课程中，他可以获得 $4$ 分。 - 在第三门远程课程中，他可以获得 $8$ 分。 - 因此，最终成绩为 $7 \mid 4 \mid 8 = 15$。 2. 第二个学生的最大成绩为 $11$： - 在第三门远程课程中，他可以获得 $9$ 分。 - 在第四门远程课程中，他可以获得 $2$ 分。 - 因此，最终成绩为 $9 \mid 2 = 11$。 由 ChatGPT 4.1 翻译