#include"highway.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int INF=1e9;
vector< pair<int,int> > ds[MAXN],nex[MAXN];
int dp[MAXN],trace[MAXN],pe[MAXN],ps[MAXN],root[MAXN],roote[MAXN],cnt=0;
bool ck[MAXN];
void dfs(int i,int pre)
{
ps[cnt]=i,root[i]=pre;
for(auto v:nex[i]) if(v.first!=pre)
{
pe[++cnt]=v.second,roote[v.first]=v.second;
dfs(v.first,i);
}
}
void find_pair(int n,vector<int> U,vector<int> V,int A,int B)
{
int m=U.size();
for(int i=0;i<m;i++) ds[U[i]].push_back({V[i],i}),ds[V[i]].push_back({U[i],i});
vector<int> vi(m);
long long dist=ask(vi)/A;
int pos=0;
for(int i=16;i+1;i--) if(pos+(1<<i)<m)
{
vector<int> res(m);
for(int j=0;j<pos+(1<<i);j++) res[j]=1;
if(ask(res)==dist*A) pos+=(1<<i);
}
queue<int> Q;
for(int i=0;i<n;i++) dp[i]=INF;
Q.push(U[pos]),dp[U[pos]]=0,trace[U[pos]]=pe[0]=-1;
while(!Q.empty())
{
int a=Q.front();
Q.pop();
for(auto v:ds[a]) if(dp[v.first]==INF) dp[v.first]=dp[a]+1,trace[v.first]=v.second,Q.push(v.first);
}
for(int i=0;i<n;i++) if(trace[i]>=0)
{
ck[trace[i]]=true;
nex[U[trace[i]]].push_back({V[trace[i]],trace[i]});
nex[V[trace[i]]].push_back({U[trace[i]],trace[i]});
}
for(int i=0;i<m;i++) vi[i]=!ck[i];
dfs(U[pos],U[pos]);
int l=0,r=0;
for(int i=16;i+1;i--) if(r+(1<<i)<n)
{
vector<int> res=vi;
for(int j=1;j<r+(1<<i);j++) res[pe[j]]=1;
if(ask(res)!=dist*B) r+=(1<<i);
}
int pa=ps[r];
while(pa!=U[pos]) vi[roote[pa]]=1,pa=root[pa];
for(int i=16;i+1;i--) if(l+(1<<i)<r-1)
{
vector<int> res=vi;
for(int j=1;j<l+(1<<i);j++) res[pe[j]]=1;
if(ask(res)!=dist*B) l+=(1<<i);
}
answer(ps[r],ps[l]);
}
