Go 2

On the evening before the first day of CEOI 2024, Křemílek and Vochomůrka sit in their room, nervous about what comes next. To pass the time, they decide to play a game of Go. They have no Go board. Luckily, Křemílek always carries a matchbox in his pocket, and Vochomůrka has an infinite grid in his backpack, so they can play Go 2.

Go 2 differs from Go in two ways: the board and the rules.

Go 2 is played on a square grid. Players take turns placing matches on the grid. A match may be placed on any edge between two squares. If placing a match creates an enclosed area, the player who placed it receives points equal to the area of the enclosed space, and the match is removed. Otherwise, the player receives no points and the match stays on the grid. A match may not be placed at a position where a match was placed before, even if that match has since been removed.

The first line contains the integer $N$, the number of matches placed. The next $N$ lines each contain two numbers $x_i$ and $y_i$ and a character $c_i$, separated by spaces. Each corner is identified by its coordinates $x$ and $y$. If $c$ is x, the match is placed on the edge between $(x, y)$ and $(x + 1, y)$. If $c$ is y, the match is placed on the edge between $(x, y)$ and $(x, y + 1)$.

Output $N$ lines. The $i$-th line contains a single number $s_i$, the number of points the $i$-th match is worth.

• $1 \le N \le 3 \cdot 10^5$
• $0 \le x_i, y_i \le 10^8$ for each $i$ such that $1 \le i \le N$
• $0 \le s_i \le 10^8$ for each $i$ such that $1 \le i \le N$