Migrated from Lutece 3012 深海猎宝人

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

勇敢的小橘子，开着她的深海潜水艇来各个星球上的大海寻宝啦！ 她对于每片大海划定了一个 $n\times n\times n$ 体积的一个正方体区域，她的空间探索捕捞器每次可以将一个以自身为一个顶点，然后$a\times b\times c$ 大小的立方体区域内所有宝藏捕获，消耗 $a\times b\times c$ 的能量，这次捕捞的收益则为捕捞到的宝藏价值总和减去消耗的能量值（其中 $n,a,b,c$ 必须均为整数，防止区块刷新问题）。

她已经提前用次元雷达探索了整个划定区域的宝藏分布情况，然后准备了 $Q$ 个能量胶囊，每个能量胶囊能一次性提供 $v_i$ 的能量，由于她很想最大化探索收益，但这 $Q$ 个胶囊必须用完，所以她想知道如果第一次就一次性用完第 $i$ 个胶囊的能量的最大收益是多少，你能快速告诉她吗？

Input

第一行输入 $n,m,Q$，表示 $n\times n\times n$ 的划定区域，有 $m$ 个宝藏和 $Q$ 个能量胶囊。

接下来 $m$ 行，每行四个整数 $x,y,z,w$，表示在坐标 $(x,y,z)$ 处有价值 $w$ 的宝藏。

接下来 $Q$ 个数字 $v_i$ ，表示第 $i$ 个胶囊能提供的能量值。

Output

输出 $Q$ 个数字，表示第 $i$ 个胶囊的能量一次性用完可以获得的最大收益，如果这个胶囊没法使用，输出 $-1$。

Samples

5 2 5
1 1 4 1919810
5 1 4 6699
1 3 5 7 9

1919809
1919807
1926504
-1
1919801

50 3 5
1 2 3 123
33 44 45 12345
43 21 12 245
10 20 30 80 100

12335
12325
12315
12265
12245

Constraints

$1\leq n\leq 100, 1\leq m\leq 10^6, 1\leq x,y,z\leq n, 1\leq w\leq 10^5, 1 \leq Q\leq 10, 1\leq v_i\leq 100$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming