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.

1
5
1 1 1 3
2 2 2 1
3 3 4 2
4 4 8 2
5 5 16 4

1
2
6
12
28