题目描述

一个新建工厂在虚拟现实中表示为一个 $R$ 行 $C$ 列的矩形网格，共有 $R\times C$ 个正方形区域。

其中有 $K$ 个区域已经安装了设备。任何移动路径都不能经过这些区域的内部或边界。

现在要把位于第 $1$ 行第 $1$ 列区域中的零件，移动到第 $R$ 行第 $C$ 列区域中。为了提高效率，移动路径必须是一条直线段。

你可以在 $(1,1)$ 区域的内部或边界上任意选择起点，也可以在 $(R,C)$ 区域的内部或边界上任意选择终点。

请判断是否存在一条从起点到终点的直线段，使其不经过任何安装了设备的区域的内部或边界。

输入格式

第一行包含三个整数 $R,C,K$，分别表示网格的行数、列数和障碍区域数量。

接下来 $K$ 行，每行包含两个整数 $r,c$，表示第 $r$ 行第 $c$ 列的区域安装了设备。

保证：

• $(1,1)$ 和 $(R,C)$ 不会安装设备；
• 所有障碍区域坐标互不相同。

输出格式

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

样例 1

输入

4 5 2
2 2
3 4

输出

0

样例 1 示意图

样例 2

输入

4 5 2
3 2
2 4

输出

1

样例 2 示意图