题目描述

话说有一天 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
1803632939 1051911108 963670239
296082233 384714041 782958792
1706221977 1051911108 963670239
1890039364 -1429456864 794782986
1152753107 1932597483 1442217530
10
3 -1429456864 794782986
2 -1429456864 794782986
4 -1429456864 794782986
4 2062723523 -411953943
5 -1429456864 794782986
4 1051911108 963670239
4 1051911108 963670239
1 1051911108 963670239
1 1051911108 963670239
5 -1429456864 794782986

1890039364
3780078728
3780078728
3607265878
3412443954

提示

对于 $100\%$ 的数据，$1≤n≤30000$，$0≤t≤300000$，坐标为整数，均在 $[-2^{31},2^{31})$ 内。

威武值为不超过 $2^{31}-1$ 的非负整数。