Easy Math Problem

题目描述

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

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

输入格式

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

输出格式

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

样例输入 #1

3
1 1 2
1 3 3
1 2 4

样例输出 #1

8
20
26

样例输入 #2

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

样例输出 #2

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!$ 的结果。

数据范围

对于 $10\%$ 的数据，保证 $n=x=y=1,z \le 10$。

对于 $30\%$ 的数据，保证 $1 \le n \le 10$，$1 \le x, y, z \le 10$。

对于 $50\%$ 的数据，保证 $1 \le n \le 10^3$，$1 \le x, y\le 10^3$，$z \le 10^9$。

对于 $90\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le x, y\le 10^3$，$z \le 10^9$

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le x,y,z\le 10^9$