give cpp optimum solution for :
Beauty of the mountains

time limit per test

2 seconds

memory limit per test

256 megabytes

Nikita loves mountains and has finally decided to visit the Berlyand mountain range! The range was so beautiful that Nikita decided to capture it on a map. The map is a table of nn rows and mm columns, with each cell containing a non-negative integer representing the height of the mountain.

He also noticed that mountains come in two types:

With snowy caps.

Without snowy caps.

Nikita is a very pragmatic person. He wants the sum of the heights of the mountains with snowy caps to be equal to the sum of the heights of the mountains without them. He has arranged with the mayor of Berlyand, Polikarp Polikarpovich, to allow him to transform the landscape.

Nikita can perform transformations on submatrices of size k×kk×k as follows: he can add an integer constant cc to the heights of the mountains within this area, but the type of the mountain remains unchanged. Nikita can choose the constant cc independently for each transformation. Note that cc can be negative.

Before making the transformations, Nikita asks you to find out if it is possible to achieve equality of the sums, or if it is impossible. It doesn't matter at what cost, even if the mountains turn into canyons and have negative heights.

If only one type of mountain is represented on the map, then the sum of the heights of the other type of mountain is considered to be zero.

Input

Each test consists of several test cases. The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases. This is followed by a description of test cases.

The first line of each test case contains three integers n,m,kn,m,k (1≤n,m≤500,1≤k≤min(n,m)1≤n,m≤500,1≤k≤min(n,m)).

The next nn lines of each test case contain mm integers aijaij (0≤aij≤1090≤aij≤109) — the initial heights of the mountains.

The next nn binary strings of length mm for each test case determine the type of mountain, '00' — with snowy caps, '11' — without them.

It is guaranteed that the sum of n⋅mn⋅m for all test cases does not exceed 250000250000.

Output

For each test case, output "YES" without quotes if it is possible to equalize the sums of the mountain heights, otherwise output "NO" without quotes. You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Example

Input

Copy

8

3 3 2

7 11 3

4 2 3

0 1 15

100

010

000

4 4 3

123 413 24 233

123 42 0 216

22 1 1 53

427 763 22 6

0101

1111

1010

0101

3 3 2

2 1 1

1 1 2

1 5 4

010

101

010

3 3 2

2 1 1

1 1 2

1 5 3

010

101

010

3 4 3

46 49 50 1

19 30 23 12

30 25 1 46

1000

0100

0010

5 4 4

39 30 0 17

22 42 30 13

10 44 46 35

12 19 9 39

21 0 45 40

1000

1111

0011

0111

1100

2 2 2

3 4

6 7

00

00

2 2 2

0 0

2 0

01

00

Output

Copy

YES NO YES NO YES NO YES YES

Note

The mountain array from the first test case looks like this:

Initially, the sum of the heights of the mountains with snowy caps is 11+3+4+3+0+1+15=3711+3+4+3+0+1+15=37, and without them is 7+2=97+2=9.

To equalize these sums, we can perform two transformations:

First transformation:

Note that the constant cc can be negative.

After the first transformation, the mountain array looks like this:

Second transformation:

As a result, the mountain array looks like this:

The sum of the heights of the mountains with snowy caps is 17+9+9−16−20−19+15=−517+9+9−16−20−19+15=−5, and without them is 7−12=−57−12=−5, thus the answer is YES.