Bajtazar 正在玩一款波兰版的《炸弹人》游戏。玩家在 $n \times n$ 的棋盘上移动。每个格子要么是空的，要么包含障碍物（砖墙或坚硬的岩石）。障碍物所在的格子无法进入。
游戏的目标是尽快从起点移动到终点。从一个格子移动到相邻的格子（共享边）需要 1 秒。
游戏开始时，玩家可以在棋盘上任何不包含坚硬岩石的格子上放置一颗炸弹。这包括砖墙、起点、终点或空地。炸弹爆炸后，会摧毁与炸弹位于同一行或同一列的所有砖墙，前提是炸弹与该砖墙之间没有坚硬的岩石。换句话说，如果一个砖墙格子与炸弹在同一行或同一列，且它们之间没有坚硬的岩石，那么该砖墙就会变成可以通过的空地。
炸弹在玩家进入棋盘之前就会引爆，因此无论炸弹放置在哪里，玩家都不会受到伤害。
Bajtazar 想要为不同的棋盘找到最优解。请编写一个程序来帮助他。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 1000$)，表示棋盘的大小。
接下来的 $n$ 行描述了棋盘的每一行；每行由一个长度为 $n$ 的字符串组成，包含字符 .（空地）、#（砖墙）、X（坚硬岩石）、P（起点）和 K（终点）。
输入中恰好包含一个起点和一个终点。假设这些格子初始为空。
输出格式
第一行应输出一个整数 $T$，表示在最优放置炸弹的情况下，从起点到终点的最小移动时间（以秒为单位）。
第二行应输出两个整数 $W$ 和 $K$，分别表示放置炸弹的行号和列号。行号和列号从 1 到 $n$ 编号（从上到下，从左到右）。
第三行（最后一行）应输出一个长度为 $T$ 的字符串，描述从起点到终点的移动序列。该序列应由字符 L、P、G 或 D 组成，分别表示向左、向右、向上或向下移动。
如果无论炸弹放置在哪里都无法从起点到达终点，则输出一行包含单词 NIE。
如果存在多个正确的解，输出其中任意一个即可。
说明
示例说明：不使用炸弹时的最小移动时间为 13 秒。将炸弹放置在第二行第三列的交点处，可以摧毁三堵砖墙，从而使移动时间缩短至 9 秒。
测试用例
- $n = 7$，起点和终点在棋盘的对角，无障碍物，结果为 12。
- $n = 10$，起点和终点被三道斜向的坚硬岩石墙隔开，结果为
NIE。 - $n = 21$，棋盘被坚硬岩石包围，起点和终点之间只有一条锯齿状路径，结果为 198。
- $n = 200$，起点和终点在棋盘的对角，其余格子均为砖墙，结果为 398。
- $n = 1000$，仅前两行包含非坚硬岩石的格子，结果为 1001。
子任务
| 子任务 | 条件 | 时间限制 | 分数 |
|---|---|---|---|
| 1 | 棋盘不包含砖墙 | 8 s | 10 |
| 2 | $n \le 50$ | 2 s | 20 |
| 3 | $n \le 200$ | 3 s | 30 |
| 4 | $n \le 1000$ | 8 s | 40 |
如果你的程序仅正确输出了第一行（最小时间），将获得该测试点 80% 的分数。请注意，程序仍需在时间和内存限制内运行，且不能出现运行时错误。
样例
输入格式 1
6 ...... .X.##. ..#.X. ..X.#K .P#.X# .X....
输出格式 1
9 2 3 GGPPGPPDD