Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation pp of length nn, and Skynyrd bought an array aa of length mm, consisting of integers from 11 to nn.
Lynyrd and Skynyrd became bored, so they asked you qq queries, each of which has the following form: "does the subsegment of aa from the ll-th to the rr-th positions, inclusive, have a subsequence that is a cyclic shift of pp?" Please answer the queries.
A permutation of length nn is a sequence of nn integers such that each integer from 11 to nn appears exactly once in it.
A cyclic shift of a permutation (p1,p2,…,pn)(p1,p2,…,pn) is a permutation (pi,pi+1,…,pn,p1,p2,…,pi−1)(pi,pi+1,…,pn,p1,p2,…,pi−1) for some ii from 11 to nn. For example, a permutation (2,1,3)(2,1,3) has three distinct cyclic shifts: (2,1,3)(2,1,3), (1,3,2)(1,3,2), (3,2,1)(3,2,1).
A subsequence of a subsegment of array aa from the ll-th to the rr-th positions, inclusive, is a sequence ai1,ai2,…,aikai1,ai2,…,aik for some i1,i2,…,iki1,i2,…,ik such that l≤i1<i2<…<ik≤rl≤i1<i2<…<ik≤r.
The first line contains three integers nn, mm, qq (1≤n,m,q≤2⋅1051≤n,m,q≤2⋅105) — the length of the permutation pp, the length of the array aa and the number of queries.
The next line contains nn integers from 11 to nn, where the ii-th of them is the ii-th element of the permutation. Each integer from 11 to nnappears exactly once.
The next line contains mm integers from 11 to nn, the ii-th of them is the ii-th element of the array aa.
The next qq lines describe queries. The ii-th of these lines contains two integers lili and riri (1≤li≤ri≤m1≤li≤ri≤m), meaning that the ii-th query is about the subsegment of the array from the lili-th to the riri-th positions, inclusive.
Print a single string of length qq, consisting of 00 and 11, the digit on the ii-th positions should be 11, if the subsegment of array aa from the lili-th to the riri-th positions, inclusive, contains a subsequence that is a cyclic shift of pp, and 00 otherwise.
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5
110
2 4 3
2 1
1 1 2 2
1 2
2 3
3 4
010
In the first example the segment from the 11-st to the 55-th positions is 1,2,3,1,21,2,3,1,2. There is a subsequence 1,3,21,3,2 that is a cyclic shift of the permutation. The subsegment from the 22-nd to the 66-th positions also contains a subsequence 2,1,32,1,3 that is equal to the permutation. The subsegment from the 33-rd to the 55-th positions is 3,1,23,1,2, there is only one subsequence of length 33 (3,1,23,1,2), but it is not a cyclic shift of the permutation.
In the second example the possible cyclic shifts are 1,21,2 and 2,12,1. The subsegment from the 11-st to the 22-nd positions is 1,11,1, its subsequences are not cyclic shifts of the permutation. The subsegment from the 22-nd to the 33-rd positions is 1,21,2, it coincides with the permutation. The subsegment from the 33 to the 44 positions is 2,22,2, its subsequences are not cyclic shifts of the permutation.
#pragma GCC optimize(2) #include <bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; const int maxn = 2e5 + 168; typedef long long ll; const ll mod = 1e9 + 7; int n,m,q,c[maxn],o[maxn],last[maxn],limit; int ans[maxn]; ll t[maxn]; int pre[maxn]; int f[maxn][28]; inline int solve(int cur){ int tot=n-1; int res=cur; for(register int i=limit;i>=0;--i){ if(t[i]<=tot){ res=f[res][i]; tot-=t[i]; } } return res; } int main() { #ifndef ONLINE_JUDGE freopen("1.txt", "r", stdin); #endif scanf("%d%d%d",&n,&m,&q); limit=(int)((log(n))/(log(2))+1); t[0]=1; for(register int i=1;i<=30;++i){ t[i]=(t[i-1]<<1); } for(register int i=1;i<=n;++i){ scanf("%d",&c[i]); pre[c[i]]=c[i-1]; } pre[c[1]]=c[n]; for(register int i=1;i<=m;++i){ scanf("%d",&o[i]); f[i][0]=last[pre[o[i]]]; for(register int j=1;j<=limit;++j){ f[i][j]=f[f[i][j-1]][j-1]; } last[o[i]]=i; } for(register int i=1;i<=m;++i){ int cur_ans=solve(i); ans[i]=max(ans[i-1],cur_ans); } int l,r; while(q--){ scanf("%d%d",&l,&r); if(ans[r]>=l){ printf("1"); } else{ printf("0"); } } return 0; }