#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
const ll MOD = 1e9 + 7;
void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }
int ipow(int a, int n) {
if (n == 0) return 1;
int x = ipow(a, n/2);
if (n % 2 == 0) return x*x;
return x*x*a;
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
for (auto elem : v)
stream << elem << " ";
return stream;
}
template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
for(auto &elem : v)
stream >> elem;
return stream;
}
std::vector<std::vector<int>> devise_strategy(int N) {
vvi s(25, vi(N+1));
s[0][0] = 0;
for (int i = 1; i <= N; i++) {
s[0][i] = ((i>>12)&1)+1;
}
for (int i = 1; i <= 24; i++) {
int bit = (((i+1)/2)-1);
s[i][0] = bit % 2 == 0;
for (int j = 1; j <= N; j++) {
// if (bit == 12) {
// }
if (((j>>(12-bit))&1) ) {
if (i % 2 == 1) s[i][j] = -(bit % 2)-1;
else if (bit != 11)
s[i][j] = (bit+2)*2 - 1 + ((j>>((12-bit)-1))&1);
else {
if (((j>>(12-bit-1))&1))
s[i][j] = -(bit % 2)-1;
else
s[i][j] = -(bit % 2 == 0)-1;
}
} else {
if (i % 2 == 0) s[i][j] = -(bit % 2 == 0)-1;
else if (bit != 11)
s[i][j] = (bit+2)*2 - 1 + ((j>>((12-bit)-1))&1);
else {
if (((j>>(12-bit-1))&1))
s[i][j] = -(bit % 2 == 0)-1;
else
s[i][j] = -(bit % 2)-1;
}
}
if (s[i][j] > 24) s[i][j] = 2;
}
}
// for (int i = 0; i <= 25; i++) cout << s[i] << endl;
return s;
}
