该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个 $n$ 行 $m$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的格子。江月诗现在位于 $(1,1)$，准备前往 $(n,m)$。

然而，不是所有的格子都是可以通行的，有且恰有一个格子是陷阱格，一旦江月诗踏入陷阱格，就会直接去逝。保证这个陷阱格不会出现在 $(1,1)$ 和 $(n,m)$。

江月诗每一步只能向右或者向下前进。请你帮江月诗规划一条行动路线，使得她可以顺利到达 $(n,m)$。

行动路线为一个仅由字符 $\texttt{"D"}$、$\texttt{"S"}$ 构成的字符串 $s$，第 $i$ 个字符代表江月诗第 $i$ 次行动的方向。记第 $i$ 次行动前江月诗位于 $(x,y)$，则：

​ $\bullet\,$若 $s_i = \texttt{"D"}$，则江月诗向右移动一格即抵达 $(x,y+1)$；

​ $\bullet\,$若 $s_i = \texttt{"S"}$，则江月诗向下移动一格即抵达 $(x+1,y)$。

输入格式

第一行，输入两个正整数 $n,m \left(2 \leq n,m \leq 10^3\right)$，代表网格的行数和列数。

接下来的 $n$ 行，第 $i$ 行输入一个长度为 $m$ 的、仅由 $\texttt{"."}$ 和 $\texttt{"\#"}$ 构成的字符串 $a_{i,1},a_{i,2}\cdots a_{i,m}$。其中 $a_{i,j} = \texttt{"."}$ 表示格子 $(i,j)$ 可以通行，$a_{i,j} = \texttt{"\#"}$ 表示格子 $(i,j)$ 是陷阱格。

除此之外，保证有且只有一个陷阱格，且不位于 $(1,1)$ 和 $(n,m)$。

输出格式

输出一个字符串，代表江月诗的行动路线。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

输入样例

2 3
...
.#.

输出样例

DDS