Ruby Hoshino likes to travel on a 2D plane. She is always at integer coordinates, and each step she takes is either $+1$ or $-1$ in either the $x$ or $y$ coordinate.

For $N$ $(N \ge 1)$ integer points $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ on a 2D plane, we define a tour as the process where Ruby Hoshino starts at $(X_1, Y_1)$, visits $(X_2, Y_2), (X_3, Y_3), \dots, (X_N, Y_N)$ in order, and returns to $(X_1, Y_1)$. The minimum number of steps required for Ruby Hoshino to complete this tour is called the excitement value of the tour.

Ruby Hoshino now wants to perform a tour. She first selects $n$ integer points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ on the 2D plane and prepares to insert some additional points between them to determine the points she will visit in her next tour.

She then finds $m$ integer points $(x'_1, y'_1), (x'_2, y'_2), \dots, (x'_m, y'_m)$ on the 2D plane. Each integer point $(x'_j, y'_j)$ has an associated profit $w_j$ (which may be negative). She can choose one of the original $n$ points $(x_i, y_i)$ and insert $(x'_j, y'_j)$ after $(x_i, y_i)$. Of course, she can also choose not to insert any point.

To keep the tour from becoming too complex, she stipulates that at most one integer point can be inserted after each $(x_i, y_i)$.

Now, for each $k=1, 2, \dots, n$, she wants to know the maximum possible value of the sum of the excitement value of the next tour and the total profit of the chosen inserted points after exactly $k$ points are inserted.

Input

The first line contains two positive integers $n, m$.

The next $n$ lines each contain two integers $x_i, y_i$.

The next $m$ lines each contain three integers $x'_j, y'_j, w_j$.

Output

A single line containing $n$ integers, representing the answers for $k=1, 2, \dots, n$.

Examples

Input 1

3 4
1 1
2 2
4 3
2 3 0
5 4 -3
6 6 2
7 9 1

Output 1

35 47 48

Note 1

One optimal solution for choosing $1$ point changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3)$, with an excitement value of $34$ and a profit of $1$, totaling $35$.

One optimal solution for choosing $2$ points changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3), (6, 6)$, with an excitement value of $44$ and a profit of $3$, totaling $47$.

One optimal solution for choosing $3$ points changes the tour to $(1, 1), (7, 9), (2, 2), (5, 4), (4, 3), (6, 6)$, with an excitement value of $48$ and a profit of $0$, totaling $48$.

Input 2

3 4
0 4
5 1
3 4
4 3 -1
3 1 0
0 1 5
2 2 -5

Output 2

27 33 32

Note 2

One optimal solution for choosing $1$ point is $(0, 4), (5, 1), (3, 4), (0, 1)$.

One optimal solution for choosing $2$ points is $(0, 4), (5, 1), (0, 1), (3, 4), (3, 1)$.

One optimal solution for choosing $3$ points is $(0, 4), (4, 3), (5, 1), (0, 1), (3, 4), (3, 1)$.

Subtasks

• For $15\%$ of the data, $m \le 10$.
• For $30\%$ of the data, $m \le 200$.
• For $40\%$ of the data, $m \le 600$.
• For $60\%$ of the data, $m \le 10^3$.
• For $100\%$ of the data, $1 \le n \le m \le 10^5$, $|x_i|,|y_i|,|x'_j|,|y'_j|,|w_j| \le 10^8$.