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

题面

给你一个为 $n$ 列数为 $m$ 的网格。我们用 $(i, j)$ 来表示 $i$ ( $1\le i\le n$ )行和 $j$ ( $1\le j\le m$ )列上的方格，用 $a_{ij}$ 来表示其中的数字。所有数字都等于 $k$ 或 $-k$ 。

您从 $(1, 1)$ 开始，每次向下或向右移动一格。最后，您希望在 $(n, m)$ 处结束。

是否有可能这样移动，使得写在所有已访问单元格（包括 $a_{11}$ 和 $a_{nm}$ ）中的值之和为 $s$ ？

格式

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10^4$ )。测试用例说明如下。

每个测试用例的第一行包含四个整数 $n$ , $m$ , $k$ 和 $s$ ( $1 \le n, m \le 1000$ ) - 网格大小,( $1 \leq k \leq 10^4$ ) - 网格内出现的数，( $1 \leq s \leq 10^4$ ) - 要求最终路径之和。

接下来的每行 $n$ 都包含 $m$ 个整数。第 $i$ 行的第 $j$ 个整数是 $a_{ij}$ （ $a_{ij} = k$ 或 $-k$ ）--单元格 $(i, j)$ 中的元素。

保证所有测试用例的$n\cdot m$ 之和不超过 $10^6$ 。

输出

对于每个测试用例，如果存在从左上角到右下角相加等于 $s$ 的路径，则打印 "YES"，否则打印 "NO"。

样例

5
1 1 1 0
1
1 2 2 0
2 -2
1 4 1 0
1 -1 1 -1
3 4 10 -40
10 -10 -10 -10
-10 10 10 -10
10 10 10 -10
3 4 1 0
1 -1 1 1
-1 1 -1 1
1 -1 1 1

NO
YES
YES
YES
NO

Limitation

1s, 1024KiB for each test case.