#include "lockpicking.h"
#include <bits/stdc++.h>
using namespace std;
void construct_card (int n, vector <int> a, vector <vector <int>> S) {
/* long long s = n;
for (int i = 0; i < n; i++) {
s = (1004 * s + a[i]) % 10000007;
s = (1004 * s + S[i][0]) % 10000007;
s = (1004 * s + S[i][1]) % 10000007;
}
assert(s == 8971510);*/
vector <array <int, 2>> trie = {{-1, -1}};
vector <int> node = {0};
vector <int> val = {0};
for (int i = 0; i < n; i++) {
int x = i;
vector <int> s;
for (int j = 0; j + 2 < n; j++) {
s.push_back(a[x]);
x = S[x][0];
}
int cur = 0;
for (auto j : s) {
if (trie[cur][j] == -1) {
trie[cur][j] = (int)trie.size();
trie.push_back({-1, -1});
node.push_back(0);
val.push_back(-1);
}
cur = trie[cur][j];
node[cur] = x;
val[cur] = j;
}
}
//n^2 so far
int m = trie.size() + n;
vector <vector <int>> T(m);
vector <int> b(m);
for (int i = 0; i < n; i++) {
b[i] = a[i];
T[i] = S[i];
}
for (int i = n; i < m; i++) {
T[i] = {trie[i - n][0], trie[i - n][1]};
if (T[i][0] == -1 && T[i][1] == -1) {
//if (i == 10) cout << val[i - n] << " || +" << node[i - n] << '\n';
T[i][a[node[i - n]]] = S[node[i - n]][0];
T[i][1 - a[node[i - n]]] = i;
b[i] = 0;
} else if (T[i][0] == -1) {
T[i][1] += n; T[i][0] = i;
b[i] = 0;
} else if (T[i][1] == -1) {
T[i][0] += n; T[i][1] = i;
b[i] = 0;
} else {
T[i][0] += n; T[i][1] += n;
b[i] = 0;
}
}
/* for (int i = 0; i < n; i++) {
int x = i, y = n;
int cnt = 0;
for (int itr = 1; itr <= 10000; itr++) {
int g = a[x], h = b[y];
cnt += g != h;
cout << cnt << " " << x << " " << y << ": " << g << " " << h << '\n';
if (cnt >= n) {
assert(0);
}
x = S[x][h], y = T[y][g];
}
}*/
define_states(m, b, T, n);
}
