#include <bits/stdc++.h>
#include "squares.h"
//#include "grader.cpp"
using namespace std;
vector<vector<int>> adj;
vector<pair<int, int>> edges;
vector<bool> visited;
int id = 0;
vector<int> order;
string s = "0000000001111111111011111111001111111010111111100011111101101111110100111111001011111100001111101110111110110011111010101111101000111110011011111001001111100010111110000011110111101110011110110101111011000111101011011110101001111010010111101000011110011101111001100111100101011110010001111000110111100010011110000101111000000111011101011101110001110110110111011010011101100101110110000111010110011101010101110101000111010011011101001001110100010111010000011100111001101011100110001110010110111001010011100100101110010000111000110011100010101110001000111000011011100001001110000010111000000011011011001101101010110110100011011001001101100010110110000011010110101100011010101001101010010110101000011010011001101001010110100100011010001001101000010110100000011001100101100110000110010101011001010001100100100110010001011001000001100011000101001100010010110001000011000010101100001000110000010011000000101100000000101010101000101010010010101000001010010100100001010001000101000010010100000001001001000100100000010001000001000010000000000";
void dfs(int node)
{
while (!adj[node].empty())
{
int ed = adj[node].back();
adj[node].pop_back();
if (visited[ed])
{
continue;
}
visited[ed] = true;
dfs(edges[ed].second);
}
order.emplace_back(node);
}
void get_de_brujin_sequence(int k)
{
adj.resize(1 << (k - 1));
for (int i = 0; i < (1 << (k - 1)); i++)
{
int zw = (i & ((1 << (k - 2)) - 1));
zw <<= 1;
adj[i].emplace_back(id);
edges.emplace_back(i, zw);
adj[i].emplace_back(id + 1);
edges.emplace_back(i, zw + 1);
id += 2;
}
visited.resize(edges.size());
dfs(0);
reverse(order.begin(), order.end());
for (int i = k - 2; i > 0; i--)
{
if (order[0] & (1 << i)) cout << 1;
else cout << 0;
}
for (auto i : order) cout << (i & 1);
}
std::vector<int> paint(int n) {
std::vector<int> labels(n + 1, 1);
for (int i = 0; i < n; i++) labels[i] = (s[i] - '0');
labels[n] = 10;
return labels;
}
int find_location(int n, std::vector<int> c) {
int ct = 0;
for (int i = 0; i < 10; i++) if (c[i] == -1) ct++;
if (ct > 0)
{
return n + ct - 10;
}
for (int i = 0; i < 114514; i++)
{
bool b = true;
for (int j = 0; j < 10; j++)
{
if (c[j] + '0' != s[i + j]) b = false;
}
if (!b) continue;
return i;
}
return 0;
}
/*
int main()
{
get_de_brujin_sequence(10);
}
*/
