Go 2

CEOI 2024 첫날 전날 저녁, Křemílek과 Vochomůrka는 방에서 내일 일을 걱정하며 앉아 있다. 시간을 보내려고 둘은 바둑을 두기로 했다. 그런데 바둑판이 없다. 다행히 Křemílek은 주머니에 성냥갑을 늘 넣고 다니고, Vochomůrka는 배낭에 무한한 격자를 넣고 다닌다. 그래서 둘은 Go 2를 둘 수 있다.

Go 2는 바둑과 두 가지가 다르다. 판과 규칙이다.

Go 2는 정사각형 격자 위에서 진행된다. 플레이어는 번갈아 가며 격자에 성냥을 놓는다. 성냥은 두 정사각형 사이에 있는 어떤 변에든 놓을 수 있다. 성냥을 놓아서 닫힌 영역이 생기면, 그 성냥을 놓은 플레이어는 닫힌 영역의 넓이만큼 점수를 얻고, 그 성냥은 격자에서 제거된다. 닫힌 영역이 생기지 않으면 점수는 없고 성냥은 격자에 그대로 남는다. 이전에 성냥을 놓았던 위치에는, 그 성냥이 이미 제거되었더라도 다시 놓을 수 없다.

첫 줄에 놓은 성냥의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 두 정수 $x_i$, $y_i$와 문자 $c_i$가 공백으로 구분되어 주어진다. 각 교점은 좌표 $x$, $y$로 나타낸다. $c$가 x이면 성냥은 $(x, y)$와 $(x + 1, y)$를 잇는 변에 놓인다. $c$가 y이면 성냥은 $(x, y)$와 $(x, y + 1)$을 잇는 변에 놓인다.

$N$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 성냥이 얻는 점수 $s_i$를 한 개의 수로 출력한다.

• $1 \le N \le 3 \cdot 10^5$
• 모든 $i$ ($1 \le i \le N$)에 대해 $0 \le x_i, y_i \le 10^8$
• 모든 $i$ ($1 \le i \le N$)에 대해 $0 \le s_i \le 10^8$