给定 $n$ 条垂直线，其 $x$ 坐标分别为 $x_1, x_2, \dots, x_n$，权重分别为 $a_1, a_2, \dots, a_n$；以及 $m$ 条水平线，其 $y$ 坐标分别为 $y_1, y_2, \dots, y_m$，权重分别为 $b_1, b_2, \dots, b_m$。

若一个矩形的四条边均位于给定的直线上，则称该矩形为“好矩形”。定义一个好矩形的代价为其四条边代价之和。其中，一条边的代价等于其长度与该边所在直线权重的乘积。

求代价不超过 $c$ 的好矩形的最大面积。注意，矩形的长和宽可以为零，因此答案总是存在的。

你需要回答 $T$ 个关于不同 $c$ 的查询。

输入格式

第一行包含三个整数 $n, m$ ($2 \le n, m \le 5\,000$) 和 $T$ ($1 \le T \le 100$)。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_1 < x_2 < \dots < x_n \le 10^5$)。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$)。

第四行包含 $m$ 个整数 $y_1, y_2, \dots, y_m$ ($1 \le y_1 < y_2 < \dots < y_m \le 10^5$)。

第五行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^7$)。

接下来的 $T$ 行，每行包含一个整数 $c$ ($1 \le c \le 4 \times 10^{12}$)，表示一个查询。

输出格式

对于每个查询，输出一行表示答案。

样例

样例输入 1

3 4 20
1 3 4
3 1 2
1 3 4 7
4 2 1 2
1
5
6
7
9
10
11
12
15
16
17
22
23
28
30
35
43
47
49
57

样例输出 1

0
0
1
1
1
2
2
3
3
4
4
6
6
9
9
12
12
12
18
18