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.

Format

Input

The first line contains an integer $T(1≤T≤5)$representing the number of test cases.
For each test case, the first line contains an integer $n(1≤n≤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≤x_i,y_i≤10^9)$, the loss when it is covered $v_i(1≤v_i≤10^9)$, and the range of smoke $r_i (0≤r_i≤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.

Samples

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