Hyundai AutoEver 正在建设一座智能工厂，将人工智能、机器人、物联网和大数据等 ICT 技术应用于现有的生产流程。在 Hyundai AutoEver 工作的 Daehyun 负责利用新建立的智能工厂技术优化工厂内的移动路径。

Daehyun 希望基于数字孪生技术模拟实际工厂内的移动，该技术在虚拟现实中实现了实际工厂的映射。新建的工厂被表示为一个由 $r \times c$ 个方形区域组成的矩形网格，共有 $r$ 行和 $c$ 列。其中一些区域已经安装了设备，不允许通过这些区域及其边界。

我们将位于第 $r$ 行第 $c$ 列的方形区域记为 $(r, c)$。Daehyun 希望将生产于 $(1, 1)$ 的零件移动到 $(r, c)$。由于直线移动效率最高，Daehyun 想知道是否存在一条从 $(1, 1)$ 区域内或其边界上的任意一点，到 $(r, c)$ 区域内或其边界上的任意一点的直线路径。请帮助 Daehyun。

输入格式

第一行包含三个整数 $r$、$c$ 和 $k$：行数、列数以及已安装设备的区域数量（$2 \le r, c \le 1000$；$1 \le k \le 10^5$）。

接下来的 $k$ 行中，第 $i$ 行包含两个整数 $r_i$ 和 $c_i$：第 $i$ 个已安装设备区域的行号和列号（$1 \le r_i \le r$；$1 \le c_i \le c$）。

你可以假设 $(1, 1)$ 和 $(r, c)$ 处的区域没有安装设备，且已安装设备的区域坐标各不相同。

输出格式

如果存在满足题目条件的直线路径，输出 1；否则，输出 0。

样例

样例输入 1

4 5 2
2 2
3 4

样例输出 1

0

样例输入 2

4 5 2
3 2
2 4

样例输出 2

1