A2559 | 千山鸟飞绝

话说有一天 doyouloveme 和 vfleaking 到山里玩。谁知 doyouloveme 刚刚进山，所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking 顿时膜拜不已。

这时鸟王用鸟语说道：「!@#\$%…?」，安抚了一下众鸟的情绪。鸟王生性好斗，作出了一个决定：要排鸟布阵把刚才吓到它们的人类赶出山去。

每只鸟都有一个编号，都有一个威武值。每秒钟鸟王都会发一个命令，编号为 $v$ 的鸟飞到 $(x,y)$ 去（坐标系原点是山顶，坐标单位为鸟爪）。鸟飞得很快，一秒之内就飞到了，可以看作是瞬间移动。如果编号为 $v$ 的鸟和编号为 $u$ 的鸟某一时刻处在同一位置，它们就会互相鼓励，增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值，团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置，则士气值和团结值都为 $0$。要注意自己不能鼓励自己，计算士气值和团结值时不能算上自己。

$t$ 秒钟后，doyouloveme 目测出了现在每只鸟的战斗力，于是感叹了一句：「不妙，我们得走了。」

正所谓团结的鸟儿一个顶俩，所以 doyouloveme 这样描述战斗力：一只鸟战斗力值等于它在 $0$ 到 $t$ 秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。

vfleaking 很想知道现在每只鸟的战斗力，但是他当然不会啦，于是他把这个任务交给了你来完成。

第一行一个整数 $n$，代表鸟的只数。（鸟王那家伙你可以完全忽视掉）

接下来 $n$ 行，每行三个整数 $w,x,y$ 描述每只鸟的威武值和初始坐标。第 $i+1$ 行描述编号为i的鸟。

接下来一行有一个整数 $t$，代表经过时间 $t$ 秒。

接下来 $t$ 行，每行三个整数 $v,x,y$ 描述鸟王每秒的命令。

一共 $n$ 行，每行一个数，代表每只鸟的战斗力。