Ordered Array

Interview

Time limit2sMemory limit128 MB

Summary
Check whether a given 2D array satisfies the Monge-like inequality A[i][j]+A[k][l] ≤ A[i][l]+A[k][j] for all row and column pairs, using adjacent checks only.
Level

Medium4 of 10

Topics
Matrix, Implementation, Brute force
Solved
No attempts yet

Problem

There is an N×M two-dimensional array A of integers. The array is ordered if, for every two rows i, k and two columns j, l such that 1 ≤ i < k ≤ N and 1 ≤ j < l ≤ M, the inequality A[i][j] + A[k][l] ≤ A[i][l] + A[k][j] always holds.

Given a two-dimensional array, determine whether it is ordered.

Input

The first line contains the number of arrays T.

Then the T arrays are given in order. For each array, the first line contains two integers N and M. Each of the next N lines contains M integers. The elements are given in the order A[1][1], A[1][2], …, A[1][M], A[2][1], …, A[N][M].

Output

For each array, output one answer per line in the same order as the input.

Print YES if the array is ordered, and NO otherwise. The letter case must match exactly.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 500
  • -1,000,000 ≤ A[i][j] ≤ 1,000,000

Examples1

  1. Example 1

    Input
    2
2 3
1 1 1
1 1 1
3 2
1 1
1 2
1 1
    Expected output
    YES
NO