#include "egybabu.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn=1001;
int merre[maxn][maxn];

void init(int N, std::vector<std::vector<int>> table) {
    vector<vector<int>> dp(N+1,vector<int>(N+1));
    memset(merre,0,sizeof(merre));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i+j==2)continue;
            if((i+j)&1)dp[i][j]=max(dp[i-1][j],dp[i][j-1])+table[i-1][j-1];
            else dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
        }
    }
    for(int i=1;i<=N;i++)merre[N][i]=1;
    for(int i=1;i<N;i++){
        for(int j=1;j<N;j++){
            if((i+j)&1){
                merre[i][j]=(dp[i][j+1]<dp[i+1][j]);
                dp[i][j]=min(dp[i][j+1],dp[i+1][j]);
            }else{
                merre[i][j]=(dp[i][j+1]>dp[i+1][j]);
                dp[i][j]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
}

int step(int row, int col) {
    return merre[row+1][col+1];
}