#include "datalab.h"
#include <vector>

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

using namespace std;

const int B = 90, N = 8200;

int n, pos[N], qe, L[N], R[N], f[N << 1], cnt, w[N];

bool ban[N];

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

void inline merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	cnt += 1;
	f[x] = y;
}

void inline mg(int x, int y, int o) {
	if (!o) {
		merge(x, y), merge(x + n, y + n);
	} else {
		merge(x, y + n), merge(x + n, y);
	}
}

vector<int> solve(int k,int LIMIT){
	n = k;
	cnt = 0; qe = 0;
	memset(L, -1, sizeof L);
	for (int i = 0; i < k; i++) {
		pos[i] = i / B + 1;
		if (L[pos[i]] == -1) L[pos[i]] = i, w[pos[i]] = i;
		R[pos[i]] = i;
	}
	
	for (int i = 0; i < 2 * k; i++) f[i] = i;
	mg(k - 2, k - 1, 1);
	int tot = pos[k - 1];
//	for (int i = 1; i < tot; i++) {
//		bitset<8192> T;
//		T[R[i]] = 1; qe++;
//		bitset<8192> A = Add(T, T);
//		if (A[R[i] + 2] == 1) mg(R[i], R[i] + 1, 1);
//		else mg(R[i], R[i] + 1, 0);	
//	}
	
	while (cnt < 16382) {
		bitset<8192> T;
		for (int i = 1; i <= tot; i++) {
			if (ban[i] || w[i] == R[i] + 1 || w[i] >= k - 2) continue;
			T[w[i]] = 1;
		}
		++qe;
		bitset<8192> A = Add(T, T);
		for (int i = 1; i <= tot; i++) {
			if (ban[i] || w[i] == R[i] + 1 || w[i] >= k - 2) continue;
			if (i < tot && A[R[i] + 2] && (ban[i + 1] || w[i + 1] == R[i + 1] + 1 || w[i + 1] >= k - 2 || w[i + 1] != L[i + 1])) {
				for (int j = w[i] + 1; j <= R[i] + 1; j++)
					mg(w[i], j, 1);
				ban[i] = 1;
				break;
			}
			if (i < tot && !A[R[i] + 2] && A[R[i] + 1] && w[i + 1] == L[i + 1] && !(ban[i + 1] || w[i + 1] == R[i + 1] + 1 || w[i + 1] >= k - 2)) {
				for (int j = w[i] + 1; j <= R[i] + 1; j++)
					mg(w[i], j, 1);
				ban[i] = 1;
				break;
			}
			int ps = -1;
			for (int j = w[i] + 1; j <= R[i] + 1; j++)
				if (A[j]) ps = j;
			for (int j = w[i] + 1; j < ps; j++)
				mg(w[i], j, 1);
			mg(w[i], ps, 0);
			w[i] = ps;
		}
	}
	vector<int> ans;

	for (int i = 0; i < k; i++)
		if (find(i) == find(k - 1 + k)) ans.pb(-1);
		else ans.pb(1);
	return ans;
}