#include #pragma GCC optimize("unroll-loops") using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; const ll ILL=2167167167167167167; const int INF=2100000000; const int mod=998244353; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} void yneos(bool a,bool upp=0){if(a) cout<<(upp?"YES\n":"Yes\n"); else cout<<(upp?"NO\n":"No\n");} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} namespace po167{ struct UFtree { using _F=int; int _n; std::vector<_F> wei; std::vector q; int component; UFtree(int n):_n(n),wei(n),component(n),par(n){ for(int i=0;i par; }; } using po167::UFtree; namespace po167{ template struct Doubling_op { int _n; long long Log; std::vector> index_data; std::vector> value_data; Doubling_op(int n,long long limit,std::vector index,std::vector value):_n(n){ Log=2; while(limit){ limit/=2; Log++; } index_data.resize(Log); value_data.resize(Log); index_data[0]=index; value_data[0]=value; for(int i=1;i query(long long times,int start_index,T start_value){ for(int i=0;i>=1; } return std::make_pair(start_index,start_value); } }; struct Doubling { int _n; long long Log; std::vector> index_data; Doubling(int n,long long limit,std::vector index):_n(n){ Log=2; while(limit){ limit/=2; Log++; } index_data.resize(Log); index_data[0]=index; for(int i=1;i>=1; } return start_index; } }; } using po167::Doubling_op; using po167::Doubling; using doubleing_F=long long; doubleing_F d_op(doubleing_F l,doubleing_F r){ return l+r; } //for(i=0;i0の格子点の数) ll Fsum(ll n,ll m,ll a,ll b){ ll ans=0; ans+=(b/m)*n+(a/m)*n*(n-1)/2; b%=m,a%=m; ll y=(a*(n-1)+b)/m; ll x=y*m-b; if(y==0){ return ans; } ans+=(n-(x-1)/a-1)*y; ans+=Fsum(y,a,m,((x+a-1)/a)*a-x); return ans; } //a*x+b*y=gcd(a,b)となるx,yにする 返り値gcd(a,b) ll Euclid(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0; return a; } ll d=Euclid(b,a%b,y,x); y-=a/b*x; return d; } // val1=(a,p) val2=(b,q) // return (c,r) // c: c%p==a && c%q==b // r: r=lcm(a,b) // need: a%gcd(p,q)==b%gcd(p,q) // use: Euclid std::pair ctr_sub(std::pair val1,std::pair val2){ long long a,b,p,q; long long X,Y,G,ans_val,ans_mod; tie(a,p)=val1; tie(b,q)=val2; G=Euclid(p,q,X,Y); if((b-a)%G!=0) return {-1,-1}; ans_mod=p*(q/G); ans_val=(p*((X*((b-a)/G))%q))%ans_mod+a; return {(ans_val%ans_mod+ans_mod)%ans_mod,ans_mod}; } void solve(); // oddloop int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; //cin>>t; rep(i,0,t) solve(); } void solve(){ int N; ll L,R; cin>>N>>L>>R; vector A(N); UFtree T(N); vector> G(N); vector to(N); vector pare(N); vector syc(N); vector pos(N); vector dpeth(N,-1); rep(i,0,N) cin>>A[i],A[i]--,T.unite(i,A[i]),G[A[i]].push_back(i),to[A[i]]++; vector order; Doubling D(N,N+1,A); rep(i,0,N) if(to[i]==0) order.push_back(i); rep(i,0,order.size()){ int a=order[i]; a=A[a]; to[a]--; if(to[a]==0) order.push_back(a); } rep(i,0,N) if(to[i]!=0){ vector p; while(to[i]){ pos[i]=p.size(); p.push_back(i); to[i]=0; i=A[i]; } for(auto x:p) dpeth[x]=0,syc[x]=p.size(),pare[x]=x; rep(rp,0,p.size()){ int a=p[rp]; for(auto x:G[a]) if(dpeth[x]==-1){ dpeth[x]=dpeth[a]+1; syc[x]=syc[a]; pare[x]=pare[a]; p.push_back(x); } } } int Q; cin>>Q; rep(rp,0,Q){ int s,t; cin>>s>>t; s--,t--; if(T.same(s,t)==0){ cout<<"-1\n"; continue; } if(dpeth[s]>dpeth[t]){ cout<<"-1\n"; continue; } if(dpeth[t]!=0){ int len=dpeth[s]-dpeth[t]; if(D.query(len,s)!=t){ cout<<"-1\n"; } else{ int k=((len+R-1)/R); cout<<(k*L<=len?k:-1)<<"\n"; } continue; } ll P=syc[s]; ll len=(dpeth[s]+(pos[t]-pos[pare[s]]+P)%P); if(R==L){ ll x,y; ll g=Euclid(P,R,x,y); if(len%g){ cout<<"-1\n"; } else{ x*=-len/g; y*=-len/g; ll tmp=(len/g)*R; x%=tmp; if(x<0) x+=tmp; tmp=x*P+len; assert(tmp%R==0); cout<1){ int m=(l+r)/2; ll a=Fsum(m+1,P,R,R*k-len); ll b=Fsum(m+1,P,L,k*L-1-len); if(a!=b) r=m; else l=m; } cout<