题目描述

给定共 $n$ 行 $m$ 列的网格，在其中放有 $k$ 个激光发射器。

每个激光发射器的方向为上下左右其中之一。激光以激光发射器为起点按给定方向延伸，在碰到网格边缘或者另一个激光发射器后停下。

我们认为激光发射器 $a$ 能够攻击发射器 $b$ 当且仅当 $b$ 是从 $a$ 发出的激光第一个碰到的激光发射器。

现在给定所有发射器的位置和初始方向，问能否改变至多一个发射器的方向使得不存在两个发射器能够互相攻击。

输入格式

本题采用多组测试数据。

第 $1$ 行一个正整数 $T$，表示测试数据的组数。

对于每组数据，第 $1$ 行 $3$ 个正整数 $n,m,k$，分别表示网格的大小以及激光发射器的个数。

接下来 $k$ 行，每行 $2$ 个整数 $x,y$，表示发射器的位置（这里 $x$, $y$ 表示从上往下第 $x$ 行从左往右第 $y$ 列），以及一个字符 $c\in \{\texttt{L},\texttt{R},\texttt{U},\texttt{D}\}$ 描述这个发射器的初始方向。

输出格式

输出 $T$ 行，每行输出字符串 $\texttt{Yes}$ 或者 $\texttt{No}$，表示是否能改变至多一个发射器的方向使得不存在两个相互攻击的发射器。

2
3 3 4 
1 1 R
1 3 L
3 1 R
3 3 L
3 3 4
1 1 R
1 3 L
3 1 R
3 3 U

No
Yes

说明/提示

数据范围

为表述方便，记 $K$ 为所有测试数据的 $k$ 之和，$N,M$ 分别为所有测试数据的 $n,m$ 的最大值

对于 $100\%$ 的数据，保证 $1\le N,M\le 10^9$，$1\le K\le 2\times10^5$，$1\le x\leq n$，$1\le y\le m$，$c\in \{\texttt{L},\texttt{R},\texttt{U},\texttt{D}\}$，保证给出的发射器两两位置不相同