// author: georgeyucjr
# include <bits/stdc++.h>

# ifndef ONLINE_JUDGE
  # define LOCAL
# endif

# if __cplusplus >= 201100LL
# else
  # error Please use C++11 Or Higher CPP version
# endif

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std :: array < int, 3 >;
using arr4 = std :: array < int, 4 >;
using pii = std :: pair < int, int >;

# define rep(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i )
# define per(i, f, t, ...) for ( std :: decay < decltype ( f + t ) > :: type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i )
# define eb emplace_back
# define pb push_back
# define mkp make_pair
# define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)
# define INLINE_V inline

template < class T, class U >
inline constexpr auto ceil ( T && x, U && y ) {
  return ( x > 0 ? ( x + y - 1 ) / y : x / y );
}

template < class T, class U >
inline constexpr auto floor ( T && x, U && y ) {
  return ( x > 0 ? x / y : ( x - y + 1 ) / y );
}

template < class T, class U >
inline constexpr auto divmod ( T && x, U && y ) {
  auto && q = floor ( x, y );
  return std :: pair { q, x - q * y };
}

# define ALL( vc ) std :: begin ( vc ), std :: end ( vc )

template < class T >
  requires ( std :: is_signed_v < T > || std :: is_unsigned_v < T > )
INLINE_V constexpr static T inf = std :: numeric_limits < T > :: max ( ) >> 1;

template <std :: ranges :: forward_range R>
inline constexpr auto Sum ( R && r ) {
  return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), 0 );
}

template < std :: ranges :: forward_range R, typename T >
inline constexpr auto Sum ( R && r, T init) {
  return std :: accumulate ( std :: ranges :: begin ( r ), std :: ranges :: end ( r ), init );
}

template < std :: ranges :: forward_range R >
inline constexpr int SZ ( R && x ) { return std :: size ( x ); }

template < class Os, class T >
inline Os & operator << ( Os & os, T & t ) {
  for ( auto ele : t )
    os << ele << " ";
  os << "\n";
  return os;
}

template < class T >
inline constexpr void clr_cont ( T & cont ) { 
  T nw; cont.swap ( nw ); 
}

inline constexpr auto Abs ( const auto & x ) { return x < 0 ? -x : x; }
inline constexpr auto sqr ( const auto & x ) { return x * x; }
inline constexpr auto Max ( const auto & x ) { return x; }
inline constexpr auto Min ( const auto & x ) { return x; }
inline constexpr auto Max ( const auto & x, const auto & y, const auto & ... args ) { return x < y ? Max ( y, args ... ) : Max ( x, args ... ); }
inline constexpr auto Min ( const auto & x, const auto & y, const auto & ... args ) { return x < y ? Min ( x, args ... ) : Min ( y, args ... ); }
inline constexpr void chkmax ( auto & d, const auto & ... x ) { d = Max ( d, x ... ); }
inline constexpr void chkmin ( auto & d, const auto & ... x ) { d = Min ( d, x ... ); }

using namespace std;

constexpr int N = 1e6 + 5;

# include "richest.h"

constexpr array<int, 8> Ls = { (int)5e5, (int)2.5e5, 125000, 62500, 20832, 3472, 183, 1 };

// signed main() {
int richest(int n, int T, int S) {
	// cerr << "N = " << n << ", T = " << T << ", S = " << S << "\n";
	if (T == 1) {
		vector<int> v1, v2;
		rep(i, 1, n) rep(j, i + 1, n) v1.eb(i - 1), v2.eb(j - 1);
		auto ans = ask(v1, v2);
		vector<int> cnt(n);
		for(auto i : ans) ++cnt[i];
		rep(i, 0, n - 1) if (cnt[i] == n - 1) return i;
		return 114514;
	} else {
		vector<int> id(n);
		iota(ALL(id), 0);
		rep(_, 0, 7) {
			auto k = Ls[_];
			vector<vector<int>> rec(n);
			rep(i, 0, SZ(id) - 1) rec[i % k].eb(id[i]);
			vector<int> v1, v2;
			rep(t, 0, k - 1) {
				auto tv = rec[t];
				rep(x, 0, SZ(tv) - 1)
					rep(y, 0, SZ(tv) - 1)
						v1.eb(id[x]), v2.eb(id[y]);
			}
			auto ans = ask(v1, v2);
			vector<int> cnt(n, 0);
			for (auto i : ans) ++cnt[i];
			id.resize(k);
			rep(i, 0, k - 1) {
				auto tv = rec[i];
				id[i] = -1;
				for (auto j : tv) if (cnt[j] == SZ(tv) - 1) id[i] = j;
			}
		}
		return id[0];
	}
	return 0;
}