#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> ii;
const int mxN = 90005;
int N, M, A, B;
int E[mxN];
vector<int> al[mxN];
vector<int> dist;
vector<ii> tree;
vector<int> w;
int num = 0;
ll query() {
++num;
assert(num <= 100);
//cout << num << ": ";
//FOR(i,0,M-1) cout << w[i] << ' ';
//cout << endl;
return ask(w);
}
void bfs(vector<int> S) {
dist.assign(N,-1);
tree.assign(N,ii(-1,-1));
queue<int> q;
for (auto& s : S) { q.push(s), dist[s] = 0, tree[s].second = s; }
while (!q.empty()) {
int u = q.front(); q.pop();
for (int e : al[u]) {
int v = E[e]^u;
if (dist[v] == -1) {
dist[v] = dist[u]+1;
tree[v] = ii(e,tree[u].second);
q.push(v);
}
}
}
}
void setW(int u, int v, vector<int>& V, int p) {
vector<bool> vis(N,0);
FOR(i,u,v){
for (int x = V[i]; tree[x].first != -1 && !vis[x]; x = E[tree[x].first]^x) {
vis[x] = 1;
w[tree[x].first] = p;
}
}
}
int solve(int S, int L, ll D) {
w.assign(M,1);
vector<int> V;
FOR(i,0,N-1) if (tree[i].second == S && dist[i] == L) V.push_back(i);
setW(0,SZ(V)-1,V,0);
int lo = -1, hi = SZ(V)-1;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
setW(lo+1,mid,V,1);
ll q = query();
setW(lo+1,mid,V,0);
if (q < D) lo = mid;
else hi = mid;
}
return V[hi];
}
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
N = _N;
M = U.size();
FOR(i,0,M-1){
E[i] = U[i]^V[i];
al[U[i]].push_back(i);
al[V[i]].push_back(i);
}
A = _A, B = _B;
w.assign(M,0);
ll toll = query();
int e;
{
int lo = -1, hi = M;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
FOR(i,lo+1,mid) w[i] = 1;
ll q = query();
if (q == toll) lo = mid;
else {
FOR(i,lo+1,mid) w[i] = 0;
hi = mid;
}
}
e = hi;
}
//TRACE(U[e] _ V[e]);
bfs({U[e],V[e]});
w.assign(M,0);
vector<int> vec;
FOR(i,0,N-1) if (tree[i].second == U[e]) vec.push_back(i);
setW(0,SZ(vec)-1,vec,1);
int l = toll / A;
int l1 = (query() - toll) / (B - A);
int l2 = l - 1 - l1;
//TRACE(l1 _ l2);
int S = solve(U[e],l1,(ll)l*B), T = solve(V[e],l2,(ll)l*B);
//TRACE(S _ T);
answer(S,T);
}
