C. Dominance
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

To help Noumi Kudryavka study math, you, as the leader of Little Busters, come up with a game on matrices. The initial matrix has $$$n$$$ rows and $$$m$$$ columns and contains $$$n\cdot m$$$ distinct integers from $$$1$$$ to $$$n\cdot m$$$.

  • The $$$i$$$-th row is dominant if and only if for all $$$1\le j\le m$$$, $$$a_{i,j}$$$ is the minimum value of the $$$j$$$-th column.
  • The $$$j$$$-th column is dominant if and only if for all $$$1\le i\le n$$$, $$$a_{i,j}$$$ is the maximum value of the $$$i$$$-th row.

If a row or column is dominant, Kudryavka can remove the row or column, and the remaining elements keep their order. If Kudryavka can remove the entire matrix by this operation, then you consider the matrix to be good.

You're lazy to generate such matrices, and you assign the work to others. However, you must write a checker to confirm the matrices are good.

Input

Each test contains multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^6$$$, $$$1\le n\cdot m\le10^6$$$) — the number of the rows and columns in the matrix.

The $$$i$$$-th line of the next $$$n$$$ lines of each test case contains $$$m$$$ integers $$$a_{i,1},a_{i,2},\dots,a_{i,m}$$$ ($$$1\le a_{i,j}\le n\cdot m$$$). It is guaranteed that $$$a_{i,j}$$$ are pairwise distinct.

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output "YES" if the matrix is good; otherwise, output "NO". You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
2
2 2
1 2
3 4
2 2
1 4
3 2
Output
YES
NO