#include <bits/stdc++.h>
#include "richest.h"
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef int li;
typedef long double lf;
		
inline li read(){
	li ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

vector<li> v1, v2, v3, rest, rest2;
li a[2010][2010], mpclear;
map<pair<li, li>, li> mp;
li x[] = {2, 2, 2, 2, 3, 6, 19, 183};
li z[] = {0, 0, 0, 0, 4, 7, 18, 0};
li y[] = {500000, 250000, 125000, 62500, 20832, 3471, 178, 1};

li richest(li n, li t, li s){
//	FILE *out = fopen("www.ww", "w");
//	for(li i = 0; i < n; i++) a[i] = mpclear;
	if(t == 1){
		v1.clear(),  v2.clear();
		for(li i = 1; i <= n; i++){
			for(li j = i + 1; j <= n; j++){
				v1.push_back(i - 1);
				v2.push_back(j - 1);
			}
		}	
		v3 = ask(v1, v2);
		li now = 0;
		for(li i = 1; i <= n; i++){
			for(li j = i + 1; j <= n; j++){
				if(v3[now] + 1 == i) a[i][j] = 1;
				else a[i][j] = 0;
				a[j][i] = !a[i][j];
				//				fprintf(out, "%d %d %d %d\n", v1[now], v2[now], v3[now] + 1, a[i][j]);
				now++;
			}
			a[i][i] = 1;
		}
		for(li i = 1; i <= n; i++){
			li cnt = 0;
			for(li j = 1; j <= n; ++j) cnt += a[i][j];
			//			fprintf(out, "cnt %d = %d\n", i, cnt);
			if(cnt == n){
				//				fclose(out);
				return i - 1;
			}
		}
	}
	mp.clear();
	rest.clear();
	for(li i = 0; i < n; i++) rest.push_back(i);
	for(li i = 0; i <= 7; i++){
//		fprintf(out, "i = %d\n", i); fflush(out);
		rest2.clear();
		li nn = rest.size();
		li cnt = 0;
		for(li j = 0; j < nn; j += x[i]){
			cnt++;
			if(cnt > y[i]) swap(x[i], z[i]), cnt = -1e8;	
			li r = j + x[i] - 1;
			r = min(r, nn - 1);
			for(li p = j; p <= r; p++){
				for(li q = p + 1; q <= r; q++){
					v1.push_back(rest[p]), v2.push_back(rest[q]);
					mp[{rest[p], rest[q]}] = v1.size() - 1;
				}
			}			
		}
		if(cnt < 0) swap(x[i], z[i]);
		cnt = 0; 
		v3 = ask(v1, v2);
		for(li j = 0; j < nn; j += x[i]){
			cnt++;
			if(cnt > y[i]) swap(x[i], z[i]), cnt = -1e8;	
			li r = j + x[i] - 1;
			r = min(r, nn - 1);
			for(li p = j; p <= r; p++){
				a[p - j][p - j] = 1;
				for(li q = p + 1; q <= r; q++){
					a[p - j][q - j] = 0;
					if(v3[mp[{rest[p], rest[q]}]] == rest[p]) a[p - j][q - j] = 1;
					a[q - j][p - j] = !a[p - j][q - j];
//					v1.push_back(rest[p]), v2.push_back(rest[q]);
//					mp[{rest[p], rest[q]}] = v1.size() - 1;
				}
			}			
			for(li p = j; p <= r; p++){
				li cnt = 0;
				for(li q = j; q <= r; q++) cnt += a[p - j][q - j];
//				fprintf(out, "%d\n", cnt);
				if(cnt == r - j + 1) rest2.push_back(rest[p]);
			}
		}
		if(cnt < 0) swap(x[i], z[i]);
		cnt = 0; 
		rest = rest2;
		rest2.clear();
		v1.clear(), v2.clear();
	}
	return rest[0];
}