Kevin and Grid

题意翻译

小L最近正在研究一个矩阵陷阱，这个矩阵是$n\times m$的。 当你掉进这个陷阱的时候，你可能会掉到这个矩阵的任意一个小方格内。矩阵的每行都有一个加热器，可以给一整行进行加热，$a_i$表示可以给第$i$行的每个格子加热的温度，同理，矩阵的每列也都有一个加热器，$b_i$表示可以把第$i$列的每个格子加热的温度。于是第$i$行第$j$列的格子的温度就变成了$a_i+b_j$。 幸运的是，当你掉进这个陷阱的时候，你的身上会马上出现一件防护衣，这件防护衣有两种模式可以选择。 1. 热抗模式：也就是你穿着这件防护衣可以在任意温度大于等于$x$的格子里面行走（当然这些格子必须要上下左右相邻）。如果你走到了一个温度低于 x 的格子上，那么这件防护衣马上就 会灰飞烟没（此时你也灰飞烟灭了）。 2. 冷抗模式：也就是你穿着这件防护衣可以在任意温度低于 x 的格子里面行走（同理这些格子必须要上下左右相邻）。如果你走到了一个温度大于等于 x 的格子上，那么这件防护衣就会灰飞烟灭（你也完了）。 总结一下，也就是说当你掉进陷阱的某个格子的时候，防护衣会自动选择模式，然后这个模式在你行走的时候不能被改变。 我们定义一个联通块为在一种模式下可以相互到达的一些格子。 我们定义一个联通块是“好“的，即这个联通块里面至少有一个格子在边界上，反之这个联通块就是“坏”的。 为了评估当前的矩阵，小L会给每个联通块打分，“好”的联通块分数是$1$分，“坏”的联通块分数是$2$分。 现在，小L想要知道在这个矩阵里面，热抗模式的联通块的分数减去冷抗模式的联通块的分数的差值是多少 为了增加难度，这里有$q$个$x$让你计算，即对于每个$x$，你都要计算出一个答案。

题目描述

As Kevin is in BigMan's house, suddenly a trap sends him onto a grid with $ n $ rows and $ m $ columns. BigMan's trap is configured by two arrays: an array $ a_1,a_2,\ldots,a_n $ and an array $ b_1,b_2,\ldots,b_m $ . In the $ i $ -th row there is a heater which heats the row by $ a_i $ degrees, and in the $ j $ -th column there is a heater which heats the column by $ b_j $ degrees, so that the temperature of cell $ (i,j) $ is $ a_i+b_j $ . Fortunately, Kevin has a suit with one parameter $ x $ and two modes: - heat resistance. In this mode suit can stand all temperatures greater or equal to $ x $ , but freezes as soon as reaches a cell with temperature less than $ x $ . - cold resistance. In this mode suit can stand all temperatures less than $ x $ , but will burn as soon as reaches a cell with temperature at least $ x $ . Once Kevin lands on a cell the suit automatically turns to cold resistance mode if the cell has temperature less than $ x $ , or to heat resistance mode otherwise, and cannot change after that. We say that two cells are adjacent if they share an edge. Let a path be a sequence $ c_1,c_2,\ldots,c_k $ of cells such that $ c_i $ and $ c_{i+1} $ are adjacent for $ 1 \leq i \leq k-1 $ . We say that two cells are connected if there is a path between the two cells consisting only of cells that Kevin can step on. A connected component is a maximal set of pairwise connected cells. We say that a connected component is good if Kevin can escape the grid starting from it — when it contains at least one border cell of the grid, and that it's bad otherwise. To evaluate the situation, Kevin gives a score of $ 1 $ to each good component and a score of $ 2 $ for each bad component. The final score will be the difference between the total score of components with temperatures bigger than or equal to $ x $ and the score of components with temperatures smaller than $ x $ . There are $ q $ possible values of $ x $ that Kevin can use, and for each of them Kevin wants to know the final score. Help Kevin defeat BigMan!

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , $ q $ ( $ 1 \leq n,m,q \leq 10^5 $ ) – the number of rows, columns, and the number of possible values for $ x $ respectively. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ). The third line contains $ m $ integers $ b_1, b_2, \dots, b_m $ ( $ 1 \leq b_i \leq 10^5 $ ). Each of the next $ q $ lines contains one integer $ x $ ( $ 1 \leq x \leq 2 \cdot 10^5 $ ).

输出格式

Output $ q $ lines, in the $ i $ -th line output the answer for the $ i $ -th possible value of $ x $ from the input.

输入输出样例

输入样例 #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

说明

In the first example, the score for components with temperature smaller than $ 5 $ is $ 1+2 $ , and the score for components with temperature at least $ 5 $ is $ 2 $ . Thus, the final score is $ 2-3=-1 $ .