#P18160. Cycle Game

Cycle Game

Cycle Game

有一块 n×mn\times m 的白色棋盘。Jeroen 每回合把一个格子染黑。两个格子若共边则相邻。格子与相邻关系构成一个平面图。当黑色格子中形成一个内部非空的简单环时,游戏结束。

把图的边画成连接格子中心的直线段;一个不在环上的格子,若其中心位于环的边所围成的多边形内部,就称它在环的内部。

环内格点可以是白色或黑色;2×2黑方块的普通四边环内部没有格点,因此允许。

Jeroen 已经计划好了 kk 步(互不相同的位置 (ri,ci)(r_i,c_i))。若某一步会结束游戏,他就不下这一步(棋盘保持原样)。对每一步,判断它是否会被实际执行。

输入格式

第一行三个整数 n,m,kn,m,k(1≤n⋅m≤3⋅1051\le n\cdot m\le 3\cdot10^5,1≤k≤n⋅m1\le k\le n\cdot m)。

接下来 kk 行,每行两个整数 ri,cir_i,c_i。

输出格式

输出一个长度为 kk 的 0/1 串:第 ii 位为 1 表示第 ii 步会被执行,为 0 表示该步会结束游戏、不会被执行。

样例 1

输入:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

输出:

1111111

样例 2

输入:

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

输出:

11111110