题目描述

在 L 省 K 小学二年级的课堂上，卡睿正在教学生们 Hamilton 圈的相关知识。

给定一个 $R\times C$ 的网格，距离为 $1$ 的两个点之间连有一条边，你需要找到该图的一条 Hamilton 圈。

通过这个例子，卡睿引入组合数学问题的一般思想：

如果 $R$ 和 $C$ 都是奇数，通过黑白染色（奇偶分析）可以证明无解；

否则，不妨设 $R$ 是偶数，则可以通过画 S 字形的方式来构造，具体图略。

你作为课堂上的学生，觉得这个问题太简单了，于是想增大一点难度：

你希望该 Hamilton 圈中，任意连续的两条边不能平行。

聪明的你立马意识到，此时除了 $R=C=2$ 都是无解的：

设所有顶点的坐标分别为 $(i,j)$（$0\le i\le C-1$，$0\le j\le R-1$，右为 $+i$，上为 $+j$）。

由于 $(0,0)$ 点的度为 $2$，因此其连接方式唯一，那么由于不能平行，则必须存在路径

$$(0,0)\to (0,1)\to (1,1)$$

和

$$(0,0)\to (1,0)\to (1,1),$$

这说明 $R$ 和 $C$ 都必须为 $2$。

于是你放宽了要求，认为距离为 $\sqrt 2$ 的两个点之间，也能相连。为了美观，你还要求 Hamilton 圈上的任意两条边不能在非顶点处相交。

这样，问题看似复杂了许多。你能找到，当 $R$ 和 $C$ 满足什么条件时，存在 Hamilton 圈吗？

简要题意：给定无向简单图 $G=(V,E)$，其中

$$V=\{(i,j)\mid 0\le i\le C-1,\ 0\le j\le R-1,\ i,j\in\mathbb Z\},$$

$E$ 为所有距离为 $1$ 或 $\sqrt 2$ 的点对构成的二元组。你需要判断 $G$ 是否存在满足连续两条边不平行且任意两条边不在非顶点处相交的 Hamilton 圈，并给出一组构造。

输入格式

共一行，包含两个正整数 $R,C$。

输出格式

如果不存在满足条件的 Hamilton 圈，输出一行一个整数 $-1$。

否则，我们将 Hamilton 圈看成从 $(0,0)$ 出发回到 $(0,0)$ 的一次 travel，每一步有八种选择：左、上、右、下、左上、右上、右下、左下，它们分别用字母 A、W、D、X、Q、E、C、Z 表示（可以看看你的键盘）。

你需要输出一个长度为 $R\times C$ 的字符串，表示每一步的方向，顺时针逆时针均可；如果有多组解，输出任意一组均可。

样例一

输入

2 2

输出

DWAX

解释

当然，WDXA 也是正确答案，除此之外没有其它的正确答案了。

样例二

输入

4 4

输出

DEXDWQDWAZWAXCAX

解释

见题目描述中第一张图。

样例三

输入

3 5

输出

-1

限制与约定

对于所有的测试点，保证：

$$R,C\ge 2,\qquad R\times C\le 10^6.$$

• 对于前 $16\%$ 的数据，保证 $R,C\le 6$；
• 对于另外 $12\%$ 的数据，保证 $\min\{R,C\}\le 4$；
• 对于另外 $20\%$ 的数据，保证 $R,C\le 50$；
• 对于另外 $24\%$ 的数据，保证 $R,C$ 都是偶数。

时间限制：$1\text{s}$

空间限制：$512\text{MB}$