配点 : 100 点
問題文
在二维平面上 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
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
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 个查询的答案。 对于第
入力例 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) 是最大值。