Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation p of length n, and Skynyrd bought an array a of length m, consisting of integers from 1 to n. 

Lynyrd and Skynyrd became bored, so they asked you q queries, each of which has the following form: "does the subsegment of a from the l-th to the r-th positions, inclusive, have a subsequence that is a cyclic shift of p?" Please answer the queries.

A permutation of length n is a sequence of n integers such that each integer from 1 to n appears exactly once in it.

A cyclic shift of a permutation (p_1, p_2, …, p_n) is a permutation (p_i, p_{i + 1}, …, p_{n}, p_1, p_2, …, p_{i - 1}) for some i from 1 to n. For example, a permutation (2, 1, 3) has three distinct cyclic shifts: (2, 1, 3), (1, 3, 2), (3, 2, 1).

A subsequence of a subsegment of array a from the l-th to the r-th positions, inclusive, is a sequence a_{i_1}, a_{i_2}, …, a_{i_k} for some i_1, i_2, …, i_k such that l ≤ i_1 < i_2 < … < i_k ≤ r.

Input

The first line contains three integers n, m, q (1 ≤ n, m, q ≤ 2 ⋅ 10^5) — the length of the permutation p, the length of the array a and the number of queries.

The next line contains n integers from 1 to n, where the i-th of them is the i-th element of the permutation. Each integer from 1 to n appears exactly once.

The next line contains m integers from 1 to n, the i-th of them is the i-th element of the array a.

The next q lines describe queries. The i-th of these lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ m), meaning that the i-th query is about the subsegment of the array from the l_i-th to the r_i-th positions, inclusive.

Output

Print a single string of length q, consisting of 0 and 1, the digit on the i-th positions should be 1, if the subsegment of array a from the l_i-th to the r_i-th positions, inclusive, contains a subsequence that is a cyclic shift of p, and 0 otherwise.

Examples

Input

3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5


Output

110


Input

2 4 3
2 1
1 1 2 2
1 2
2 3
3 4


Output

010

Note

In the first example the segment from the 1-st to the 5-th positions is 1, 2, 3, 1, 2. There is a subsequence 1, 3, 2 that is a cyclic shift of the permutation. The subsegment from the 2-nd to the 6-th positions also contains a subsequence 2, 1, 3 that is equal to the permutation. The subsegment from the 3-rd to the 5-th positions is 3, 1, 2, there is only one subsequence of length 3 (3, 1, 2), but it is not a cyclic shift of the permutation.

In the second example the possible cyclic shifts are 1, 2 and 2, 1. The subsegment from the 1-st to the 2-nd positions is 1, 1, its subsequences are not cyclic shifts of the permutation. The subsegment from the 2-nd to the 3-rd positions is 1, 2, it coincides with the permutation. The subsegment from the 3 to the 4 positions is 2, 2, its subsequences are not cyclic shifts of the permutation.
import java.io.FileInputStream;
import java.util.*;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class TaskB {
    int INF = 1000100;
    int n, m, q;
    int[] ps, as;
    int[] dp;
    int[][] aft;
    Map<Integer, Integer> mp = new HashMap<>();
    Map<Integer, ArrayList<Integer>> ids = new HashMap<>();

    int get(int i, int j){
        //System.out.println(i + " " + j);
        if(i<0 || i>=m || j>(m-i) || j<=0 ) return INF;
        int k=0;
        while((1<<k) < j){
            k++;
        }
        if((1<<k) == j){
            return aft[i][k];
        }else{
            int ii = get(i, 1<<(k-1));
            return get(ii, j - (1<<(k-1)) + 1);
        }
    }

    int upper_bound(List<Integer> ls, int t){
        int ln = ls.size();
        int l = 0, r = ln-1;
        if(ls.get(r)<=t) return -1;
        if(ls.get(0)>t) return ls.get(0);
        while(l<=r){
            int m = l + (r-l)/2;
            if(ls.get(m)<=t){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return ls.get(l);
    }
    int low_bound(List<Integer> ls, int t){
        int ln = ls.size();
        int l = 0, r = ln-1;
        if(ls.get(r)<t) return ls.get(r);
        if(ls.get(0)>=t) return -1;
        while(l<=r){
            int m = l + (r-l)/2;
            if(ls.get(m)<t){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return ls.get(r);
    }

    void solve() throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();
        ps = new int[n];
        as = new int[m];
        for (int i = 0; i < n; i++) {
            ps[i] = sc.nextInt();
            mp.put(ps[i], i);
        }
        for (int i = 0; i < m; i++) {
            as[i] = sc.nextInt();
            int a = as[i];
            if(!ids.containsKey(a)){
                ids.put(a, new ArrayList<>());
            }
            ids.get(a).add(i);
        }

        aft = new int[m][31];
        for(int i=m-1; i>=0; i--){
            int a = as[i];
            int api = mp.get(a);
            int bpi = (api + 1) % n;
            int b = ps[bpi];
            //System.out.println(b + " " +  i + " " + ids.get(b));
            int bi = INF;
            if(ids.get(b)!=null) {
                bi = upper_bound(ids.get(b), i);
            }
            aft[i][0] = i;
            for(int j=1; j<31; j++){
                aft[i][j] = get(bi, (1<<j)-1);
                //System.out.println(i + " " + j + " " + aft[i][j]);
            }
        }

        //System.out.println(get(1, 3));

        dp = new int[m];
        int ci = INF;
        for(int i=m-1; i>=0; i--){
            ci = min(ci, get(i, n));
            dp[i] = ci;

            //System.out.println(i + "=====" + dp[i]);
        }

        int[] res = new int[q];
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<q; i++){
            int l,r;
            l = sc.nextInt(); r= sc.nextInt();
            l--; r--;
            int rr = dp[l];
            if(rr<=r){
                res[i] = 1;
            }else{
                res[i] = 0;
            }
            if(n==1) res[i] = 1;

            sb.append(res[i]);
            //System.out.printf("%d", res[i]);
        }
        System.out.println(sb.toString());
        System.out.println("");

    }
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("inputs/b.in"));
        TaskB s = new TaskB();
        s.solve();
    }
}
