爱丽丝这几天得到了一个新娃娃。它甚至可以行走!
Alice 为娃娃建造了一个迷宫并想要测试它。迷宫是一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。有 $$$k$$$ 个障碍物,其中第 $$$i$$$ 位于单元格 $$$(x_i, y_i)$$$ 上,即第 $$$x_i$$$ 行与第 $$$y_i$$$ 列交集的单元格。
然而,这个娃娃在某些方面很笨拙。在同一个单元格(包括起始单元格)内最多只能直行或右转一次。它无法进入有障碍物的牢房或走出迷宫。
更正式地说,存在 $$$4$$$ 方向,娃娃可以在其中查看:
1. 娃娃沿着行从第一个单元格到最后一个单元格的方向看。当朝这个方向移动时,娃娃将从单元格 $$$(x, y)$$$ 移动到单元格 $$$(x, y + 1)$$$;
2. 娃娃沿着列从第一个单元到最后一个单元的方向看。当朝这个方向移动时,娃娃将从单元格 $$$(x, y)$$$ 移动到单元格 $$$(x + 1, y)$$$;
3. 娃娃沿着行从最后一个单元格到第一个单元格的方向看。当朝这个方向移动时,娃娃将从单元格 $$$(x, y)$$$ 移动到单元格 $$$(x, y - 1)$$$;
4. 娃娃沿着列从最后一个单元格到第一个单元格的方向看。当朝这个方向移动时,娃娃将从单元格 $$$(x, y)$$$ 移动到单元格 $$$(x - 1, y)$$$。
站在某个牢房中,玩偶可以按照它看起来的方向进入牢房,也可以向右转一次。向右转一次,娃娃会按照以下规则改变方向:$$$1 \to 2$$$、$$$2 \to 3$$$、$$$3 \to 4$$$、$$$4 \to 1$$$。站在一间牢房里,娃娃最多只能右转一圈。
现在爱丽丝正在控制娃娃的动作。她将娃娃放入单元格 $$$(1, 1)$$$(迷宫的左上角单元格)中。最初,娃娃朝 $$$1$$$ 方向看,因此沿着从第一个单元格到最后一个单元格的行。她想让娃娃顺利地穿过所有牢房一次,并在任何地方结束。能实现吗?
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$,用空格分隔 ($$$1 \leq n,m \leq 10^5, 0 \leq k \leq 10^5$$$) — 迷宫的大小和障碍物的数量。
接下来的$$$k$$$行描述了障碍物,第$$$i$$$行包含两个整数$$$x_i$$$和$$$y_i$$$,用空格分隔($$$1 \leq x_i \leq n,1 \leq y_i \leq m$$$),它描述了第$$$i$$$个障碍物的位置。
保证同一单元格中没有两个障碍物,并且单元格 $$$(1, 1)$$$ 中没有障碍物。
输出
如果玩偶可以按照声明中描述的规则准确无误地穿过所有单元格一次,则打印“是”(不带引号)。
如果按照这些规则不可能穿过迷宫,则打印“否”(不带引号)。
示例
输入 #1
3 3 2 2 2 2 1
输出 #1
Yes
输入 #2
3 3 2 3 1 2 2
输出 #2
No
输入 #3
3 3 8 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
输出 #3
Yes
注意
这是第一个示例中描述的迷宫图片:
在第一个例子中,娃娃可以这样走路:
- 娃娃位于单元格 $$$(1, 1)$$$ 中,看向 $$$1$$$ 方向。直行;
- 娃娃位于单元格 $$$(1, 2)$$$ 中,看向 $$$1$$$ 方向。直行;
- 娃娃位于单元格 $$$(1, 3)$$$ 中,看向 $$$1$$$ 方向。右转;
- 娃娃位于单元格 $$$(1, 3)$$$ 中,看向 $$$2$$$ 方向。直行;
- 娃娃位于单元格 $$$(2, 3)$$$ 中,看向 $$$2$$$ 方向。直行;
- 娃娃位于单元格 $$$(3, 3)$$$ 中,看向 $$$2$$$ 方向。右转;
- 娃娃位于单元格 $$$(3, 3)$$$ 中,看向 $$$3$$$ 方向。直行;
- 娃娃位于单元格 $$$(3, 2)$$$ 中,看向 $$$3$$$ 方向。直行;
- 娃娃位于单元格 $$$(3, 1)$$$ 中,看向 $$$3$$$ 方向。目标达到了,迷宫中没有障碍物的所有单元格都通过了一次。