题目描述

你正在一个 $h\times w$ 的网格上玩类似弹球的游戏。

游戏开始时，一个小球位于标记为 S 的格子中心。网格中的每个格子属于以下类型之一：

• #：方块墙。小球不能进入该格子，而会在墙面处反弹；
• \ 或 /：细斜墙。小球进入该格子后，会根据斜墙方向发生反射；
• .：空格子，小球可以自由穿过；
• S：小球的初始位置，该格子本质上也是空格子。

弹球场地示意图

游戏目标是让小球逃出网格。

开始时，你可以将小球朝四个方向之一轻推：

• U：向上；
• D：向下；
• L：向左；
• R：向右。

小球穿过一个空格子需要 $1$ 秒；进入并离开一个含有细斜墙的格子也需要 $1$ 秒；小球撞到方块墙并完成反弹不消耗时间，因为方块墙占满整个格子。

例如，小球进入一个空格子、穿过它、撞上相邻的方块墙、反弹并再次穿过该空格子直至离开，共需要 $2$ 秒。

小球与所有墙壁的碰撞都是完全弹性的。

在小球运动期间，你可以在任意时刻摧毁细斜墙。被摧毁的斜墙会永久变为空格子。你可以摧毁多面斜墙。

请判断是否能够让小球逃出网格。如果可以，还需要：

1. 最小化摧毁的斜墙数量；
2. 给出每一面被摧毁斜墙的准确摧毁时间。

输入格式

第一行包含两个整数 $h,w$：

$$1\le h,w\le1000.$$

接下来 $h$ 行描述初始网格。第 $i$ 行包含一个长度为 $w$ 的字符串。

所有字符均属于集合：

. # \ / S

并且字符 S 恰好出现一次。

输出格式

如果无法让小球逃出网格，输出：

NO

否则，第一行输出：

YES

第二行输出一个字符 $d\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$，表示开始时轻推小球的方向。

第三行输出整数 $k$，表示需要摧毁的最少斜墙数量。

接下来输出 $k$ 行。第 $i$ 行包含三个整数 $t_i,r_i,c_i$，表示在小球开始运动后的第 $t_i$ 秒，摧毁位于从上往下第 $r_i$ 行、从左往右第 $c_i$ 列的斜墙。

斜墙会在时间恰好到达 $t_i$ 之前被摧毁。换言之，如果小球原本会在第 $t_i$ 秒恰好撞上该斜墙，那么此时该格子已经被视为空格子。

输出还必须满足：

• 操作按时间非递减顺序输出，即 $t_i\le t_{i+1}$；
• 同一面墙不能被摧毁多次；
• 每个指定格子在初始网格中都必须是 \ 或 /；
• 所有时间均满足：

$$0\le t_i\le10^7.$$

可以证明，只要存在解，就一定存在所有 $t_i$ 都不超过 $10^7$ 的解。

样例 1

输入

4 6
#\###.
#./S##
#\\..#
######

输出

YES
L
2
7 3 3
8 1 2

说明

至少需要摧毁两面墙。样例方案中的关键时刻如下：

• $t=0$：小球从初始位置向左运动；
• $t=4.5$：小球撞上方块墙并反弹；
• 在 $t=7$ 之前，摧毁位置 $(3,3)$ 的斜墙；
• 在 $t=8$ 之前，摧毁位置 $(1,2)$ 的斜墙；
• $t=10.5$：小球最终逃出网格。

样例 1 的关键时刻

样例 2

输入

3 3
###
.S.
###

输出

YES
R
0

说明

直接将小球向左或向右推动即可逃出网格，无需摧毁任何斜墙。