Origami Folding Verification

You are given a rectangular sheet of paper of size n×m in centimeters. The paper is pre‐printed with grid lines that partition it into n×m unit squares. In each square (i, j) a distinct positive integer P[i,j] (1 ≤ P[i,j] ≤ n×m) is written. A classmate has folded this paper by a sequence of folds along the grid lines so that the entire paper becomes a perfect stack of n×m layers (each layer being exactly one unit square) forming a 1×1 square. Moreover, if the layers are numbered from top to bottom as 1, 2, …, n×m, then the number on the top layer is 1, the next is 2, and so on.

The allowed operation is a perfect half fold. In a perfect half fold the paper is divided into two parts by a grid line such that the two parts have the same size along the folding direction. The fold reverses the order of the folded part (in that direction) and places it on top of the other part. Specifically, you may:

• Fold horizontally if the number of rows is even. There are two options:
  • Top downward: Divide the paper into two halves (top and bottom) of equal number of rows. The top half is reversed (its row order is inverted) and placed on top of the bottom half.
  • Bottom upward: The bottom half is reversed and placed on top of the top half.
• Fold vertically if the number of columns is even. There are two options:
  • Left rightwards: Divide the paper into left and right halves of equal number of columns. The left half is reversed (its column order is inverted) and placed on top of the right half.
  • Right leftwards: The right half is reversed and placed on top of the left half.

The folds may be applied in any order provided the corresponding dimension is even at that stage. At the end, the paper must be folded into a single cell whose stack (from top to bottom) is exactly [1, 2, 3, …, n×m]. Note that the paper must not be torn or overlapped incorrectly: every fold must be a perfect half fold as described.

Your task is to determine, given the initial n×m matrix of numbers, whether there is a sequence of allowed folds that will result in a stack with layers in ascending order from top to bottom.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10) indicating the number of rows and columns respectively. Each of the next n lines contains m space‐separated integers representing the matrix P. It is guaranteed that all numbers are distinct and lie between 1 and n×m.

outputFormat

Output YES if there exists a sequence of perfect half folds that results in a 1×1 stack whose layers (from top to bottom) are exactly 1, 2, …, n×m. Otherwise, output NO.

sample

2 2
1 3
2 4

YES