AT_pakencamp_2024_day3_1_f RGB Triangle

二次元平面上に $ 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 $

入力は以下の形式で標準入力から与えられる。 > $ R $ $ G $ $ B $ $ RX_1 $ $ RY_1 $ $ RX_2 $ $ RY_2 $ $ \vdots $ $ RX_R $ $ RY_R $ $ GX_1 $ $ GY_1 $ $ GX_2 $ $ GY_2 $ $ \vdots $ $ GX_G $ $ GY_G $ $ BX_1 $ $ BY_1 $ $ BX_2 $ $ BY_2 $ $ \vdots $ $ BX_B $ $ BY_B $ $ Q $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ $ \vdots $ $ x_Q $ $ y_Q $ $ z_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 - $ 2 $ 番目のクエリについて、 $ \text{tri}(1,1,2) $ が最大です。 - $ 3 $ 番目のクエリについて、 $ \text{tri}(3,2,1) $ が最大です。 - $ 4 $ 番目のクエリについて、 $ \text{tri}(2,2,1) $ が最大です。 - $ 5 $ 番目のクエリについて、 $ \text{tri}(2,2,1) $ が最大です。 ### Constraints - $ 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 $ - 入力はすべて整数