解题思路

题目允许输出任意一条走遍每个格子恰好一次的路径。可以固定从左上角 $(1,1)$ 出发，按蛇形走完整张网格：

• 奇数行（第 1、3、5、$\ldots$ 行，对应下标从 0 开始的偶数行）一律向右走，输出 D；
• 偶数行一律向左走，输出 A；
• 走到一行尽头且还不是最后一行时，向下走一格，输出 S。

这样每个格子恰好经过一次，路径长度为 $n\times m-1$。当某一维为 1 时，蛇形会退化成一条直线，仍然合法。

题目内容

仓库被划分成 $n$ 行 $m$ 列的格子。巡检员需要从某个格子出发，走过每一个格子恰好一次。行走时只能走到相邻格子，并用四个字符记录方向：W 表示向上，S 表示向下，A 表示向左，D 表示向右。

请给出一个合法的起点以及一条长度为 $n \times m - 1$ 的路径字符串。有多解时输出任意一组即可。

约束：行数与列数均不超过 1000，且二者不同时为 1。

输入描述

一行两个正整数 $n$ 和 $m$，分别表示仓库的行数与列数。保证 $1 \le n, m \le 1000$，且 $n$、$m$ 不同时为 1。

输出描述

第一行两个正整数 $x$ 和 $y$，表示起点位于第 $x$ 行第 $y$ 列。 第二行一个长度为 $n \times m - 1$ 的字符串，仅由字符 W、S、A、D 组成，表示依次行走的方向。

样例1

输入

1 2

输出

1 1
D

说明

只有一行两列，从 $(1,1)$ 向右走一步即可。路径为 D。这是 $n=1$ 的边界情形。

样例2

输入

2 1

输出

1 1
S

说明

只有一列两行，从 $(1,1)$ 向下走一步即可。路径为 S。这是 $m=1$ 的边界情形。

样例3

输入

2 2

输出

1 1
DSA

说明

从 $(1,1)$ 向右 D 到 $(1,2)$，向下 S 到 $(2,2)$，向左 A 到 $(2,1)$，走遍 $2 \times 2$ 网格。