#include "Annalib.h"
#pragma GCC target("avx2")
#include<bits/stdc++.h>
//#include<x86intrin.h>
//#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=155;
void Anna(signed n, ll x, signed k, signed p[]){
const int mod[2]={Mod,Mod+2};
int re[2];
re[0]=x/mod[1],re[1]=x%mod[1];
bool good[maxn],res[maxn];
rep(n) good[i]=1,res[i]=0;
rep(k) good[p[i]]=0;
int pw2[2][maxn];
pw2[0][0]=pw2[1][0]=1;
rep(2) rep1(j,maxn-2) pw2[i][j+1]=pw2[i][j]*2%mod[i];
rep1(_,2){
int l=0+n/2*_,r=n/2+n/2*_;
int tot=0;
rep2(i,l,r) tot+=good[i];
vector<int> vec;
int tar=min(tot/2,20ll);
int cur;
rep2(i,l,r) if(good[i]){
vec.pb(i);
tar--;
cur=i+1;
if(!tar) break;
}
vector<pii> vv;
rep1(mask,pow2(sz(vec))){
int t=0;
rep(sz(vec)) if(mask>>i&1) t=(t+pw2[_][vec[i]-l])%mod[_];
vv.pb({t,mask});
}
sort(all(vv));
vector<int> vec2;
tar=min(tot/2,20ll);
rep2(i,cur,r) if(good[i]){
vec2.pb(i);
tar--;
if(!tar) break;
}
bool flag=0;
rep1(mask,pow2(sz(vec2))){
int t=0;
rep(sz(vec2)) if(mask>>i&1) t=(t+pw2[_][vec2[i]-l])%mod[_];
t=(re[_]-t+mod[_])%mod[_];
auto it=lower_bound(all(vv),pii(t,-1));
if(it!=vv.end()&&(*it).first==t){
int m2=(*it).second;
rep(sz(vec)) if(m2>>i&1) res[vec[i]]=1;
rep(sz(vec2)) if(mask>>i&1) res[vec2[i]]=1;
flag=1;
break;
}
}
assert(flag);
}
rep(n) Set(i,res[i]);
}
#include "Brunolib.h"
#pragma GCC target("avx2")
#include<bits/stdc++.h>
//#include<x86intrin.h>
//#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=155;
long long Bruno(signed n, signed a[]){
const int mod[2]={Mod,Mod+2};
int r[2];
rep(2) r[i]=0;
rep3(i,n/2-1,0) r[0]=(r[0]*2+a[i])%mod[0];
rep3(i,n-1,n/2) r[1]=(r[1]*2+a[i])%mod[1];
return r[0]*mod[1]+r[1];
}
