← 返回题目列表

Codeforces · 1725/F

F. 实地摄影

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

Pak Chanek 正在前往万鸦老。原来,2019年OSN(印度尼西亚国家科学奥林匹克竞赛)正在举办。 OSN 2019的参赛者目前正在拍照场地排队。该字段的形状类似于大小为 $$$N \times 10^{100}$$$ 的网格,其中包含 $$$N$$$ 行和 $$$10^{100}$$$ 列。行从北到南编号为 $$$1$$$ 到 $$$N$$$,列从西到东编号为 $$$1$$$ 到 $$$10^{100}$$$。 $$$r$$$ 行和 $$$c$$$ 列中的图块表示为 $$$(r,c)$$$。

参加 OSN 2019 的省份有 $$$N$$$。最初,代表省份 $$$i$$$ 的每位参赛者都站在 $$$(i, p)$$$ 板块中,每个 $$$p$$$ 满足 $$$L_i \leq p \leq R_i$$$。因此,我们可以看到代表省份$$$i$$$的参赛者有$$$R_i-L_i+1$$$。

Pak Chanek 有一个变量 $$$Z$$$,最初等于 $$$0$$$。在一次操作中,Pak Chanek 可以选择一行 $$$i$$$ 和一个正整数 $$$k$$$。然后,Pak Chanek 将执行以下两种可能性之一:

- 将 $$$i$$$ 行中的所有参赛者恰好移至西边 $$$k$$$ 格。换句话说,$$$(i, p)$$$ 中的参赛者被移至 $$$(i, p-k)$$$。
- 将 $$$i$$$ 行中的所有参赛者恰好移动到东部 $$$k$$$ 块。换句话说,$$$(i, p)$$$ 中的参赛者被移至 $$$(i, p+k)$$$。

每次运算后,$$$Z$$$ 的值将变为 $$$Z \text{ OR } k$$$,其中 $$$\text{OR}$$$ 为按位或运算。请注意,Pak Chanek 可以多次对同一行执行操作。另请注意,Pak Chanek 不得将参赛者移出网格。

有 $$$Q$$$ 问题。对于第 $$$j$$$ 题,给定一个正整数 $$$W_j$$$,Pak Chanek 必须进行零次或多次运算,以便 $$$Z$$$ 的最终值恰好是 $$$W_j$$$。将 $$$M$$$ 定义为最大数字,以便在所有操作之后,至少有一列恰好包含 $$$M$$$ 参赛者。对于每个问题,您必须找到 Pak Chanek 可以完成的所有操作序列的最大可能 $$$M$$$。请注意,Pak Chanek 对一个问题所做的操作不会延续到其他问题。

输入

第一行包含一个整数 $$$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$$$ 最终值。

输出

输出 $$$Q$$$ 行,其中第 $$$j$$$ 行包含一个整数,该整数是第 $$$j$$$ 问题的答案。

示例

输入 #1

3
1 5
10 11
8 8
2
12
5

输出 #1

2
3

注意

对于$$$1$$$-st问题,Pak Chanek可以执行以下操作来得到$$$M=2$$$:

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

现在,$$$14$$$ 和 $$$15$$$ 列分别包含 $$$2$$$ 参赛者。

对于第 $$$2$$$-nd 题,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$$$-nd 问题的示例操作说明。