#include <bits/stdc++.h>
using namespace std;
//author: Hubert Lukasik
int state_to_board[28] = {-10, 1, 2, 3, 4, 5, 6, 7, -10, -10, -10, 8, 9, 10, 11, 12, 13, 14, 15, -10, -10, 16, 17, 18, 19, 20, 21, 22};
int board_to_state[23] = {-1, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15, 16, 17, 18, 21, 22, 23, 24, 25, 26, 27};
int trenary(int x, int which_digit)
{
string res = "";
while(x > 0)
{
res = char('0' + x % 3) + res;
x = x / 3;
}
while(res.length() < 8)
res = '0' + res;
return int(res[which_digit - 1] - '0');
}
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> ans;
vector <int> pom;
for(int i = 0; i < N+1; ++i)
pom.push_back(-10);
for(int i = 0; i <= 22; ++i)
{
ans.push_back(pom);
}
//column 0
for(int i = 0; i <= 7; ++i)
ans[i][0] = i % 2;
for(int i = 8; i <= 22; ++i)
ans[i][0] = (i % 2 + 1) % 2;
//row 0
ans[0][1] = -1;
ans[0][N] = -2;
for(int n = 2; n < N; ++n)
ans[0][n] = state_to_board[trenary(n, 1)*10 + 1];
//the rest of rows
for(int r = 1; r <= 22; ++r)
{
if(ans[r][0] == 0)
{
ans[r][1] = -1;
ans[r][N] = -2;
}
else
{
ans[r][1] = -2;
ans[r][N] = -1;
}
int prev_pos = board_to_state[r] % 10;
int prev_digit = board_to_state[r] / 10;
for(int n = 2; n < N; ++n)
{
int digit = trenary(n, prev_pos);
if(digit < prev_digit)
{
if(ans[r][0] == 0)
ans[r][n] = -1;
else
ans[r][n] = -2;
}
else if(digit > prev_digit)
{
if(ans[r][0] == 0)
ans[r][n] = -2;
else
ans[r][n] = -1;
}
else
{
int act_digit = trenary(n, prev_pos + 1);
int state = 10 * act_digit + prev_pos + 1;
if(state == 8)
{
if(ans[r][0] == 0)
ans[r][n] = -1;
else
ans[r][n] = -2;
}
else if(state == 28)
{
if(ans[r][0] == 0)
ans[r][n] = -2;
else
ans[r][n] = -1;
}
else
ans[r][n] = state_to_board[state];
}
}
}
return ans;
}
