题目背景

翻译自 POI2021~2022R2 Day2T1。

时限：sub1 和 sub4 8s，sub2 2s, sub3 3s。

题目描述

你有一个 $n \times n$ 的图，仅包含 .、X、P、K、#，意义如下：

• P 起点。
• K 终点。
• . 可以通过的路。
• X 不可以通过的岩石墙。
• # 不可以通过的砖墙。

你还有一枚炸弹，你选择一个不是岩石墙的地方放置，爆炸时，会从原来的地方上下左右依次扩散爆炸直到某一方向碰到了岩石墙或超出了图的范围。
爆炸区域变为空地，但岩石墙不会。

然后你需要求出起点至终点的最短路径。

输入格式

第一行一个整数 $n\ (2 \leq n \leq 1000)$。

然后 $n \times n$ 大小的字符矩阵，描述了图。

输出格式

如果放置完炸弹并引爆后有解，则输出三行：

• 第一行：最短路径长度。
• 第二行：放置炸弹位置。
• 第三行：其中符合条件的最短路径（其中 G 表示向上，D 表示向下，L 表示向左，P 表示向右）。

若无解，输出 NIE。

6
......
.X.##.
..#.X.
..X.#K
.P#.X#
.X....

9
2 3
GGPPGPPDD

提示

样例解释：

子任务分配如下：