有一个 $n \times m$ 的白色方格棋盘。Jeroen 在这个网格上玩一个单人游戏。每一回合，他将一个方格涂成黑色。如果两个方格共享一条边，则称它们相邻。这些方格及其相邻关系构成了一个平面图。当形成一个具有非空内部的黑色方格简单环时，游戏结束。通过在方格中心之间用直线绘制图的边，我们得到了该平面图的一个绘图。如果一个不在环上的方格位于环的边作为线段所构成的多边形内部，则称该方格位于环的内部。Jeroen 希望在游戏结束时在棋盘上呈现出一幅漂亮的图案，因此他已经预先规划好了他要走的每一步。如果某一步会导致游戏结束，他将不会执行这一步。输入中给出了 $k$ 个不同的位置 $(r_i, c_i)$，即 Jeroen 计划走的每一步。

你的任务是判断对于每一手棋，它是否会导致游戏结束。输出一个长度为 $k$ 的位串，如果第 $i$ 手棋会被执行，则第 $i$ 位为 $1$；如果这一步会导致游戏结束（因此不会被执行），则第 $i$ 位为 $0$。

输入格式

输入的第一行包含三个整数 $n, m, k$ ($1 \le n \cdot m \le 300\,000$, $1 \le k \le n \cdot m$)。接下来的 $k$ 行，每行包含两个整数 $r_i, c_i$ ($1 \le r_i \le n, 1 \le c_i \le m$)，表示 Jeroen 计划走的第 $i$ 手棋所在的行和列。

输出格式

输出一行长度为 $k$ 的字符串，如果第 $i$ 手棋会被执行，则第 $i$ 位为 $1$；如果这一步会导致游戏结束（因此不会被执行），则第 $i$ 位为 $0$。

样例

输入 1

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

输出 1

1111111

输入 2

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

输出 2

11111110