You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

这是2024年IOI比赛的第一天前夕，Zky和Hlt在他们的房间里，对即将到来的比赛感到紧张。为了打发时间，他们决定玩一局围棋。不幸的是，他们俩都没带围棋盘。幸运的是，Zky总是随身携带火柴盒，而Hlt的背包里有一个无限网格，这意味着他们可以玩火柴棋！

顾名思义，火柴棋与围棋在两个主要方面有所不同：棋盘和规则。

火柴棋在一个正方形网格上进行。玩家轮流在网格上放置火柴。火柴可以放置在两个方格之间的任何边缘上。如果放置火柴创造了一个封闭区域，放置它的玩家将获得与封闭空间面积相等的分数，并且火柴被移除。否则，玩家不得分，火柴仍然留在网格上。禁止在之前放置过火柴的位置放置火柴，即使那个火柴已经被移除。

由于比赛前他们不想耗费脑力计算，Zky和Hlt希望你们帮助评估他们的游戏。你将收到他们游戏中放置的所有火柴的列表（按照他们玩的顺序排列）。对于每根火柴，你应该计算它获得的分数。

输入格式

第一行一个整数 $n$ 表示火柴的数目。

接下来 $n$ 行，每行两个整数 $x, y$ 和一个符号 $c$ 表示一根火柴。

如果 c='x',表示火柴放置在 (x,y)与(x+1,y)。 如果c='y',表示火柴放置在 (x,y)与(x,y+1)。

输出格式

输出 $n$ 行，对于每根火柴，输出他的分数。

4
0 0 x
0 0 y
1 0 y
0 1 x

0
0
0
1

放置完第四根火柴后，围成一个面积为1的图形。

数据范围

$1 \le n \le 3*10^5$ $0 \le x_i, y_i \le 10^8$

保证答案 $\le 10^8$

子任务1(25分): $n \le 3*10^4, x_i, y_i\le 10^4$

子任务2(25分): $x_i, y_i\le 10^4$

子任务3(25分): $n \le 3*10^4$

子任务4(25分): 没有额外限制