#P7878. Rocket land

Rocket land

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 ii-th rocket will bring up smoke when it lands. The range is a circle with radius rir_i.if the smoke cover the jj-th rocket, it will cause the loss of vjv_j.How much loss does each rocket cause.

Input

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

Output

For each test case, print nn line representing the loss caused by ii-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)