Problem Description

Define the “lateral surface area” of a 3D shape built from some unit cubes (cubes with side length $1$) as follows: for every cube, if its front, back, left, or right face is not tightly adjacent to another cube, then that face is counted in the lateral surface area.

Maintain a rectangular ground plane with infinite length and width. The ground is divided into unit grid cells of side length $1$. There are $n$ operations. In each operation, choose a cell $(x_i, y_i)$ and stack $z_i$ unit cubes upward at that position. After each operation, output the “lateral surface area” of the whole 3D shape.

Input Format

• The first line contains an integer $n$.
• The next $n$ lines each contain three integers $x_i, y_i, z_i$.

Output Format

• Output $n$ lines in total, each line containing one integer, representing the “lateral surface area” of the 3D shape after each operation.

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

Hint

Explanation of Sample 1

As shown in the figure, set up a 3D Cartesian coordinate system. The $x$-axis points south, the $y$-axis points east, and the $z$-axis points upward. Due to technical limitations, only an oblique drawing is provided here; please imagine how the 3D shape looks from other angles. The green part in the figure is exactly the lateral surface of the 3D shape.

After the first operation, a shape of height $2$ is placed at position $(1, 1)$, and the lateral surface area is $8$.

After the second operation, a shape of height $3$ is placed at position $(1, 3)$, and the lateral surface area is $12$. Since the two shapes do not touch, we can directly add the lateral surface area of the first shape, so the total lateral surface area is $20$.

After the third operation, a shape of height $4$ is placed at position $(1, 2)$. Since some faces come into contact, the areas corresponding to those faces are not counted in the lateral surface area. It is easy to see that the total lateral surface area is $26$.

---

To emphasize again, each stacking operation adds another $z_i$ cubes on top of the existing cubes at that position. For example, the figure below shows the result of first executing $\verb!2 2 1!$ and then executing $\verb!2 2 3!$.

Additional Samples

• Sample $3$ can be found in the attached files $\textbf{\textit{two3.in/two3.ans}}$. This sample satisfies the limits of test point $4$.
• Sample $4$ can be found in the attached files $\textbf{\textit{two4.in/two4.ans}}$. This sample satisfies the limits of test point $7$.
• Sample $5$ can be found in the attached files $\textbf{\textit{two5.in/two5.ans}}$. This sample satisfies the limits of test point $10$.
• Sample $6$ can be found in the attached files $\textbf{\textit{two6.in/two6.ans}}$. This sample satisfies the limits of test point $13$.
• Sample $7$ can be found in the attached files $\textbf{\textit{two7.in/two7.ans}}$. This sample satisfies the limits of test point $20$.

Constraints

$$\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{Special property}} & \textbf{\textsf{\#}} & \bm{{n \le }} & \bm{{x,y \le}} & \bm{{z \le}} & \textbf{\textsf{Special property}} \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}$$

• Special constraint $\bf A$: $\forall 1 \le i\le j \le n$, we have $x_i = x_j$.
• Special constraint $\bf B$: $\forall 1 \le i\le j \le n$, we have $(x_i, y_i) \ne (x_j, y_j)$.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 3 \times 10^5$, $1 \le x, y \le 10^9$, and $1 \le z \le 10^{13}$.

Translated by ChatGPT 5