题目描述

Blue-edged Shot is forbidden from playing Genshin Impact by LeavingZ, so she turned to Go game.

A game of Go involves two players, one playing with Black stones and the other with White stones. Two players take turns making moves, with the Black stones going first. The Go board is composed of a grid of $19\times 19$ intersections, and we use $(x,y)$ to represent the intersection at the $x$-th row and $y$-th column. The stones are placed on the intersections. The top left corner is $(1,1)$, while the bottom right corner is $(19,19)$.

The intersections $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent if and only if $|x_1-x_2| + |y_1-y_2| = 1$. Adjacent intersections with stones of the same color belong to the same group of stones. The number of liberties for a stone is equal to the number of adjacent intersections to the stone's intersection that do not have any stones on them. The liberties of a group of stones equal the sum of the liberties of all the stones belonging to that group. A group of stones with zero liberties is considered dead and must be removed from the board.

Note that after Black plays, priority is given to removing any dead White stones, and then recalculating the liberties for Black stones. This is because there might be situations where, after Black plays, both Black and White stones have zero liberties, but removing the dead White stones increases the liberties for Black stones. As for White, process the stones similarly. After White plays, priority is given to removing any dead Black stones, and then recalculating the liberties for White stones.

Now there is a game of Go, starting with an empty board, and a total of $m$ moves have been made by both players. Given the positions where each stone is placed, output after each move, how many Black and White stones are removed respectively causing by this move. Obviously, black stones are played on odd-numbered moves, and white stones are played on even-numbered moves. It's guaranteed that stones are placed on empty intersections. Note that stones can be placed on $\textbf{any}$ intersections that do not have stones on them at the moment, regardless of violating the Go rules in real life.

输入格式

Input $m$ ($1 \le m \le 5\times 10^5)$ lines, the $i$-th line contains two integers $x_i,y_i$ ($1 \le x_i,y_i \le 19$), representing the $i$-th move puts stone on $(x_i,y_i)$.

It's guaranteed that stones are placed on intersections that do not have stones on them at the moment.

输出格式

Output $m$ lines, each line contains two integers. The first integer in the $i$-th line represents the number of Black stones removed after the $i$-th move, while the second for White stones.

题目大意

弹窗内容

LeavingZ：你被禁止玩《原神》。

题目描述

蓝边铅球因LeavingZ的禁止而无法玩《原神》，所以她转向了围棋。

围棋游戏由两名玩家进行，一方使用黑子，另一方使用白子。两名玩家轮流下子，黑子先行。围棋棋盘由$19\times 19$的交叉点组成，我们用$(x,y)$表示第$x$行第$y$列的交叉点。棋子放置在交叉点上。左上角为$(1,1)$，右下角为$(19,19)$。

如果$|x_1-x_2| + |y_1-y_2| = 1$，那么交叉点$(x_1,y_1)$和$(x_2,y_2)$是相邻的。相邻的交叉点上放置相同颜色的棋子属于同一组棋子。一个棋子的“气”数等于该棋子所在交叉点的相邻交叉点上没有棋子的个数。一组棋子的“气”数等于该组棋子中所有棋子的“气”数之和。一组棋子如果“气”数为零，则被视为“死棋”并且必须从棋盘上移除。

注意，在黑子落子后，优先移除任何死掉的白子，然后重新计算黑子的“气”数。这是因为可能出现这样的情况：黑子落子后，黑白两方的棋子都没有“气”，但移除死掉的白子会增加黑子的“气”。白子落子的处理方式类似。在白子落子后，优先移除任何死掉的黑子，然后重新计算白子的“气”数。

现在有一局围棋，从空棋盘开始，总共进行了$m$步。给定每步棋子的放置位置，请输出每步棋子落子后，分别有多少颗黑子和白子被移除。显然，黑子在奇数步落子，白子在偶数步落子。保证棋子放置在空的交叉点上。注意，棋子可以放置在$\textbf{任意}$当前没有棋子的交叉点上，无论是否违反了现实中的围棋规则$^{(1)}$。

注释：

• (2):译者补充

输入格式

输入包含 $m$ 行（$1 \le m \le 5\times 10^5$），第 $i$ 行包含两个整数 $x_i, y_i$ （$1 \le x_i, y_i \le 19$），表示第 $i$ 步在 $(x_i, y_i)$ 位置放置棋子。

保证棋子放置在当前没有棋子的交叉点上。

输出格式

输出包含 $m$ 行，每行包含两个整数。第 $i$ 行的第一个整数表示第 $i$ 步后被移除的黑子数量，第二个整数表示被移除的白子数量。

翻译者：Immunoglobules

8
2 1
1 1
1 2
2 2
1 1
1 3
2 3
3 1

0 0
0 0
0 1
0 0
0 0
0 0
0 0
3 0

提示