#include <bits/stdc++.h>

using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

std::vector<int> getVisionPattern1d()
{
    return {1,2,1,2,1,1,3};
}

int getMove1d(std::vector<int> v)
{
    if(v.size()==3){
        for(ll i = 0; i < 3; ++i){
            if(v[i]!=1)return i;
        }
    }
    else if(v.size()==5){
        if(v[0]==3)return 4;
        if(v[4]==3)return 0;
        if(v[0]==2)return 4;
        if(v[4]==2)return 0;
    }
    else{
        if(v[1]==2)return 1;
        return 5;
    }
}

std::vector<std::vector<int>> getVisionPattern2d()
{
    vector<int> p={1,2,1,2,1,1,3};
    ll mx = 3;
    vector<vector<int>> q;
    vector<int> em(p.size(),1);
    for(ll i = 0; i < p.size(); ++i){
        for(ll _ = 1; _ < mx; ++_){
            q.pb(em);
        }
        vll shif(p.size());
        for(ll j = 0; j < p.size(); ++j){
            shif[j] = p[(i+j)%p.size()];
        }
        q.pb(shif);
    }
    return q;
}

std::pair<int, int> getMove2d(std::vector<std::vector<int>> v)
{
    ll mx = 3;
    if(v.size()==3){
        for(ll i = 0; i < 3; ++i){
            for(ll j = 0; j < 3; ++j){
                if(v[i][j]!=1)return {i,j};
            }
        }
        return {0,1};
    }
    else if(v.size()<mx*2+1){
        return {v.size()/2, getMove1d(v[v.size()/2])};
    }
    else{
        ll o = getMove1d(v[mx]);
        if(o==1){
            if(v[0][o+1]==2)return {0,o+1};
            return {mx*2,o+1};
        }
        else{
            if(v[0][o-1]==2)return {0,o-1};
            return {mx*2,o-1};
        }
    }
}