该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个二维迷宫，该迷宫将被视为一个大小为 $N×M$ 的网格。一些单元格中有障碍物，无法到达，用1 表示；能到达的点则用0表示。迷宫的起点是 $(1,1)$，终点是$(1,M)$。迷宫当然是能从起点走到终点的，所以我们保证迷宫的第一列和最后一列没有障碍物，并且一定存在一条路径能从 起点$(1,1)$走到终点$(1,M)$。

您可以使用任意次移动操作从起点到达终点。 移动操作包括：

• W 向上走一步，即从$(x,y)$ 走到 $(x + 1, y)$
• S 向下走一步，即从$(x,y)$ 走到 $(x - 1, y)$
• 向右走一步，即从$(x,y)$走到$(x,y + 1)$

如果题目到这里结束未免太简单了，所以我们引入一个视距的概念。给定视距K，当您在点$(X,Y)$时，您能看见第$1$列到第$Y + K$ 列所有网格信息，用数学语言表示为$${(U, V) \mid 1 \leq U \leq N, Y \leq V \leq \min (Y+K, M)}$$ 在我们能看到的范围内，如果我们提前知道执行一次移动操作会使我们走不到终点，我们当然就不会选择这么走。但是即使这样，最终仍可能走进“死胡同”，无法到达终点。

如果可能走进“死胡同”，输出Yes,否则输出No。

输入格式

输入的第一行包含一个正整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。每个测试用例如下所述。

每个测试用例的第一行包含三个正整数 $N, M, K$（$2 \le N, M, N \cdot M \le 10^6$，$1 \le K \le M - 1$），分别表示地图的尺寸参数和可见范围参数。

接下来的 $N$ 行中每行包含一个长度为 $M$ 的二进制字符串 $s_i$，表示迷宫第 $i$ 行的障碍物信息。这里，当且仅当在位置 $(i, j)$ 有障碍物时，$s_{i,j} = 1$。输入保证第一列和最后一列中没有障碍物，且从 $(1,1)$ 到 $(1,M)$ 存在一条路径。

保证所有测试用例中 $N \cdot M$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，如果存在满足问题所述条件，则在一行中Yes；否则，输出 No。

输入输出样例

6
3 5 2
00010
01110
00000
3 5 3
00010
01110
00000
3 5 2
01000
01110
00000
3 5 2
00000
01110
00000
3 5 2
01010
01110
00000
5 5 2
00000
00110
00010
01010
00010

Yes
No
No
No
No
Yes

提示

样例解释 对于第一个测试样本，位于$(1,1)$处时的可见度信息可以用以下矩阵表示：

000??
011??
000??

根据这些信息，不能排除从$(1,2)$开始到达$(1,5)$的可能性。然而事实上无法从$(1,2)$移动到$(1,5)$。除最后一个测试样本外，其他测试样本中，不会因为视线限制而无法到达终点，也不会遇到”死胡同“。