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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int numQueries = in.nextInt();
            int[] p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = in.nextInt() - 1;
            }
            int[] a = new int[m];
            for (int i = 0; i < m; i++) {
                a[i] = in.nextInt() - 1;
            }


            int[] nextP = new int[n];
            for (int i = 0; i < n; i++) {
                int j = i + 1;
                if (j == n) {
                    j = 0;
                }
                nextP[p[i]] = p[j];
            }

            int log = 22;
            int[][] next = new int[log][m + 1];
            int[] latest = new int[n + 1];
            Arrays.fill(latest, m);
            for (int[] arr : next) {
                Arrays.fill(arr, m);
            }
            for (int i = m - 1; i >= 0; i--) {
                next[0][i] = latest[nextP[a[i]]];
                latest[a[i]] = i;
            }

            for (int level = 1; level < log; level++) {
                for (int i = 0; i <= m; i++) {
                    next[level][i] = next[level - 1][next[level - 1][i]];
                }
            }

            MinTree tree = new MinTree(m);
            for (int i = 0; i < m; i++) {
                int need = n - 1;
                int j = i;
                for (int level = log - 1; level >= 0; level--) {
                    if (need >= (1 << level)) {
                        j = next[level][j];
                        need -= 1 << level;
                    }
                }
                tree.set(i, j);
            }

            char[] ans = new char[numQueries];
            for (int queryId = 0; queryId < numQueries; queryId++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                ans[queryId] = tree.getMin(l, r) <= r ? '1' : '0';
            }
            out.println(new String(ans));
        }

        class MinTree {
            int[] a;
            int n;

            MinTree(int size) {
                n = 1;
                while (n < size) {
                    n *= 2;
                }
                a = new int[2 * n];
                Arrays.fill(a, Integer.MAX_VALUE);
            }

            void set(int pos, int val) {
                pos += n;
                a[pos] = val;
                while (pos > 1) {
                    pos /= 2;
                    a[pos] = Math.min(a[2 * pos], a[2 * pos + 1]);
                }
            }

            int getMin(int l, int r) {
                if (l > r) {
                    return 0;
                }
                l += n;
                r += n;
                if (l == r) {
                    return a[l];
                }
                int lm = a[l];
                int rm = a[r];
                while (r - l > 1) {
                    if (l % 2 == 0) {
                        lm = Math.min(lm, a[l + 1]);
                    }
                    if (r % 2 == 1) {
                        rm = Math.min(rm, a[r - 1]);
                    }
                    l /= 2;
                    r /= 2;
                }
                return Math.min(lm, rm);
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

