Under construction

Still being built. Things may change

Matrix Transformation

Interview

Time limit1sMemory limit1024 MB

Summary
Given an integer grid, decide whether repeatedly adding or subtracting 1 from both cells of an adjacent pair can turn every cell into zero.
Level

Medium4 of 10

Topics
Math, Matrix, Implementation
Solved
No attempts yet

Problem

You have an integer matrix A with R rows and C columns. Each of the R rows contains C integers. Two integers are adjacent if their cells share an edge. For example, in the grid below, (0, 1), (4, 5), (1, 4), and (5, 2) are adjacent, but (0, 4), (2, 6), and (5, 7) are not.

You may perform only one kind of operation. In each step, you select two adjacent cells and either increase both values by 1 or decrease both values by 1.

Determine whether the matrix can be transformed into a zero matrix, where every entry is zero, using these operations.

Input

The first line contains a positive integer n, the number of matrices. Each matrix starts with a line containing R and C separated by a single space (2≤R≤302 \le R \le 30, 2≤C≤302 \le C \le 30). Each of the next R lines contains C integers, each between −20-20 and +20+20 inclusive. Each input matrix has at least one nonzero value.

Output

For each matrix (test case), first print "Case #i:", where i is the test case number starting at 1. Then print "YES" if the matrix can be transformed into a zero matrix, or "NO" otherwise. Leave a blank line after the output for each test case. Follow the format of the sample output.

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
    Case #1: YES

Case #2: NO

Case #3: NO

Case #4: YES

Case #5: NO

Case #6: YES