Johnny 刚到达纽约参加会议。他在飞机上睡了一觉，现在有一整天的空闲时间。他想去观光，但晚上必须准时赶到会议地点。Johnny 做好了充分的准备——他知道纽约的街道呈规则的网格状，每个路口都有他感兴趣的景点！Johnny 想知道，是否有可能从位于路口 $s$ 的酒店出发，前往位于路口 $t$ 的会议地点，并恰好经过每一个路口一次——他不想浪费任何时间。当然，他在离开酒店后，甚至在旅程开始前，就已经访问了路口 $s$。

纽约的街道呈规则的网格状：地图上有 $n$ 条纵向街道和 $m$ 条横向街道。街道名称仅为数字：纵向街道从左侧开始编号，横向街道从上方开始编号，两种街道均从 1 开始依次编号。每条横向街道都与每条纵向街道相交，第 $x$ 条纵向街道与第 $y$ 条横向街道的交点记为 $(x, y)$。

输入格式

输入包含三行，每行包含两个由空格分隔的整数。第一行包含 $n$ 和 $m$ ($4 \le n, m \le 1000$)，分别表示地图上纵向和横向街道的数量。第二行包含 $s_x$ 和 $s_y$ ($1 \le s_x \le n$ 且 $1 \le s_y \le m$)。第三行包含 $t_x$ 和 $t_y$ ($1 \le t_x \le n$ 且 $1 \le t_y \le m$)。酒店位于路口 $(s_x, s_y)$，会议地点位于路口 $(t_x, t_y)$。路口 $s$ 和 $t$ 不相同。

输出格式

输出应包含一行，描述 Johnny 可以采取的行程，如果无法满足上述条件的行程，则输出单词 NIE。该描述应由一个长度为 $n \cdot m - 1$ 的字符串组成，包含字符 D、G、L 或 P，分别表示 Johnny 下一步应向下方、上方、左方或右方最近的路口移动（此处上、下、左、右是指 Johnny 在地图上的方向）。

样例

样例输入 1

4 4
1 1
1 4

样例输出 1

PPPDLLLDPPPDLLL

说明 1

下图展示了 Johnny 可以采取的一个行程示例。酒店用圆点标记，会议地点用叉号标记。

样例输入 2

4 4
3 2
2 3

样例输出 2

NIE

说明 2

酒店用圆点标记，会议地点用叉号标记。无法完成经过每一个路口恰好一次的行程。