Kevin and Grid

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,…,a_n and an array b_1,b_2,…,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,…,c_k of cells such that c_i and c_{i+1} are adjacent for 1 ≤ i ≤ 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!

Input

The first line contains three integers n,m,q (1 ≤ n,m,q ≤ 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, ..., a_n (1 ≤ a_i ≤ 10^5).

The third line contains m integers b_1, b_2, ..., b_m (1 ≤ b_i ≤ 10^5).

Each of the next q lines contains one integer x (1 ≤ x ≤ 2 ⋅ 10^5).

Output

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

Examples

Input

5 5 1 1 3 2 3 1 1 3 2 3 1 5

Output

-1

Input

3 3 2 1 2 2 2 1 2 3 4

Output

0 1

Note

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.

inputFormat

Input

The first line contains three integers n,m,q (1 ≤ n,m,q ≤ 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, ..., a_n (1 ≤ a_i ≤ 10^5).

The third line contains m integers b_1, b_2, ..., b_m (1 ≤ b_i ≤ 10^5).

Each of the next q lines contains one integer x (1 ≤ x ≤ 2 ⋅ 10^5).

outputFormat

Output

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

Examples

Input

5 5 1 1 3 2 3 1 1 3 2 3 1 5

Output

-1

Input

3 3 2 1 2 2 2 1 2 3 4

Output

0 1

Note

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.

样例

5 5 1
1 3 2 3 1
1 3 2 3 1
5

-1

</p>