当凯文在 BigMan 的房子里时,突然一个陷阱把他送到了一个有 $$$n$$$ 行和 $$$m$$$ 列的网格上。
BigMan 的陷阱由两个数组配置:数组 $$$a_1,a_2,\ldots,a_n$$$ 和数组 $$$b_1,b_2,\ldots,b_m$$$。
在第 $$$i$$$ 行中有一个加热器,该加热器将该行加热 $$$a_i$$$ 度,在第 $$$j$$$ 列中有一个加热器将该列加热 $$$b_j$$$ 度,因此单元 $$$(i,j)$$$ 的温度为 $$$a_i+b_j$$$。
幸运的是,Kevin 有一套带有一个参数 $$$x$$$ 和两种模式的套装:
- 耐热性。在此模式下,套装可以承受所有大于或等于 $$$x$$$ 的温度,但一旦到达温度低于 $$$x$$$ 的单元格就会冻结。
- 耐寒性。在此模式下,套装可以承受低于 $$$x$$$ 的所有温度,但一旦到达温度至少为 $$$x$$$ 的单元格就会燃烧。
一旦凯文降落在一个单元上,如果单元的温度低于$$$x$$$,套装会自动转为耐寒模式,否则转为耐热模式,并且此后无法更改。
如果两个单元共享一条边,我们就说它们是相邻的。
令路径为单元格序列 $$$c_1,c_2,\ldots,c_k$$$,使得 $$$c_i$$$ 和 $$$c_{i+1}$$$ 相邻 $$$1 \leq i \leq k-1$$$。
如果两个单元格之间存在一条仅由 Kevin 可以踩到的单元格组成的路径,我们就说两个单元格是相连的。
连接分量是成对连接单元的最大集合。
如果 Kevin 能够从它开始逃离网格(当它至少包含一个网格边界单元时),我们就说一个连通分量是好的,否则它就是坏的。
为了评估情况,Kevin 给每个好的组件打了 $$$1$$$ 的分数,给每个坏的组件打了 $$$2$$$ 的分数。
最终得分将是温度大于或等于$$$x$$$的组件的总分与温度小于$$$x$$$的组件的得分之差。
Kevin 可以使用 $$$q$$$ 个可能的 $$$x$$$ 值,对于每个值,Kevin 想知道最终得分。
帮助凯文击败BigMan!
输入
第一行包含三个整数 $$$n$$$,$$$m$$$,$$$q$$$ ($$$1 \leq n,m,q \leq 10^5$$$) – 分别是行数、列数以及 $$x$$$ 的可能值数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 10^5$$$)。
接下来的每一行 $$$q$$$ 都包含一个整数 $$$x$$$ ($$$1 \leq x \leq 2 \cdot 10^5$$$)。
输出
输出 $$$q$$$ 行,在第 $$$i$$$ 行中输出输入中 $$$x$$$ 的第 $$$i$$$ 可能值的答案。
示例
输入 #1
5 5 1 1 3 2 3 1 1 3 2 3 1 5
输出 #1
-1
输入 #2
3 3 2 1 2 2 2 1 2 3 4
输出 #2
0 1
注意
在第一个示例中,温度小于 $$$5$$$ 的组件的得分为 $$$1+2$$$,温度至少为 $$$5$$$ 的组件的得分为 $$$2$$$。因此,最终得分为$$$2-3=-1$$$。