#include "prison.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<int> s{1666, 555, 185, 61, 20, 9, 4, 2};
    vector<int> cut{3, 3, 3, 3, 3, 2, 2, 1};
    const int m = 20;
    
    vector a(m + 1, vector<int>(N + 1));

    for (int i = 0; i <= m; ++i) {
        int l = 0, b = i;
        while (b > 0) {
            b -= cut[l++];
        }
        a[i][0] = l % 2 == 0;
        int me = a[i][0] == 0 ? -1 : -2;
        int oth = -1 + -2 - me;
        for (int x = 1; x <= N; ++x) {
            int y = x - 1, last = -1;
            for (int j = 0; j < l; ++j) {
                if (y == 0 || y == s[j] * cut[j] + 1) {
                    y = y == 0 ? -1 : -2;
                    break;
                } else {
                    last = (y - 1) / s[j];
                    y = (y - 1) % s[j];
                }
            }
            if (y < 0) {
                a[i][x] = y == -1 ? me : oth;
                continue;
            }
            if (l > 0) {
                int other = b + cut[l - 1] - 1;
                if (last != other) {
                    if (last < other) {
                        a[i][x] = me;
                    } else {
                        a[i][x] = oth;
                    }
                    continue;
                }
            }
            if (y == 0) {
                a[i][x] = me;
            } else if (l == size(cut) || y == s[l] * cut[l] + 1) {
                a[i][x] = oth;
            } else {
                y -= 1;
                a[i][x] = accumulate(cut.begin(), cut.begin() + l, 0) + 1 + (y / s[l]);
            }
        }
    }


    for (auto &x : a) {
        for (auto &y : x) {
            y = min(y, m);
        }
    }

    return a;
}