Problem Description

One day, doyouloveme and vfleaking went to the mountains to play. As soon as doyouloveme entered the mountains, all the birds were startled by his divine aura and flew away. vfleaking was in awe.

The bird king then spoke in bird language: "!@#\$%…?", calming the birds' emotions. The bird king, being naturally combative, made a decision: to arrange the birds in a formation to drive the humans out of the mountains.

Each bird has a number and a valor value. Every second, the bird king issues an order for the bird numbered $v$ to fly to $(x,y)$ (the coordinate system's origin is the mountain peak, with the unit being bird claws). Birds fly very fast, reaching their destination within a second, which can be considered as teleportation. If a bird numbered $v$ and a bird numbered $u$ are at the same position at any moment, they will encourage each other, increasing their morale and unity values. A bird's morale value is equal to the highest valor value among the birds at the same position as it at that moment, and its unity value is equal to the number of birds at the same position. If no birds are at the same position as it at any moment, both the morale and unity values are $0$. Note that a bird cannot encourage itself; it should not be included when calculating morale and unity values.

After $t$ seconds, doyouloveme estimated the combat power of each bird and exclaimed, "This is not good, we have to leave."

As the saying goes, a united bird is worth two, so doyouloveme described the combat power as follows: A bird's combat power value is the product of the maximum morale value and the maximum unity value it had from $0$ to $t$ seconds. Note that it is the product of the maximum values, not the maximum product.

vfleaking wants to know the combat power of each bird now, but he certainly doesn't know how, so he assigns this task to you.

Input Format

The first line contains an integer $n$, representing the number of birds. (You can completely ignore the bird king)

The next $n$ lines, each containing three integers $w, x, y$, describe the valor value and initial coordinates of each bird. The $i+1$-th line describes the bird numbered $i$.

The next line contains an integer $t$, representing the time elapsed in seconds.

The next $t$ lines, each containing three integers $v, x, y$, describe the bird king's commands every second.

Output Format

There are $n$ lines in total, each containing a number representing the combat power of each bird.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
4
6
8
8

Input Sample #2

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

Output Sample #2

1890039364
3780078728
3780078728
3607265878
3412443954

Notes/Hints

For $100\%$ of the data, $1 \leq n \leq 30000$, $0 \leq t \leq 300000$, coordinates are integers within $[-2^{31}, 2^{31})$, and the valor value is a non-negative integer not exceeding $2^{31} - 1$.

见题面 Input 部分

见题面 Output 部分