Background

Problem Description

Hoshino Rubii likes to wander on a 2D plane. She is always on integer grid points, and each step can only choose one of up, down, left, or right (that is, increase or decrease the $x$-coordinate or $y$-coordinate by $1$).

For $N$ $(N \ge 1)$ integer points $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ on the plane, we call the tour they describe a process where Hoshino Rubii starts from $(X_1, Y_1)$, visits $(X_2, Y_2), (X_3, Y_3), \dots, (X_N, Y_N)$ in order, and then returns to $(X_1, Y_1)$. The minimum number of steps Hoshino Rubii needs for a tour is called the tour’s excitement value.

Now Hoshino Rubii wants to take a tour. She first chooses $n$ integer points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ on the plane, and plans to insert some additional points among them to determine the sequence of points her next tour must pass through.

So she finds another $m$ integer points $(x'_1, y'_1), (x'_2, y'_2), \dots, (x'_m, y'_m)$ on the plane. Each point $(x'_j, y'_j)$ has a profit $w_j$ (possibly negative). She may choose one of the previous $n$ points $(x_i, y_i)$ and insert $(x'_j, y'_j)$ right after $(x_i, y_i)$. Of course, she may also choose not to insert it anywhere.

However, to avoid making the tour too complicated, she requires that after each $(x_i, y_i)$, at most one integer point can be inserted.

Now, for $k = 1, 2, \dots, n$, she wants to know: after inserting exactly $k$ points, what is the maximum possible value of the sum of the next tour’s excitement value and the total profit of the inserted points.

Input Format

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

The next $n$ lines: the $i$-th line contains two integers $x_i, y_i$.

The next $m$ lines: the $j$-th line contains three integers $x'_j, y'_j, w_j$.

Output Format

Output one line with $n$ integers, representing the answers for $k = 1, 2, \dots, n$.

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

35 47 48

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

27 33 32

Hint

Idea: Aleph1022, Solution: Aleph1022&zx2003, Code: Aleph1022, Data: Aleph1022

Sample Explanation #1

One optimal solution when choosing $1$ point changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3)$. The excitement value is $34$, and the profit is $1$, totaling $35$.

One optimal solution when choosing $2$ points changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3), (6, 6)$. The excitement value is $44$, and the profit is $3$, totaling $47$.

One optimal solution when choosing $3$ points changes the tour to $(1, 1), (7, 9), (2, 2), (5, 4), (4, 3), (6, 6)$. The excitement value is $48$, and the profit is $0$, totaling $48$.

Sample Explanation #2

One optimal plan when choosing $1$ point is $(0, 4), (5, 1), (3, 4), (0, 1)$.

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

One optimal plan when choosing $3$ points is $(0, 4), (4, 3), (5, 1), (0, 1), (3, 4), (3, 1)$.

Constraints

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

Translated by ChatGPT 5