#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int M = 1e6;

vector<int> a, b, c;
int w[N + 5][N + 5];

vector<int> k[2];
bool vis[M + 5];
int cnt;

int richest(int n, int t, int s){
	if(t == 1){
		a.clear();
		b.clear();
		for(int i = 0; i < n; ++ i){
			for(int j = i + 1; j < n; ++ j){
				a.push_back(i);
				b.push_back(j);
			}
		}
		c = ask(a, b);
		for(int i = 0; i < a.size(); ++ i){
			w[a[i]][b[i]] = w[b[i]][a[i]] = c[i];
			// cout << a[i] << ' ' << b[i] << ": " << c[i] << '\n';
			// cout << w[a[i]][b[i]] << '\n';
		}
		int now = 0;
		for(int i = 1; i < n; ++ i){
			// cout << now << '-' << i << ':' << w[now][i] << '\n';
			if(w[now][i] == i) now = i;
		}
		// cout << now << '\n';
		return now;
	}

	srand(time(0));
	for(int i = 0; i < n; ++ i) vis[i] = 0;
	cnt = 0;

	int nowk = 0;
	k[0].clear(); k[1].clear();
	for(int i = 0; i < n; ++ i) k[nowk].push_back(i);
/*	while(t --){
		a.clear(); b.clear();
		int size = k[nowk].size();
		if(size == 1) break;
		for(int i = 0; i + 1 < size; i += 2){
			a.push_back(k[nowk][i]);
			b.push_back(k[nowk][i + 1]);
		}
		if(size & 1){
			a.push_back(k[nowk][size - 1]);
			b.push_back(k[nowk][size - 2]);
		}
		c = ask(a, b);
		for(int i = 0; i < c.size(); ++ i){
			if(a[i] == c[i]) vis[b[i]] = 1;
			if(b[i] == c[i]) vis[a[i]] = 1;
			// cout << a[i] << ' ' << b[i] << ": " << c[i] << '\n';
		}
		for(int i = 0; i < size; ++ i){
			if(!vis[k[nowk][i]]){
				k[nowk ^ 1].push_back(k[nowk][i]);
			}
		}
		k[nowk].clear();
		nowk ^= 1;
	}*/

	int ss = n;
	while(t --){
		// if(cnt == n - 2) break;
		// cnt = 0;
		// for(int i = 0; i < n; ++ i) cnt += !vis[i];
		// if(cnt == 1) break;
		a.clear(); b.clear();
		int m = k[nowk].size();
		
		// cout << m << '\n';
		if(m == 1) break;
		int ss = m / 2;
		for(int i = 1; i <= ss / 10; ++ i){
			int x = rand() % m;
			// while(vis[k[x]]) x = rand() % m;
			int y = rand() % m;
			while(y == x || y == x - 1 || y == x + 1) y = rand() % m;
			a.push_back(k[nowk][x]);
			b.push_back(k[nowk][y]);
		}
		
		for(int i = 0; i + 1 < m; i += 2){
			a.push_back(k[nowk][i]);
			b.push_back(k[nowk][i + 1]);
		}
		if(m & 1){
			a.push_back(k[nowk][m - 1]);
			b.push_back(k[nowk][m - 2]);
		}
		
		c = ask(a, b);
		for(int i = 0; i < c.size(); ++ i){
			if(a[i] == c[i]) vis[b[i]] = 1;
			if(b[i] == c[i]) vis[a[i]] = 1;
			// cout << a[i] << ' ' << b[i] << ": " << c[i] << '\n';
		}
		ss >>= 1;
		for(int i = 0; i < m; ++ i){
			if(!vis[k[nowk][i]]){
				k[nowk ^ 1].push_back(k[nowk][i]);
				// cout << k[nowk][i] << ' ';
			}
		}
		// cout << '\n';
		k[nowk].clear();
		nowk ^= 1;
	}

	int now = 0;
	while(vis[now]) ++ now;
	return now;
}