题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Bomberman

Bajtazar 最近沉迷于字节版的《炸弹人》（Bomberman）游戏。在这个游戏中，你控制一个角色在一个 $n \times n$ 的方格地图上移动。地图上的每个格子可能是空的，也可能是砖墙或坚固岩石构成的障碍物。你无法进入有障碍物的格子。

游戏的目标是从起点格子尽快到达终点格子。角色只能移动到与当前格子共享边的相邻格子，每次移动需要 $1$ 秒。

游戏开始时，你可以在地图上任意一个没有坚固岩石的格子放置一枚炸弹——可以是砖墙格、起点、终点或空地。炸弹爆炸后，会摧毁同一行或同一列中所有的砖墙，前提是炸弹与这些砖墙之间没有被坚固岩石阻隔。换句话说，如果某个砖墙格与炸弹在同一行或同一列，且两者之间没有坚固岩石，那么这个砖墙会被炸成空地，可以通行。

炸弹在你进入地图前就会引爆，因此无论你把炸弹放在哪里，角色都不会受到伤害。

Bajtazar 想为不同的地图找到最佳策略。请你编写一个程序，帮他实现这个目标。

输入格式

输入的第一行包含一个整数 $n$ $(2 \leq n \leq 1000)$，表示地图的大小。

接下来的 $n$ 行描述地图的每一行，每行是一个长度为 $n$ 的字符串，包含以下字符：

• . 表示空地，
• # 表示砖墙，
• X 表示坚固岩石，
• P 表示起点，
• K 表示终点。

地图中恰好有一个起点和一个终点，且起点和终点视为空地。

输出格式

你的程序应输出三行内容：

第一行包含一个整数 $T$，表示在最佳放置炸弹的情况下，从起点到终点的最短时间（单位：秒）。

第二行包含两个整数 $W$ 和 $K$，分别表示放置炸弹的行号和列号（行和列从 $1$ 到 $n$ 编号，从上到下、从左到右）。

第三行包含一个长度为 $T$ 的字符串，由字符 L（左）、P（右）、G（上）或 D（下）组成，表示从起点到终点的移动序列。

如果无论如何放置炸弹都无法从起点到达终点，则只输出一行一个字符串 NIE。

如果存在多种正确解法，你的程序可以输出任意一种。

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

9
2 3
GGPPGPPDD

样例 2

见附加文件下 [bom1.in](file:bom1.in) 和 [bom1.out](file:bom1.out)。

该样例满足 $n=7$，起点和终点在地图对角，地图无障碍物，结果为 $12$；

样例 3

见附加文件下 [bom2.in](file:bom2.in) 和 [bom2.out](file:bom2.out)。

该样例满足 $n=10$，起点和终点被三层斜向坚固岩石墙隔开，结果为 NIE；

样例 4

见附加文件下 [bom3.in](file:bom3.in) 和 [bom3.out](file:bom3.out)。

该样例满足 $n=21$，地图被坚固岩石包围，起点和终点之间只有一条之字形通道，结果为 $198$；

样例 5

见附加文件下 [bom4.in](file:bom4.in) 和 [bom4.out](file:bom4.out)。

该样例满足 $n=200$，起点和终点在对角，除此之外全是砖墙，结果为 $398$；

样例 6

见附加文件下 [bom5.in](file:bom5.in) 和 [bom5.out](file:bom5.out)。

该样例满足 $n=1000$，只有前两行包含非坚固岩石的内容，结果为 $1001$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

如果你的程序仅正确输出第一行，仍可获得该测试点 $80\%$ 的分数。

子任务编号	附加限制	分值
$1$	地图不含砖墙	$10$
$2$	$n \leq 50$	$20$
$3$	$n \leq 200$	$30$
$4$	$n \leq 1000$	$40$