//qoj189
#include <bits/stdc++.h>
using namespace std;
#include "shop.h"

int tmp[2][2], aa[100010], cnt[100010];
bool cmp(int x, int y){
	return cnt[x] > cnt[y];
}
bool ask2(int x, int y){
	tmp[0][0] = x;
	tmp[1][0] = y;
	return query(tmp[0], 1, tmp[1], 1);
}
bool ask3(int x, int y, int z){
	tmp[0][0] = x;
	tmp[1][0] = y;
	tmp[1][1] = z;
	return query(tmp[0], 1, tmp[1], 2);
}

void find_price(int task_id, int N, int K, int ans[]){
	if(task_id == 3 || N <= 2){
		for(int i = 0; i < N; ++ i){
			ans[i] = cnt[i] = 0;
			aa[i] = i;
		}
		if(ask2(0, N-1)){
			for(int i = 0; i < N; ++ i){
				aa[i] = N - i - 1;
			}
		} else {
			for(int i = 0; i < N; ++ i){
				aa[i] = i;
			}
		}
		int l = 0, r = N - 1;
		while(l + 1 < r){
			int mid = l + r + 1 >> 1;
			if(ask3(aa[1], aa[mid], aa[mid+1])){
				l = mid;
			} else {
				r = mid;
			}
		}
		if((l & 1) == K){
			l = r;
		}
		for(int i = 0; i <= l; ++ i){
			ans[aa[i]] = 1;
		}
	} else {
		for(int i = 0; i < N; ++ i){
			ans[i] = aa[i] = 0;
		}
		int a = 0, b, c = 1, L = 0;
		for(int i = 2; i < N; ++ i){
			b = i;
			if(ask2(b, c) == 0){
				swap(b, c);
			}
			if(ask3(a, b, c) == 0){
				ans[b] = 0;
			} else {
				aa[L++] = a;
				a = c;
				c = b;
			}
		}
		if(ask2(a, c) == 0){
			swap(a, c);
		}
		ans[c] = 1;
		if(!L){
			ans[a] = K ^ 1;
			return;
		}
		aa[L++] = c;
		reverse(aa, aa + L);
		int l = 0, r = L - 1;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(mid < L - 1 && ask3(aa[0], aa[mid], aa[mid+1])){
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		for(int i = 0; i <= l; ++ i){
			ans[aa[i]] = 1;
		}
		c = aa[l+1];
		if(ask2(a, c) == 0){
			swap(a, c);
		}
		if(ask3(aa[0], c, a)){
			ans[c] = 1;
			++ l;
		} else {
			ans[a] = 0;
			a = c;
		}
		ans[a] = (l+1^K) & 1;
	}
	return;
}