import java.util.ArrayList;
public class squares {
private int[] visited = null, reverse_map = null;
private ArrayList<Integer> euler_path = null, labels = null;
void dfs(int x) {
while (visited[x] < 2) {
dfs((x >> 1) | (visited[x]++ << 8));
}
euler_path.add(x);
}
void generate_map() {
visited = new int[512];
euler_path = new ArrayList<>();
dfs(0);
labels = new ArrayList<>();
for (int i = 0; i < 8; i++) {
labels.add(0);
}
reverse_map = new int[1024];
for (int i = 0; i < euler_path.size() - 1; i++) {
labels.add(euler_path.get(i) & 1);
reverse_map[(euler_path.get(i) << 1) | (euler_path.get(i + 1) & 1)] = i;
}
}
int[] paint(int n) {
if (euler_path == null) {
generate_map();
}
int[] painting = new int[n + 1];
for (int i = 0; i < n; i++) {
painting[i] = labels.get(i);
}
painting[n] = 10;
return painting;
}
int find_location(int n, int[] c) {
if (euler_path == null) {
generate_map();
}
int val = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] == -1) return n - i;
val = (val << 1) | c[i];
}
return reverse_map[val];
}
}
