#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
const int N = 2e3 + 5;
vec<int> ord;
arr<bool, N> vs;
void intl() {
ord.clear(), vs.fill(false);
}
void dfs(int k, int u = 0) {
vs[u] = true, ord.push_back(u);
int v = (2 * u + 1) % (1 << k), w = (2 * u) % (1 << k);
if (!vs[v]) dfs(k, v);
else if (!vs[w]) dfs(k, w);
}
vec<int> slv(int n) {
int k = min(10, n);
intl(), dfs(k);
vec<int> ans;
auto on = [](int x, int i)->bool { return x & (1 << i); };
for (int i = k - 1; i >= 0; i--)
ans.push_back(on(ord[0], i));
for (int i = 1; i <= n - k; i++)
ans.push_back(on(ord[i], 0));
return ans;
}
vec<int> paint(int n) {
vec<int> ans = slv(n);
int k = min(10, n);
ans.push_back(k);
return ans;
}
int find_location(int n, vec<int> rq) {
vec<int> sq = slv(n);
int k = min(10, n);
for (int i = 0; i < n; i++) {
vec<int> cr;
for (int j = i; j <= i + k - 1; j++)
cr.push_back((j >= n) ? -1 : sq[j]);
if (cr == rq) return i;
}
assert(false); return -1;
}
