#include"datalab.h"
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#define N 8191
using namespace std;
bitset<N+1>A;
bitset<N+1>B;
int sz,block[N+1],ps[N+1],cl[N+1],cls[N+1];
bool vis[N+1];
vector<int>solve(int k,int LIMIT)
{
    int rt,d;
    bool op;
    vector<int>p(k);
    p[k-2]=-1,p[k-1]=1,sz=sqrt(k-2);
    for (int i=0;i<=k-3;++i) block[i]=i/sz;
    for (int i=0;i<=block[k-3];++i) ps[i]=i*sz;
    while (1)
    {
	A.reset(),op=0;
	for (int i=0;i<=block[k-3];++i)
	    if (ps[i]<=min((i+1)*sz-1,k-3))
		A[ps[i]]=op=1;
	if (!op) break;
	B=Add(A,A);
	for (int i=0;i<=block[k-3];++i)
	    if (ps[i]<=min((i+1)*sz-1,k-3))
	    {
		rt=0;
		for (int j=ps[i]+1;j<=min((i+1)*sz-1,k-3)+1;++j)
		{
		    if (B[j]) rt=j;
		    else break;
		}
		for (int j=ps[i]+1;j<=rt-1;++j) cl[j]=(!cl[ps[i]]);
		if (rt<=min((i+1)*sz-1,k-3)) cl[rt]=cl[ps[i]];
		if (rt==min((i+1)*sz-1,k-3)+1) cls[i]=B[min((i+1)*sz-1,k-3)+2],vis[i]=(i==block[k-3]||ps[i+1]!=(i+1)*sz);
		ps[i]=rt;
		if (rt==min((i+1)*sz-1,k-3)+1) break;
	    }
    }
    for (int i=block[k-3];i>=0;--i)
    {
	d=min((i+1)*sz-1,k-3);
	if (!vis[i]) A.reset(),A[d]=1,B=Add(A,A),cls[i]=cl[d]^B[d+2];
	for (int j=i*sz;j<=d;++j)
	{
	    if (cl[j]^cls[i]^1) p[j]=p[d+1];
	    else p[j]=-p[d+1];
	}
    }
    return p;
}