CF1935E.Distance Learning Courses in MAC

The New Year has arrived in the Master's Assistance Center, which means it's time to introduce a new feature!

Now students are given distance learning courses, with a total of $n$ courses available. For the $i$-th distance learning course, a student can receive a grade ranging from $x_i$ to $y_i$.

However, not all courses may be available to each student. Specifically, the $j$-th student is only given courses with numbers from $l_j$ to $r_j$, meaning the distance learning courses with numbers $l_j, l_j + 1, \ldots, r_j$.

The creators of the distance learning courses have decided to determine the final grade in a special way. Let the $j$-th student receive grades $c_{l_j}, c_{l_j + 1}, \ldots, c_{r_j}$ for their distance learning courses. Then their final grade will be equal to $c_{l_j}$ $|$ $c_{l_j + 1}$ $|$ $\ldots$ $|$ $c_{r_j}$, where $|$ denotes the bitwise OR operation.

Since the chatbot for solving distance learning courses is broken, the students have asked for your help. For each of the $q$ students, tell them the maximum final grade they can achieve.

新年已至，大师辅助中心即将推出一项新功能！

现在，学生们将参加远程学习课程，一共有 $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}$，其中 $|$ 表示按位或运算。

由于用于解答远程学习课程问题的聊天机器人出现故障，学生们特此向你求助。请对每位学生（共 $q$ 位），计算其能够取得的最高最终成绩。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of distance learning courses.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i \le y_i \lt 2^{30}$) — the minimum and maximum grade that can be received for the $i$-th course.

The next line contains a single integer $q$ ($1 \le q \le 2\cdot10^5$) — the number of students.

Each of the following $q$ lines contains two integers $l_j$ and $r_j$ ($1 \le l_j \le r_j \le n$) — the minimum and maximum course numbers accessible to the $j$-th student.

It is guaranteed that the sum of $n$ over all test cases and the sum of $q$ over all test cases do not exceed $2\cdot10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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 \lt 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$ 名学生可选课程的编号范围（即从第 $l_j$ 门到第 $r_j$ 门课程）。

保证所有测试用例的 $n$ 之和与所有测试用例的 $q$ 之和均不超过 $2\cdot10^5$。

For each test case, output $q$ integers, where the $j$-th integer is the maximum final grade that the $j$-th student can achieve.

对于每个测试用例，输出 $q$ 个整数，其中第 $j$ 个整数表示第 $j$ 个学生所能达到的最高最终成绩。

In the first test case:

1. The maximum grade for the first student is $1$:

   • On the first distance learning course, he will receive a grade of $1$.

   Therefore, the final grade is $1$.

2. The maximum grade for the second student is $5$:

   • On the first distance learning course, he will receive a grade of $1$.
   • On the second distance learning course, he will receive a grade of $4$.Therefore, the final grade is $1$ $|$ $4$ $=$ $5$.

3. The maximum grade for the third student is $4$:

   • On the second distance learning course, he will receive a grade of $4$.Therefore, the final grade is $4$.

In the second test case:

1. The maximum grade for the first student is $15$:

   • On the first distance learning course, he will receive a grade of $7$.
   • On the second distance learning course, he will receive a grade of $4$.
   • On the third distance learning course, he will receive a grade of $8$.

   Therefore, the final grade is $7$ $|$ $4$ $|$ $8$ $=$ $15$.

2. The maximum grade for the second student is $11$:

   • On the third distance learning course, he will receive a grade of $9$.
   • On the fourth distance learning course, he will receive a grade of $2$.Therefore, the final grade is $9$ $|$ $2$ $=$ $11$.

在第一个测试用例中：

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$。