CF1292A NEKO's Maze Game

NEKO#ΦωΦ 刚刚给自己的电脑添加了一款新的迷宫游戏！ 这个游戏的主要谜题，是一个在 $2 \times n$ 的矩形网格上的迷宫。NEKO 的任务是操控女主角 Nekomimi 从格子 $(1, 1)$ 开始，移动到位于格子 $(2, n)$ 的大门处，并离开迷宫。女主角只能在有公共边的两个格子之间移动。 然而在游戏的某些时刻，有些格子会改变它们的状态：从正常的地面变成岩浆（禁止移动到岩浆格子上）或反过来（让该格子再次变得能够通行）。游戏刚开始时，每个格子都是正常的地面。 当直播过去了数个小时后，NEKO 才终于弄明白了，只有 $q$ 个这样的时刻：第 $i$ 个时刻会翻转格子 $(r_i, c_i)$ 的状态（从地面变成岩浆或相反）。 知道了这些后，NEKO 想问在每个时刻结束后，还是否有可能从格子 $(1, 1)$ 移动到格子 $(2, n)$，并且不经过岩浆格子。 虽然 NEKO 是一个硬核玩家兼热门主播，她还是没有足够的[脑力](https://www.bilibili.com/video/av5299187)去解答这些问题。你可以帮帮她吗？

无

无

We'll crack down the example test here: - After the first query, the girl still able to reach the goal. One of the shortest path ways should be: $ (1,1) \to (1,2) \to (1,3) \to (1,4) \to (1,5) \to (2,5) $ . - After the second query, it's impossible to move to the goal, since the farthest cell she could reach is $ (1, 3) $ . - After the fourth query, the $ (2, 3) $ is not blocked, but now all the $ 4 $ -th column is blocked, so she still can't reach the goal. - After the fifth query, the column barrier has been lifted, thus she can go to the final goal again.