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.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;
 
public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        
        public int read() {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
            
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
            
            return res * sgn;
        }
        
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
        
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(),"Main",1<<27).start();
    }
    int querySegTree(int low, int high, int pos, int l, int r) {
        if(low > r || high < l)
            return -1;

        if(low >= l && high <= r)
            return segTree[pos];

        int mid = (low + high) >> 1;
        int val1 = querySegTree(low, mid, 2 * pos + 1, l ,r);
        int val2 = querySegTree(mid + 1, high, 2 * pos + 2, l, r);
        return max(val1, val2);
    }
    void updateSegTree(int low, int high, int pos, int ind, int val) {
        if(low > ind || high < ind)
            return;

        if(low == high) {
            segTree[pos] = val;
            return;
        }

        int mid = (low + high) >> 1;
        updateSegTree(low, mid, 2 * pos + 1, ind, val);
        updateSegTree(mid + 1, high, 2 * pos + 2, ind, val);
        segTree[pos] = max(segTree[2 * pos + 1], segTree[2 * pos + 2]);
    }
    int segTree[]; 
    public void run() {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
 
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        int permute[] = new int[n];
        int needed[] = new int[n + 1];
        for(int i = 0; i < n; ++i) {
            permute[i] = sc.nextInt();
            if(i != 0)
                needed[permute[i]] = permute[i - 1];
        }
        needed[permute[0]] = permute[n - 1];

        int a[] = new int[m];
        int par[][] = new int[m][18];

        segTree = new int[4 * m];
        Arrays.fill(segTree, -1);

        int ind[] = new int[n + 1];
        Arrays.fill(ind, -1);

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < 18; ++j)
                par[i][j] = -1;
        }
        for(int i = 0; i < m; ++i) {
            a[i] = sc.nextInt();

            if(ind[needed[a[i]]] != -1) {
                par[i][0] = ind[needed[a[i]]]; 
            }   
            else
                par[i][0] = -1;

            for(int j = 1; j < 18; ++j) {
                if(par[i][j - 1] != -1) {
                    par[i][j] = par[par[i][j - 1]][j - 1];
                }
            }

            int dist = n - 1;
            int curNode = i;
            for(int j = 17; j >= 0; --j) {
                int curDist = 1 << j;
                if(curDist <= dist) {
                    if(par[curNode][j] == -1)
                        break;
                    dist -= curDist;
                    curNode = par[curNode][j];
                }
            }

            if(dist == 0)
                updateSegTree(0, m - 1, 0, i, curNode);

            ind[a[i]] = i;
        }

        for(int i = 0; i < q; ++i) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;

            int cans = querySegTree(0, m - 1, 0, l, r);
            if(cans >= l)
                w.print("1");
            else
                w.print("0");
        }
 
        w.close();
    }
}