#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define rp(i,v) for(int i:v)
#define ford(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define sz(s) (int)(s.size())
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 998244353
/************************************************/
using namespace std;
//int cnt[1001];
int a[8]={1,183,3472,20832,62500,125000,250000,500000};
int richest(int n,int s,int t){
int cnt[1000001];
vi now;
forn(i,1,n+1)
now.pb(i);
forn(i,1,n+1)
cnt[i]=0;
if(n==1000){
vi a,b;
a.clear();
b.clear();
forn(i,1,n+1)
forn(j,i+1,n+1){
a.pb(i);
b.pb(j);
}
vi res=ask(a,b);
rep(i,sz(res)){
cnt[res[i]]++;
}
forn(i,1,n+1){
if(cnt[i]==n)
return i;
}
}
ford(i,8){
int c1=a[i]-n%a[i],c2=n%a[i];
int l1=n/a[i],l2=n/a[i]+1;
vi nxt;
int j=0;
while(c1--){
vi a,b;
forn(i1,j,j+l1)
forn(j1,i1+1,j+l1){
a.pb(now[i1]);
b.pb(now[j1]);
}
forn(i1,j,j+l1)
cnt[now[i1]]=0;
j+=l1;
}
while(c2--){
vi a,b;
forn(i1,j,j+l2)
forn(j1,i1+1,j+l2){
a.pb(now[i1]);
b.pb(now[j1]);
}
forn(i1,j,j+l2)
cnt[now[i1]]=0;
j+=l2;
}
vi res=ask(a,b);
rep(i,sz(res))
cnt[res[i]]++;
c1=a[i]-n%a[i],c2=n%a[i];
j=0;
while(c1--){
forn(i1,j,j+l1)
if(cnt[now[i1]]==l1)
nxt.pb(now[i1]);
j+=l1;
}
while(c2--){
forn(i1,j,j+l2)
if(cnt[now[i1]]==l2)
nxt.pb(now[i1]);
j+=l2;
}
now=nxt;
}
re now[0];
}
/*
检查循环是rep(i,n)还是rep(i,m)!!
long long所要的时间比int长!!
没有long long必要不写long long!!
写公式前先想一想!!
二分前看一看边界对不对，有没有特殊值!!
提交前要测特殊数据（边界上的）!!
比较模数时如有负数，需要+mod!!
*/