在手机游戏《丛林小径》（Jungle Trail）中，你将获得一个 $n \times m$ 的矩形棋盘，棋盘被划分为 $n \cdot m$ 个方格。每个方格要么是空的，要么是阻挡的（不可通行），要么包含一个蛇窝（蛇窝里的蛇要么全是毒蛇，要么全是无毒蛇）。
游戏允许你点击棋盘的任意列或任意行。如果你点击一列，该列中所有毒蛇都会变成无毒，反之亦然。同样，如果你点击任意行，该行中所有蛇的状态也会发生改变。每行/每列你只能点击一次。如果一个蛇窝既位于被点击的行，又位于被点击的列，那么它的状态会变回原始状态。
在执行完所有这些操作后，你必须找到一条穿过丛林的小径：这条路径从左上角出发，每一步只能向下或向右移动一格，最终到达右下角，且路径不能经过任何毒蛇窝或阻挡的方格。
输入格式
第一行包含测试用例的数量 $z$ ($1 \le z \le 500$)。接下来是各测试用例的描述。
第一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 2000$)。
接下来的 $n$ 行，每行包含 $m$ 个字符，分别为 .、#、O（大写字母“o”）和 @（at 符号），分别代表空方格、阻挡方格、无毒蛇窝和毒蛇窝。你可以假设左上角和右下角不是阻挡的。
所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $15\,000$。
输出格式
对于每个测试用例，按以下格式输出结果：
第一行输出 TAK（如果存在丛林小径）或 NIE（如果不存在）。
如果答案为 TAK，则在接下来的三行中输出：
- 一个包含 $n$ 个字符
T或N的序列，其中第 $i$ 个字符为T表示第 $i$ 行应被点击，N表示不点击； - 一个包含 $m$ 个字符
T或N的序列，以同样的方式确定是否应点击各列； - 一个包含 $n + m - 2$ 个字符
P或D的序列，表示路径：P表示向右移动，D表示向下移动。
样例
输入 1
1 4 5 ..#.. @@O@@ ##@#O ..@.@
输出 1
TAK NTNN NNTNT DPPDDPP
说明
在执行输出中描述的行和列点击操作后，棋盘状态如下：
..#.. OOOO@ ##O#@ ..O.O
现在，给定的路径仅经过 . 和 O 方格。