Background

During a training lecture in 2022, a problem appeared in the slides whose input variables were strictly ordered by the initials of MLE’s real name. MLE wanted to use the initials of vectorwyx as the input variables in their own problem, and thus this problem was created.

Unfortunately, vectorwyx has now retired. Everyone has their own dreams, and each shines in their own way.

Problem Description

Please read the Constraints of this problem carefully.

You are given an $n \times n$ square grid with $n$ rows and $n$ columns. Initially, all cells are red. There are $n$ queries. Each query recolors an entire row or an entire column to red or white. After each query, output the perimeter of all red cells. The queries are not independent.

Input Format

The first line contains a positive integer $n$.

Each of the next $n$ lines contains three positive integers $w, y, x$. $w$ indicates the color: $w=1$ means recolor to red, and $w=0$ means recolor to white. $y$ indicates row or column: $y=1$ means recolor the entire $x$-th row, and $y=0$ means recolor the entire $x$-th column.

Output Format

There are $n$ lines. Each line contains one integer, representing the perimeter of the red region after each modification.

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

28
32
36
36
32

Hint

Sample Explanation

Sample image explanation.

Constraints

For $100\%$ of the data, $3\leq n \leq 10^6$, $1<x<n$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{\textsf{\#}} & \bm{{n\le}} & \textbf{\textsf{Special Properties}} & \textbf{\textsf{\#}} & \bm{{n\le}} & \textbf{\textsf{Special Properties}}\cr\hline 1 & 5 & - & 11 & 10^5 & - \cr\hline 2 & 100 & - & 12 & 10^5 & - \cr\hline 3 & 100 & - & 13 & 10^5 & - \cr\hline 4 & 2000 & \textbf{A} & 14 & 10^5 & - \cr\hline 5 & 2000 & \textbf{B} & 15 & 10^6 & - \cr\hline 6 & 2000 & - & 16 & 10^6 & - \cr\hline 7 & 10^5 & \textbf{AB} & 17 & 10^6 & - \cr\hline 8 & 10^5 & \textbf{B} & 18 & 10^6 & - \cr\hline 9 & 10^5 & \textbf{A} & 19 & 10^6 & - \cr\hline 10 & 10^5 & - & 20 & 10^6 & - \cr\hline \end{array}$$

• Special Property $\bf A$: $w=0$ is guaranteed.
• Special Property $\bf B$: $y=0$ is guaranteed.

Translated by ChatGPT 5