AT_abc443_e [ABC443E] Climbing Silver

有一个 $N \times N$ 的网格，位于从上往下第 $i$ 行和从左往右第 $j$ 列的单元格叫做 $(i,j)$。 网格由长度为 $N$ 的字符串 $S_1,S_2,\dots,S_N$ 描述。如果 $S_i$ 的第 $j$ 个字符是 `.`，$(i,j)$ 就是一个空单元格；如果是 `#`，$(i,j)$ 就是一个墙单元格。 最初，高桥君位于空单元格 $(N,C)$，并重复以下动作 $N-1$ 次： - 如果他当前位于 $(r,c)$，则指定 $(r-1,c-1),(r-1,c),(r-1,c+1)$ 中的一个作为目的地。在此，他不能指定网格中不存在的单元格作为目的地。 - 如果目的地 $(a,b)$ 是一个墙单元格，则会出现以下情况： - 如果对于所有满足 $a < i \le N$ 的整数 $i$，即 $i\in[a+1,N]$，$(i,b)$ 当前是一个空单元格，那么他将摧毁位于 $(a,b)$ 的墙并移动到该处。也就是说，$(a,b)$ 变成空格，他移动到 $(a,b)$。 - 否则，他将无法移动。在这种情况下，即使他没有进行 $N-1$ 次移动，也会立即结束移动。 - 如果目的地 $(a,b)$ 是一个空格，那么他会移动到 $(a,b)$ 。 输出长度为 $N$ 的字符串 $R$，满足以下条件： - 如果他在移动过程中没有失败，可以到达 $(1,i)$，那么 $R$ 的第 $i$ 个字符是 `1`。 - 否则， $R$ 的第 $i$ 个字符为 `0`。 给你 $T$ 个测试用例，请逐一解决。

输入内容由标准输入法提供，格式如下： >$T\\$ >$\text{case}_1\\$ >$\text{case}_2\\$ >$\vdots\\$ >$\text{case}_T\\$ 每个测试用例的格式如下： >$N$ $C\\$ >$S_1\\$ >$S_2\\$ >$\vdots\\$ >$S_N\\$

输出 $T$ 行。 第 $i$ 行应包含第 $i$ 个测试用例的答案。

### 样例 $1$ 解释 此输入包含五个测试用例。 例如，对于第一个测试用例，他可以在如下运动中到达 $(1,3)$ 而不会失败： - 最初，他位于 $(5,3)$。 - 他移动到空格 $(4,2)$。 - $(3,3)$ 是一个有墙的单元格，但是由于 $(4,3),(5,3)$ 目前都是空单元格，他摧毁了 $(3,3)$ 处的墙并移动到 $(3,3)$。 - $(2,3)$ 是一个有墙的单元格，但是由于 $(3,3),(4,3),(5,3)$ 目前都是空格，因此他摧毁了 $(2,3)$ 处的墙，并移动到 $(2,3)$ 处。 - $(1,3)$ 是一个有墙的单元格，但是由于 $(2,3),(3,3),(4,3),(5,3)$ 目前都是空格，因此他摧毁了 $(1,3)$ 处的墙，并移动到 $(1,3)$ 处。 他可以到达 $(1,1),(1,3),(1,4),(1,5)$ 而不会在移动过程中失败，因此打印 `10111`。 ### 数据规模与约定 - $T,N,C$ 是整数 - $1 \le T \le 50000$ - $2 \le N \le 3000$ - $1 \le C \le N$ - $S_i$ 是长度为 $N$ 的字符串，由 `.` 和 `#` 组成 - $S_N$ 的第 $C$ 个字符是 `.` - 对于每个输入，$N^2$ 的总和不超过 $9 \times 10^6$