题目描述

定义由若干个边长为 $1$ 的正方体方块搭成的立体图形的「侧面积」为：对于所有方块，若它的前、后、左或右面没有紧贴着另一个方块，则该面计入侧面积。

维护长宽均无限的矩形地面，地面被划分为若干个边长为 $1$ 的格子。$n$ 次操作，每次选择一个格子 $(x_i,y_i)$ 在该位置向上堆叠 $z_i$ 个边长为 $1$ 的正方体方块。每次操作后，输出整个立体图形的「侧面积」。

输入格式

• 第一行输入一个整数 $n$。
• 接下来 $n$ 行，每行输入三个整数 $x_i,y_i,z_i$。

输出格式

• 输出共 $n$ 行，每行输出一个整数。表示每次操作后立体图形的「侧面积」。

3
1 1 2
1 3 3
1 2 4

8
20
26

6
1 2 1
2 1 4
2 3 8
3 2 6
2 2 2
2 2 11

4
20
52
76
70
90

说明/提示

样例 1 解释

如图所示，建立空间直角坐标系。其 $x$-轴向南、$y$-轴向东、$z$-轴向上。限于技术原因，此处仅给出斜二测画法的立体图形，请读者自行脑补立体图形其他角度的模样。图中绿色部分即为立体图形的侧面。

第一次操作后，在 $(1,1)$ 位置放入了一个高度为 $2$ 的立体图形，侧面积为 $8$。

第二次操作后，在 $(1,3)$ 位置放入了一个高度为 $3$ 的立体图形，侧面积为 $12$。由于两个立体图形没有接触，因此可以直接加上第一次放上的立体图形的侧面积，总侧面积为 $20$。

第三次操作后，在 $(1,2)$ 位置放入了一个高度为 $4$ 的立体图形。由于某些面发生了接触，这些面对应的面积不计入侧面积的计算范围内。容易发现，总侧面积为 $26$。

---

再强调下，每次堆叠操作是在对应位置上再加上 $z_i$ 个方块。例如下图，是先执行了 $\verb!2 2 1!$，再执行了 $\verb!2 2 3!$ 的结果。

附加样例

• 样例 $3$ 见下发文件中的 $\textbf{\textit{two3.in/two3.ans}}$。该样例满足测试点 $4$ 的限制。
• 样例 $4$ 见下发文件中的 $\textbf{\textit{two4.in/two4.ans}}$。该样例满足测试点 $7$ 的限制。
• 样例 $5$ 见下发文件中的 $\textbf{\textit{two5.in/two5.ans}}$。该样例满足测试点 $10$ 的限制。
• 样例 $6$ 见下发文件中的 $\textbf{\textit{two6.in/two6.ans}}$。该样例满足测试点 $13$ 的限制。
• 样例 $7$ 见下发文件中的 $\textbf{\textit{two7.in/two7.ans}}$。该样例满足测试点 $20$ 的限制。

输入样例 #3

30
8 3 2722714025402
6 4 7239796621134
4 10 246745499807
10 1 6238032055220
7 1 4968458023833
8 3 3223350534067
5 3 1536069032508
8 2 856482907230
1 2 108690907864
2 5 4889785290407
10 5 5964265044540
6 7 3697282650718
2 10 895396936830
8 6 6777172093321
5 1 9794415869615
6 2 1917360184832
3 7 4613327376776
7 9 5338689056214
6 7 6802685656814
7 2 7644916821347
9 1 932019419609
4 2 9373289396689
4 8 141840664717
1 6 9907451705231
4 9 6953871539509
5 1 2352620849625
3 7 2654301422961
3 2 3050819722475
1 7 6480595605862
8 2 7860606459416

输出样例 #3

10890856101608
39850042586144
40837024585372
65789152806252
85662984901584
98556387037852
104700663167884
106413628982344
106848392613800
126407533775428
150264593953588
165053724556460
168635312303780
195744000677064
234921664155524
242591104894852
261044414401956
282399170626812
309609913254068
324704978307666
326569017146884
364062174733640
364629537392508
404259344213432
431297658042420
440708141440920
451325347132764
457426986577714
470388177789438
478074572494390

数据范围

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c||c|c|c|c|c|} \hline \textbf{\textsf{\#}} & \bm{{n \le }} & \bm{{x,y \le}} & \bm{{z \le}} & \textbf{\textsf{特殊性质}} & \textbf{\textsf{\#}} & \bm{{n \le }} & \bm{{x,y \le}} & \bm{{z \le}} & \textbf{\textsf{特殊性质}} \cr\hline 1 & 1 & 1 & 10 & - & 14 & 10^3 & 10^3 & 10^3 & - \cr\hline 2 & 2 & 5 & 10 & - & 15 & 10^3 & 10^3 & 10^9 & - \cr\hline 3 & 10 & 5 & 10 & - & 16 & 10^3 & 10^9 & 10^9 & - \cr\hline 4 & 100 & 100 & 100 & - & 17 & 10^5 & 10^9 & 10^9 & \textbf{AB} \cr\hline 5 & 10^3 & 10^3 & 10^3 & \textbf{AB} & 18 & 10^5 & 10^9 & 10^9 & \textbf{A} \cr\hline 6 & 10^3 & 10^3 & 10^9 & \textbf{AB} & 19 & 10^5 & 10^9 & 10^9 & \textbf{B} \cr\hline 7 & 10^3 & 10^9 & 10^9 & \textbf{AB} & 20 & 10^5 & 10^9 & 10^9 & - \cr\hline 8 & 10^3 & 10^3 & 10^3 & \textbf{A} & 21 & 2\times 10^5 & 10^9 & 10^9 & - \cr\hline 9 & 10^3 & 10^3 & 10^9 & \textbf{A} & 22 & 2\times 10^5 & 10^9 & 10^{12} & - \cr\hline 10 & 10^3 & 10^9 & 10^9 & \textbf{A} & 23 & 2\times 10^5 & 10^9 & 10^{13} & \textbf{A} \cr\hline 11 & 10^3 & 10^3 & 10^3 & \textbf{B} & 24 & 2\times 10^5 & 10^9 & 10^{13} & - \cr\hline 12 & 10^3 & 10^3 & 10^9 & \textbf{B} & 25 & 3\times 10^5 & 10^9 & 10^{13} & - \cr\hline 13 & 10^3 & 10^9 & 10^9 & \textbf{B} &&&&&\cr\hline \end{array}$$

• 特殊限制 $\bf A$：$\forall 1 \le i\le j \le n$，有 $x_i=x_j$。
• 特殊限制 $\bf B$：$\forall 1 \le i\le j \le n$，有 $(x_i,y_i) \ne (x_j,y_j)$。

对于 $100\%$ 的数据，保证 $1 \le n \le 3 \times 10^5$，$1 \le x,y \le 10^9$，$1\le z \le 10^{13}$。