Rocket land

Problem Description

There are n rockets launched to a plain, which can be regarded as a two-dimensional plane.The rockets land in sequence.The $i$-th rocket will bring up smoke when it lands. The range is a circle with radius $r_i$.if the smoke cover the $j$-th rocket, it will cause the loss of $v_j$.How much loss does each rocket cause.

Input

The first line contains an integer T$(1 \leq T \leq 5)$representing the number of test cases. For each test case, the first line contains an integer n$(1 \leq n \leq 2*10^5)$ representing the number of the rockets. the next $n$ line followed. the $i-th$ line contains the coordinates of the $i-th$ rocket $x_i,y_i$$(-10^9 \leq x_i,y_i \leq 10^9)$, the loss when it is covered $v_i$$(1 \leq v_i \leq 10^9)$, and the range of smoke $r_i$ $(0 \leq r_i \leq 10^9)$. It is guaranteed that there are no more than 1 testcases with $n>10^5$ The rocket may land at the same coordinates all test cases create by randomly

Output

For each test case, print $n$ line representing the loss caused by $i$-th rocket.

Sample Input

1

5

1 1 1 3

2 2 2 1

3 3 4 2

4 4 8 2

5 5 16 4

Sample Output

1

2

6

12

28

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）