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 问题的示例操作说明。