Problem: Problem statement

There is a rectangular piece of paper divided in a grid with a height of $ H $ squares and a width of $ W $ squares. The integer $ i \ times W + j $ is written in the cell of the $ i $ line from the top and the $ j $ column from the left counting from $ 0 $. An example of $ H = 2 and W = 3 $ is shown in the figure below.

<image>

AOR Ika-chan performed the following operations on this paper in order.

1. Fold it repeatedly along the dividing line of the square until it reaches the area of ​​$ 1 $ square. The folding lines, mountains and valleys, and the order at this time are arbitrary. You can fold it in any way that does not tear the paper.
2. Cut off the $ 4 $ edge and divide it into $ H \ times W $ sheets of paper.
3. Turn over from the top to create a sequence $ S $ in which the written integers are arranged.



For example, if you fold it and then cut it as shown in the figure below, you will get $ 4, 3, 0, 5, 2, 1 $ as $ S $. In this way, it is possible to fold it so that it can be inserted between them.

<image>
<image>

You received a sequence of $ S $ from AOR Ika-chan. However, I don't trust AOR Ika-chan, so I want to make sure this is the real thing. Write a program that outputs "YES" if there is a paper folding method that matches $ S $, and "NO" if not.

Input constraints

$ 1 \ le H, W \ le 500 $
$ S $ contains integers from $ 0 $ to $ H \ times W --1 $ in increments of $ 1 $

sample

Sample input 1


14
0 1 2 3


Sample output 1


YES YES


<image>

Sample input 2


twenty three
4 3 0 5 2 1


Sample output 2


YES YES


This is an example in the problem statement.

Sample input 3


14
0 2 1 3


Sample output 3


NO


Sample input 4


twenty two
0 1 3 2


Sample output 4


YES YES


Fold it in half for $ 2 $.



input

$ H \ W $
$ S_0 \ cdots S_ {HW-1} $

output

Print "YES" or "NO" on the $ 1 $ line.

Example

Input

1 4
0 1 2 3


Output

YES

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int H,W;
int t[250000];
int u[250001];
bool rh[250001];
bool rw[250001];

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

bool solve(){
  int sy=t[0]/W;
  int sx=t[0]%W;
  for(int i=1;i<H*W;i++){
    int y=t[i]/W;
    int x=t[i]%W;
    if( abs(y-sy)%2 == 1 )rh[ t[i] ]=true;
    if( abs(x-sx)%2 == 1 )rw[ t[i] ]=true;
  }
  
  int last=-1;
  stack<int> total;
  stack<int> st[4];
  
  for(int i=0;i<H*W;i++){
    int n=t[i];
    vector<P> v;
    for(int dir=0;dir<4;dir++){
      int y=n/W+dy[dir];
      int x=n%W+dx[dir];
      if(y<0||H<=y)continue;
      if(x<0||W<=x)continue;
      int m=y*W+x;
      v.push_back(P(u[m],dir));
    }
    
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    
    for(int j=0;j<(int)v.size();j++){
      int dir=v[j].second;
      int y=n/W+dy[dir];
      int x=n%W+dx[dir];
      int m=y*W+x;
      int ndir=dir;
      if(rh[n]&&ndir%2==0)ndir=(ndir+2)%4;
      if(rw[n]&&ndir%2==1)ndir=(ndir+2)%4;
      stack<int> &w=st[ndir];
      if(u[m]<i){
        //        cout<<"pop  "<<n<<' '<<m<<' '<<ndir<<endl;
        if(w.empty()||w.top()!=n)return false;
        w.pop();
        //        if(total.top()<last)return false;
        total.pop();
        last=i;
      }
    }
    
    for(int j=0;j<(int)v.size();j++){
      int dir=v[j].second;
      int y=n/W+dy[dir];
      int x=n%W+dx[dir];
      int m=y*W+x;
      int ndir=dir;
      if(rh[n]&&ndir%2==0)ndir=(ndir+2)%4;
      if(rw[n]&&ndir%2==1)ndir=(ndir+2)%4;
      stack<int> &w=st[ndir];
      if(u[m]>=i){
        //        cout<<"push "<<n<<' '<<m<<' '<<ndir<<endl;
        w.push(m);
        total.push(i);
      }
    }
  }
  return true;
}

int main(){
  cin>>H>>W;
  for(int i=0;i<H*W;i++){
    cin>>t[i];
    u[t[i]]=i;
  }
  cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}