题目描述

Cimrman 建造了一整支用于天气预报的特殊钼制独木舟船队。

每一艘独木舟都在各自的干船坞中单独建造。因此，海岸上遍布着挖出的船坞，有些船坞彼此相交，有些则完全分离。

每个干船坞都是一个矩形：

• 宽度恰好为 $1$ 个标准单位；
• 长度为至少 $2$ 个标准单位的整数；
• 方向只能是水平或竖直。

因此，任意两个船坞要么平行，要么互相垂直。

每艘独木舟的宽度与其船坞相同，长度则比船坞短恰好 $1$ 个单位。

下周当地预计会有飓风。Cimrman 希望把每一艘独木舟放回制造它的船坞中。

对于一个长度为 $K$ 的船坞，长度为 $K-1$ 的独木舟可以靠船坞的任意一端放置，因此通常有两种放置方式。

所有独木舟必须同时被放入各自船坞，并且不能发生不允许的实体重叠。

请判断是否存在一种能够存放全部独木舟的方案。

顺便说明，确实可能存在正方形独木舟：当船坞长度为 $2$ 时，独木舟的尺寸为 $1\times1$。

输入格式

海岸被建模成一个矩形网格，每个单位方格的边长为 $1$。

第一行包含三个正整数 $H,W,N$：

$$1\le H,W\le500,\qquad 1\le N\le250\,000,$$

分别表示网格高度、网格宽度和船坞数量。

接下来 $N$ 行，每行描述一个船坞，包含四个字段：

X Y K D

其中：

• $(X,Y)$ 是船坞一端所在单位方格的坐标；
• $K$ 是船坞占据的单位方格数；
• $D$ 是字符 L、R、U、D 之一，表示船坞从起点开始延伸的方向：
  • L：向左；
  • R：向右；
  • U：向上；
  • D：向下。

满足：

$$1\le X\le H,\qquad 1\le Y\le W,\qquad 2\le K\le500.$$

保证所有船坞都完全位于网格范围内。

输出格式

如果存在一种方案，可以把所有独木舟同时放回各自船坞，输出：

Yes

否则输出：

No

样例输入1