星野露比喜欢在二维平面上巡游。她永远在整点上，并且每一步只可能从上下左右中选一个（即，将横坐标或纵坐标 $+1$ 或 $-1$）。

对于二维平面上 $N$ $(N \ge 1)$ 个整点 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$，我们称它们描述的一次巡游是星野露比从 $(X_1, Y_1)$ 出发，按顺序依次经过 $(X_2, Y_2), (X_3, Y_3), \dots, (X_N, Y_N)$ 并回到 $(X_1, Y_1)$ 的一个过程。我们将一次巡游中星野露比所需要的最小步数称为这次巡游的兴奋值。

星野露比现在想要进行一次巡游。她首先选定了二维平面上 $n$ 个整点 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，并准备在它们之间再插入一些点，来确定他下一次巡游所需要经过的点。

于是她又找到了二维平面上 $m$ 个整点 $(x'_1, y'_1), (x'_2, y'_2), \dots, (x'_m, y'_m)$。对于其中每个整点 $(x'_j, y'_j)$，其具有一个收益 $w_j$（可能为负）；他可以选择一个先前的 $n$ 个整点中的某一者 $(x_i, y_i)$，并将 $(x'_j, y'_j)$ 插入到 $(x_i, y_i)$ 之后。当然，她也可以选择不插入到任何位置。

但为了不让巡游变得太复杂，她规定每个 $(x_i, y_i)$ 之后只能插入至多一个整点。

现在，对于 $k=1,2,\dots,n$，他想知道恰好插入 $k$ 个点之后，下次巡游的兴奋值与选择插入的整点的总收益之和最大能达到多少。

输入格式

第一行，两个正整数 $n, m$。

以下 $n$ 行，其中第 $i$ 行两个整数 $x_i, y_i$。

以下 $m$ 行，其中第 $j$ 行三个整数 $x'_j, y'_j, w_j$。

输出格式

一行，$n$ 个整数，表示 $k=1,2,\dots,n$ 的答案。

样例数据

样例 1 输入

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

样例 1 输出

35 47 48

样例 1 解释

选择 $1$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (4, 3)$，兴奋值为 $34$，并具有 $1$ 的收益，共 $35$。

选择 $2$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (4, 3), (6, 6)$，兴奋值为 $44$，并具有 $3$ 的收益，共 $47$。

选择 $3$ 个点的一种最优解会将巡游变为 $(1, 1), (7, 9), (2, 2), (5, 4), (4, 3), (6, 6)$，兴奋值为 $48$，并具有 $0$ 的收益，共 $48$。

样例 2 输入

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

样例 2 输出

27 33 32

样例 2 解释

选择 $1$ 个点的一种最优方案为 $(0, 4), (5, 1), (3, 4), (0, 1)$。

选择 $2$ 个点的一种最优方案为 $(0, 4), (5, 1), (0, 1), (3, 4), (3, 1)$。

选择 $3$ 个点的一种最优方案为 $(0, 4), (4, 3), (5, 1), (0, 1), (3, 4), (3, 1)$。

子任务

Idea：alpha1022，Solution：alpha1022&zx2003，Code：alpha1022，Data：alpha1022

• 对于 $15\%$ 的数据，$m \le 10$。
• 对于 $30\%$ 的数据，$m \le 200$。
• 对于 $40\%$ 的数据，$m \le 600$。
• 对于 $60\%$ 的数据，$m \le 10^3$。
• 对于 $100\%$ 的数据，$1 \le n \le m \le 10^5$，$|x_i|,|y_i|,|x'_j|,|y'_j|,|w_j| \le 10^8$。