#include <bits/stdc++.h>
using namespace std;
namespace {
const int B = 3;
struct state {
bool none;
int written;
int bit;
};
int state_to_number(state st) {
if (st.none) {
st.written = 0;
}
return (B + 1) * st.bit + (st.written + !st.none);
}
state number_to_state(int x) {
state st;
st.bit = x / (B + 1);
x %= B + 1;
st.none = x == 0;
if (!st.none) {
st.written = x - 1;
}
return st;
}
vector<int> in_base(int x, int pad = 0) {
vector<int> ans;
while (x) {
ans.push_back(exchange(x, x / B) % B);
}
while (int(ans.size()) < pad) {
ans.push_back(0);
}
reverse(ans.begin(), ans.end());
return ans;
}
} // namespace
vector<vector<int>> devise_strategy(int N) {
vector<int> a = in_base(N);
vector<vector<int>> ans;
for (int i = 0; i < int((B + 1) * a.size()); ++i) {
ans.emplace_back();
state st = number_to_state(i);
ans.back().push_back(!st.none);
for (int j = 1; j <= N; ++j) {
int push = 1;
state wr = st;
if (st.none) {
wr.none = 0;
wr.written = in_base(j, a.size())[wr.bit];
} else {
if (in_base(j, a.size())[wr.bit] != wr.written) {
push = 0;
ans.back().push_back(-1 - (in_base(j, a.size())[wr.bit] < wr.written));
} else {
wr.none = 1;
wr.bit = min(wr.bit + 1, int(a.size()) - 1);
}
}
if (push) {
ans.back().push_back(state_to_number(wr));
}
}
}
return ans;
}
