Gennady 和 Georgiy 正在一个有向图上玩一个有趣的游戏。该图有 $n$ 个顶点和 $m$ 条弧，允许存在自环。Gennady 和 Georgiy 将一枚棋子放置在图中的某个顶点上。玩家轮流将棋子沿当前所在顶点出发的弧移动。当某位玩家无法移动时，该玩家输掉游戏。

对于棋子的每个初始位置以及先手玩家，你的任务是确定游戏的结果。这看起来很简单吗？其实不然。

一方面，Gennady 玩这个游戏玩得很开心，所以他想尽可能长时间地玩下去。他甚至更倾向于选择能导致无限博弈的策略，而不是让他获胜的策略。但如果他无法使游戏无限进行下去，那么他显然更倾向于获胜而不是输掉比赛。

另一方面，Georgiy 还有很多其他工作要做，所以他不想无限期地玩这个游戏。Georgiy 想赢得比赛，但如果他不能获胜，那么他更倾向于输掉比赛，而不是让游戏无限进行下去。

双方都在进行最优博弈。双方都了解对方的偏好。

输入格式

第一行包含两个整数——顶点数 $n$ ($1 \le n \le 100\,000$) 和弧数 $m$ ($1 \le m \le 200\,000$)。接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示一条从顶点 $a$ 到顶点 $b$ 的弧。顶点编号为 $1$ 到 $n$。每个 $(a, b)$ 元组最多出现一次。

输出格式

第一行输出 $n$ 个字符——第 $i$ 个字符表示如果 Gennady 从顶点 $i$ 开始移动，游戏的结果。第二行输出 $n$ 个字符——第 $i$ 个字符表示如果 Georgiy 从顶点 $i$ 开始移动，游戏的结果。游戏结果用 “W” 表示先手玩家获胜，“L” 表示先手玩家输掉游戏，“D” 表示平局（游戏无限进行）。

样例

输入 1

6 7
1 2
2 1
2 3
1 4
4 1
4 5
5 6

输出 1

WDLDWL
DWLLWL

说明

在顶点 3 和 6，游戏已经输掉。在顶点 5，唯一的移动是到顶点 6，玩家获胜。如果 Georgiy 从顶点 1 开始，或者 Gennady 从顶点 2 或 4 开始，Gennady 总能移动到顶点 1，使游戏无限进行。如果 Georgiy 从顶点 4 开始，他可以选择移动到顶点 1（导致平局）或移动到顶点 5（导致输掉比赛）。Georgiy 更倾向于后者。同样，从顶点 2 出发，他更倾向于移动到 3 并获胜。从顶点 1 出发，Gennady 可以移动到 2 并输掉比赛，或者移动到 4 并获胜。他更倾向于后者。