Description

One day, doyouloveme and vfleaking went to play in the mountains. As soon as doyouloveme entered, all the birds were startled by his "shen niu" (shen niu, divine-cow, slang for an awesome person) aura and flew away. vfleaking immediately bowed in awe.

Then the bird king said in birdspeak: 「!@#$%…?」, calming the flock. Being naturally combative, the bird king made a decision: line up the birds in formation to drive the humans who had just scared them out of the mountains.

Each bird has an ID and a might value. Every second, the bird king issues a command: the bird with ID $v$ flies to $(x, y)$ (the origin of the coordinate system is the mountain peak, and the unit of length is a bird claw). Birds fly very fast and arrive within the same second; you can think of it as teleportation. If at any moment the bird with ID $v$ and the bird with ID $u$ are at the same position, they encourage each other, increasing their morale value and unity value. A bird’s morale value at that moment is the maximum might value among the birds at the same position as it at that moment, and its unity value is the number of birds at the same position as it at that moment. If at every moment no bird is at the same position as it, then both the morale value and the unity value are $0$. Note that a bird cannot encourage itself; when computing morale and unity, do not include itself.

After $t$ seconds, doyouloveme eyeballed the current combat power of each bird and sighed, “Not good, we have to go.”

As the saying goes, united birds count for two, so doyouloveme describes combat power like this: a bird’s combat power equals the product of its maximum morale value over seconds $0$ to $t$ and its maximum unity value over seconds $0$ to $t$. Note: it is not the maximum of the product, but the product of the maxima.

vfleaking wants to know the combat power of every bird, but of course he can’t compute it, so he’s handed the task to you.

Input Format

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

The next $n$ lines each contain three integers $w, x, y$, describing each bird’s might value and initial coordinates. Line $i + 1$ describes the bird with ID $i$.

The next line contains an integer $t$, the number of seconds that have elapsed.

The next $t$ lines each contain three integers $v, x, y$, describing the bird king’s command for each second.

Output Format

Output $n$ lines. Each line contains one number: the combat power of the corresponding bird.

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

Hint

Constraints:

• For $100\%$ of the testdata, $1 \le n \le 30000$, $0 \le t \le 300000$. Coordinates are integers and lie in $[-2^{31}, 2^{31})$.
• Might values are non-negative integers not exceeding $2^{31} - 1$.

Translated by ChatGPT 5