You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

塔子哥有一些宝物藏在了家里的地板下面，地板为一个一个方格。现在他忘了有多少宝物,也忘了存放的位置。他现在希望你从一个点出发，翻开所有的地板一次且仅有一次。现在想让你找出翻开的路径。

输入描述

两个正整数$n$和$m$，用空格隔开表示家中地板的大小

$1 \leq n,m \leq 1000$

保证$n$，$m$不同时为$1$

输出描述

第一行输入两个正整数$x$和$y$，代表初始的点为第$x$行第$y$列

第二行输入一个长度为$n*m-1$的字符串，共有$4$种字符；

"$W$"向上走

"$S$"向下走

"$A$"向左走

"$D$"向右走

有多解时输出任意即可。

样例

输入

3 3

输出

3 1
DWAWDDSS

说明

如以下顺序所示