This page is still under construction.

Parts of this page are still being built. What you see may change.

Matrix Transformation

Time limit1sMemory limit128 MB

Summary
Decide whether repeated plus-or-minus-one updates on adjacent cell pairs can turn each matrix into all zeros.
Level

Medium6 of 10

Topics
Math, Greedy
Solved
No attempts yet

Problem

You have an integer matrix AA with RR rows and CC columns, so each of the RR rows holds CC integers.

Two integers are adjacent when the cells holding them share an edge. For example, in the grid below

0 1 2
3 4 5
6 7 8

(0,1)(0, 1), (4,5)(4, 5), (1,4)(1, 4), (5,2)(5, 2) are adjacent, but (0,4)(0, 4), (2,6)(2, 6), (5,7)(5, 7) are not.

Only one kind of operation is allowed on the matrix. In one step you select two adjacent cells and either increase both values by 1 or decrease both values by 1. Given a matrix, determine whether repeating this operation can turn it into a zero matrix. A zero matrix is one whose every entry is 0.

Input

The first line contains a positive integer nn, the number of matrices.

Each matrix starts with a line holding RR (2≤R≤302 \le R \le 30) and CC (2≤C≤302 \le C \le 30) separated by a single space. Each of the next RR lines contains CC integers. Every one of these integers is between −20-20 and 2020 inclusive.

Each input matrix has at least one non-zero value.

Output

For each matrix print YES on its own line if it can be turned into a zero matrix, and NO otherwise. Use capital letters only.

Examples1

  1. Example 1

    Input
    6
3 3
-2 2 2
1 1 0
2 -2 -2
3 3
-1 0 1
-2 -1 1
0 1 2
3 3
-1 0 1
0 2 -1
-1 1 2
3 3
-1 2 1
-1 -1 -3
1 1 -1
2 3
0 -2 3
1 3 1
2 3
3 1 1
2 0 1
    Expected output
    YES
NO
NO
YES
NO
YES