题目描述

话说有一天 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$ 行，每行一个数，代表每只鸟的战斗力。

5
1 1 1
3 1 2
4 4 4
2 0 1
2 2 3
5
1 1 2
2 4 4
2 4 3
3 0 1
5 0 1

3
4
6
8
8

样例说明

首先 $5$ 只鸟的位置为 $(1,1)$，$(1,2)$，$(4,4)$，$(0,1)$，$(2,3)$，士气和团结值都是 $0$。 鸟 $1$ 飞到了 $(1,2)$，于是鸟 $1$ 和鸟 $2$ 互相鼓励，鸟 $1$ 士气变为 $3$，鸟 $2$ 士气变为 $1$。鸟 $1$ 鸟 $2$ 的团结值变为 $1$。 然后鸟 $2$ 飞到 $(4,4)$，与鸟 $3$ 互相鼓励，鸟 $2$ 士气变为 $4$，鸟 $3$ 士气变为 $3$。鸟 $2$ 与鸟 $3$ 的团结值变为 $1$。 鸟 $2$ 然后飞到了 $(4,3)$，一个没有鸟的地方。于是士气和团结值都变为了 $0$。 接下来鸟 $3$ 和鸟 $5$ 都飞到了鸟 $4$ 的位置，于是三只鸟互相鼓励，鸟 $4$、鸟 $5$ 士气变为 $4$，鸟 $3$ 士气仍为 $3$。鸟 $3$、鸟 $4$、鸟 $5$ 的团结值都变为 $2$。

于是大家的战斗力：

1. 鸟 $1$：$3 \times 1 = 3$
2. 鸟 $2$：$4 \times 1 = 4$
3. 鸟 $3$：$3 \times 2 = 6$
4. 鸟 $4$：$4 \times 2 = 8$
5. 鸟 $5$：$4 \times 2 = 8$

数据规模与约定

$1 \le n \le 3 \times 10^4,~0 \le t \le 3 \times 10^5$，坐标范围为整数，且不超过 $-2^{31} \sim 2^{31} - 1$，威武值为不超过 $2^{31} - 1$ 的非负整数。

题目来源

湖北省队互测