#include "shop.h"
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define sz(x) (int)x.size()
const int maxn=5e4+5;
int rec(int l,int r){
	if(l==r){
		return l;
	}
	int mid=(l+r)/2;
	int qa[mid-l+1],qb[r-mid];
	REP(i,mid-l+1) qa[i]=l+i;
	REP(i,r-mid) qb[i]=mid+1+i;
	if(query(qa,mid-l+1,qb,r-mid)){
		return rec(mid+1,r);
	}
	return rec(l,mid);
}
void find_price(int task_id, int n, int K, int ans[]) {
	if(n==1){
		ans[0]=1;
		return;
	}
	// There will be T times call to the function, be sure to clear data before doing anything else.
	for (int i = 0; i < n; ++i) ans[i] = 0; 	
	if(task_id==3){
	int qa[]={0},qb[]={n-1};
	if(query(qa,1,qb,1)){
		int l=-1,r=n-2;
		while(l<r){
			int mid=(l+r+1)/2;
			int qa[2]={mid,mid+1},qb[1]={n-1};
			if(mid<0 or query(qa,2,qb,1)){
				l=mid;
			}
			else r=mid-1;
		}
		if((n-l)%2!=K) --l;
		REP(i,l+2) ans[i]=0;
		for(int i=l+2;i<n;i++) ans[i]=1;
	}
	else{
		int l=1,r=n+1;
		while(l<r){
			int mid=(l+r)/2;
			int qa[2]={mid,mid-1},qb[1]={0};
			if(mid>=n or query(qa,2,qb,1)){
				r=mid;
			}
			else l=mid+1;
		}
		if((l-1)%2!=K) ++l;
		REP(i,l-1) ans[i]=1;
		for(int i=l-1;i<n;i++) ans[i]=0;
	}
	}
	else{
		int on=0;
		int pv=1;
		vector<int> v;
		for(int i=2;i<n;i++){
			int qa[2]={pv,i},qb[1]={on};
			if(query(qa,2,qb,1)){
				qb[0]=i;
				if(query(qa,1,qb,1)){
					ans[pv]=0;
					pv=i;
				}
				else{
					ans[i]=0;
				}
			}
			else{
				qb[0]=i;
				v.pb(on);
				if(query(qa,1,qb,1)){
					on=i;
				}
				else{
					on=pv;
					pv=i;
				}
			}
		}
		int qa[]={on},qb[]={pv};
		bool dk=1;
		if(query(qa,1,qb,1)){
			v.pb(on);
			on=pv;
			dk=0;
		}
		v.pb(on);
		ans[on]=1;
		if(sz(v)==1){
		int cnt=0;
		REP(i,n) cnt+=ans[i];
		if(cnt%2!=K) ans[pv]=1;
		return;
		}
		/*REP(i,n) cout<<ans[i]<<' ';
		cout<<'\n';
		for(int x:v) cout<<x<<' ';
		cout<<'\n';
		cout<<pv<<'\n';*/
		int l=0,r=sz(v)-2;
		while(l<r){
			int mid=(l+r)/2;
			int qa[2]={v[mid],v[mid+1]},qb[1]={on};
			if(query(qa,2,qb,1)){
				l=mid+1;
			}
			else r=mid;
		}
		REP(i,l) ans[v[i]]=0;
		for(int i=l+1;i<sz(v);i++) ans[v[i]]=1;
		if(dk){
			int i=v[l];
			int qa[2]={pv,i},qb[1]={on};
			if(query(qa,2,qb,1)){
				qb[0]=i;
				if(query(qa,1,qb,1)){
					ans[pv]=0;
					pv=i;
				}
				else{
					ans[i]=0;
				}
			}
			else{
				qb[0]=i;
				if(query(qa,1,qb,1)){
					ans[i]=1;
				}
				else{
					ans[pv]=1;
					pv=i;
				}
			}
		}
		else pv=v[l];
		int cnt=0;
		REP(i,n) cnt+=ans[i];
		if(cnt%2!=K) ans[pv]=1;
	}
}