問題文

二次元平面上に R 個の赤い点、G 個の緑の点、B 個の青い点があります。

i 番目の赤い点は (RX_i,RY_i) にあります。

i 番目の緑の点は (GX_i,GY_i) にあります。

i 番目の青い点は (BX_i,BY_i) にあります。

複数の点が同じ座標にある可能性もあります。

関数 \text{dist},\text{tri} を以下のように定義します。

• \text{dist}((x_1,y_1),(x_2,y_2))=|x_1-x_2|+|y_1-y_2|
• \text{tri}(r,g,b)=\text{dist}((RX_r,RY_r),(GX_g,GY_g))+\text{dist}((GX_g,GY_g),(BX_b,BY_b))+\text{dist}((BX_b,BY_b),(RX_r,RY_r))

Q 個のクエリを処理してください。i 番目のクエリでは整数の組 (x_i,y_i,z_i) が与えられるので、以下の値を求めてください。

• 以下の条件をすべて満たす整数の組 (s,t,u) についての \text{tri}(s,t,u) の最大値
  • x_i=-1 なら 1\leq s\leq R 、x_i\neq -1 なら s=x_i
  • y_i=-1 なら 1\leq t\leq G 、y_i\neq -1 なら t=y_i
  • z_i=-1 なら 1\leq u\leq B 、z_i\neq -1 なら u=z_i

制約

• 1\leq R,G,B
• R+G+B\leq 200000
• 0\leq RX_i,RY_i,GX_i,GY_i,BX_i,BY_i\leq 10^9
• 1\leq Q\leq 200000
• 1\leq x_i\leq R または x_i=-1
• 1\leq y_i\leq G または y_i=-1
• 1\leq z_i\leq B または z_i=-1
• 入力はすべて整数

入力例 1

4 2 2
2 0
2 5
0 4
0 1
1 3
0 0
1 7
0 0
7
1 2 2
1 -1 2
3 -1 -1
-1 -1 -1
-1 2 -1
-1 2 2
4 2 2

出力例 1

4
10
16
18
18
14
2

• 2 番目のクエリについて、\text{tri}(1,1,2) が最大です。
• 3 番目のクエリについて、\text{tri}(3,2,1) が最大です。
• 4 番目のクエリについて、\text{tri}(2,2,1) が最大です。
• 5 番目のクエリについて、\text{tri}(2,2,1) が最大です。