CF1725F.Field Photography

Pak Chanek is traveling to Manado. It turns out that OSN (Indonesian National Scientific Olympiad) 2019 is being held. The contestants of OSN 2019 are currently lining up in a field to be photographed. The field is shaped like a grid of size $N \times 10^{100}$ with $N$ rows and $10^{100}$ columns. The rows are numbered from $1$ to $N$ from north to south, the columns are numbered from $1$ to $10^{100}$ from west to east. The tile in row $r$ and column $c$ is denoted as $(r,c)$.

There are $N$ provinces that participate in OSN 2019. Initially, each contestant who represents province $i$ stands in tile $(i, p)$ for each $p$ satisfying $L_i \leq p \leq R_i$. So, we can see that there are $R_i-L_i+1$ contestants who represent province $i$.

Pak Chanek has a variable $Z$ that is initially equal to $0$. In one operation, Pak Chanek can choose a row $i$ and a positive integer $k$. Then, Pak Chanek will do one of the two following possibilities:

• Move all contestants in row $i$ exactly $k$ tiles to the west. In other words, a contestant who is in $(i, p)$ is moved to $(i, p-k)$.
• Move all contestants in row $i$ exactly $k$ tiles to the east. In other words, a contestant who is in $(i, p)$ is moved to $(i, p+k)$.

After each operation, the value of $Z$ will change into $Z \text{ OR } k$, with $\text{OR}$ being the bitwise OR operation. Note that Pak Chanek can do operations to the same row more than once. Also note that Pak Chanek is not allowed to move contestants out of the grid.

There are $Q$ questions. For the $j$-th question, you are given a positive integer $W_j$, Pak Chanek must do zero or more operations so that the final value of $Z$ is exactly $W_j$. Define $M$ as the biggest number such that after all operations, there is at least one column that contains exactly $M$ contestants. For each question, you must find the biggest possible $M$ for all sequences of operations that can be done by Pak Chanek. Note that the operations done by Pak Chanek for one question do not carry over to other questions.

帕克·查内克正在前往万鸦老。结果发现，2019 年印度尼西亚全国科学奥林匹克竞赛（OSN）正在此举行。2019 年 OSN 的参赛选手们当前正排成一列，在一块场地上准备合影。该场地形状为一个 $N \times 10^{100}$ 的网格，共 $N$ 行、$10^{100}$ 列。行从北向南编号为 $1$ 至 $N$，列从西向东编号为 $1$ 至 $10^{100}$。位于第 $r$ 行、第 $c$ 列的格子记作 $(r,c)$。

共有 $N$ 个省份参加 2019 年 OSN。初始时，代表第 $i$ 个省份的每位选手均站在格子 $(i, p)$ 上，其中 $p$ 满足 $L_i \leq p \leq R_i$。因此，代表第 $i$ 个省份的选手共有 $R_i - L_i + 1$ 人。

帕克·查内克有一个变量 $Z$，其初始值为 $0$。在一次操作中，帕克·查内克可任选一行 $i$ 和一个正整数 $k$，然后执行以下两种操作之一：

• 将第 $i$ 行中的所有选手恰好向西移动 $k$ 格。换言之，位于 $(i, p)$ 的选手将被移至 $(i, p-k)$；
• 将第 $i$ 行中的所有选手恰好向东移动 $k$ 格。换言之，位于 $(i, p)$ 的选手将被移至 $(i, p+k)$。

每次操作后，$Z$ 的值将更新为 $Z \text{ OR } k$，其中 $\text{OR}$ 表示按位或运算。注意：帕克·查内克可对同一行执行多次操作；同时，他不允许将选手移出网格边界。

共有 $Q$ 个询问。对于第 $j$ 个询问，给定一个正整数 $W_j$，帕克·查内克必须执行零次或多次操作，使得最终 $Z$ 的值恰好等于 $W_j$。定义 $M$ 为：在所有操作完成后，某一列中所含选手数量的最大可能值（即存在至少一列恰好包含 $M$ 名选手）。对每个询问，你需要求出所有可行操作序列下所能达到的最大的 $M$ 值。注意：帕克·查内克为某一个询问所执行的操作不会影响其他询问。

The first line contains a single integer $N$ ($1 \leq N \leq 10^5$) — the number of rows in the grid and also the number of provinces that participate in OSN 2019.

The $i$-th of the next $N$ lines contains two integers $L_i$ and $R_i$ ($1 \leq L_i \leq R_i \leq 10^9$) describing the positions of the contestants who represent province $i$.

The next line contains a single integer $Q$ ($1 \leq Q \leq 10^5$) — the number of questions.

The $j$-th of the next $Q$ lines contains a single integer $W_j$ ($1 \leq W_j \leq 10^9$) — the required final value of $Z$ for the $j$-th question.

第一行包含一个整数 $N$（$1 \leq N \leq 10^5$），表示网格的行数，也等于参加 OSN 2019 的省份数量。

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $L_i$ 和 $R_i$（$1 \leq L_i \leq R_i \leq 10^9$），描述代表第 $i$ 个省份的参赛者的位置。

下一行包含一个整数 $Q$（$1 \leq Q \leq 10^5$），表示问题的数量。

接下来的 $Q$ 行中，第 $j$ 行包含一个整数 $W_j$（$1 \leq W_j \leq 10^9$），表示第 $j$ 个问题所要求的 $Z$ 的最终值。

Output $Q$ lines, with the $j$-th line containing an integer that is the answer to the $j$-th question.

输出 $Q$ 行，其中第 $j$ 行包含一个整数，表示第 $j$ 个问题的答案。

For the $1$-st question, Pak Chanek can do the following operations to get $M=2$:

• Move all contestants in row $2$ to the east by $4$ tiles. $Z$ changes into $0 \text{ OR } 4 = 4$.
• Move all contestants in row $1$ to the east by $12$ tiles. $Z$ changes into $4 \text{ OR } 12 = 12$.

Now, columns $14$ and $15$ each contains exactly $2$ contestants.

For the $2$-nd question, Pak Chanek can do the following operations to get $M=3$:

• Move all contestants in row $3$ to the east by $4$ tiles. $Z$ changes into $0 \text{ OR } 4 = 4$.
• Move all contestants in row $3$ to the west by $1$ tiles. $Z$ changes into $4 \text{ OR } 1 = 5$.
• Move all contestants in row $1$ to the east by $5$ tiles. $Z$ changes into $5 \text{ OR } 5 = 5$.
• Move all contestants in row $1$ to the east by $5$ tiles. $Z$ changes into $5 \text{ OR } 5 = 5$.

Now, column $11$ contains exactly $3$ contestants.

The following is an illustration of the example operations for the $2$-nd question.

对于第 $1$ 个问题，Pak Chanek 可以执行以下操作以得到 $M=2$：

• 将第 $2$ 行的所有参赛者向东移动 $4$ 格。此时 $Z$ 变为 $0 \text{ OR } 4 = 4$。
• 将第 $1$ 行的所有参赛者向东移动 $12$ 格。此时 $Z$ 变为 $4 \text{ OR } 12 = 12$。

此时，第 $14$ 列和第 $15$ 列各自恰好包含 $2$ 名参赛者。

对于第 $2$ 个问题，Pak Chanek 可以执行以下操作以得到 $M=3$：

• 将第 $3$ 行的所有参赛者向东移动 $4$ 格。此时 $Z$ 变为 $0 \text{ OR } 4 = 4$。
• 将第 $3$ 行的所有参赛者向西移动 $1$ 格。此时 $Z$ 变为 $4 \text{ OR } 1 = 5$。
• 将第 $1$ 行的所有参赛者向东移动 $5$ 格。此时 $Z$ 变为 $5 \text{ OR } 5 = 5$。
• 将第 $1$ 行的所有参赛者向东移动 $5$ 格。此时 $Z$ 变为 $5 \text{ OR } 5 = 5$。

此时，第 $11$ 列恰好包含 $3$ 名参赛者。

以下是第 $2$ 个问题示例操作的示意图。