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.OutputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.Random;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        ELynyrdSkynyrd solver = new ELynyrdSkynyrd();
        solver.solve(1, in, out);
        out.close();
    }

    static class ELynyrdSkynyrd {
        int blockSize = 450;
        int FAIL = -1;
        int OK = 1;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            if (false) {
                new Tester().test();
            }
            int n = in.readInt();
            int m = in.readInt();
            int q = in.readInt();
            int[] p = in.readIntArray(n);
            int[] a = in.readIntArray(m);
            MiscUtils.decreaseByOne(p, a);
            Query[] queries = new Query[q];
            for (int i = 0; i < q; i++) {
                int l = in.readInt() - 1;
                int r = in.readInt() - 1;
                queries[i] = new Query(i, l, r);
            }
            new Solve(n, m, q, p, a, queries).solve();
            for (Query query : queries) {
                out.print(query.answer == OK ? 1 : 0);
            }
        }

        int getBlock(int x) {
            return x / blockSize;
        }

        class Tester {
            Random rnd = new Random(239);

            void shuffle(int[] a) {
                int n = a.length;
                for (int i = 1; i < a.length; i++) {
                    int j = rnd.nextInt(i + 1);
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }

            int[] perm(int n) {
                int[] a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = i;
                }
                shuffle(a);
                return a;
            }

            int[] array(int n, int m) {
                int[] a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = rnd.nextInt(m);
                }
                return a;
            }

            void test() {
                for (int t = 0; ; t++) {
                    int n = 5;
                    int m = 20;
                    int q = 10;
                    int[] p = perm(n);
                    int[] a = array(m, n);
                    shuffle(a);
                    Query[] queries = new Query[q];
                    for (int i = 0; i < q; i++) {
                        int x = rnd.nextInt(m);
                        int y = rnd.nextInt(m);
                        if (x > y) {
                            i--;
                            continue;
                        }
                        queries[i] = new Query(i, x, y);
                    }
                    new Naive(n, m, q, p, a, queries).solve();
                    int[] naive = extractAnswer(queries);
                    new Solve(n, m, q, p, a, queries).solve();
                    int[] solve = extractAnswer(queries);
                    if (!Arrays.equals(naive, solve)) {
                        System.err.println(n + " " + m + " " + q);
                        System.err.println(Arrays.toString(p));
                        System.err.println(Arrays.toString(a));
                        System.err.println(Arrays.toString(queries));
                        System.err.println(Arrays.toString(naive));
                        System.err.println(Arrays.toString(solve));
                        return;
                    }
                }
            }

            int[] extractAnswer(Query[] queries) {
                int n = queries.length;
                int[] ans = new int[n];
                for (int i = 0; i < n; i++) {
                    ans[i] = queries[i].answer;
                }
                return ans;
            }

        }

        class Naive {
            int n;
            int m;
            int q;
            int[] p;
            int[] a;
            Query[] queries;

            Naive(int n, int m, int q, int[] p, int[] a, Query[] queries) {
                this.n = n;
                this.m = m;
                this.q = q;
                this.p = p;
                this.a = a;
                this.queries = queries;
            }

            void solve() {
                for (Query query : queries) {
                    query.answer = FAIL;
                    int[] sub = getSub(a, query.l, query.r);
                    for (int i = 0; i < n; i++) {
                        if (contains(sub, get(p, i))) {
                            query.answer = OK;
                        }
                    }
                }
            }

            int[] getSub(int[] a, int l, int r) {
                return Arrays.copyOfRange(a, l, r + 1);
            }

            int[] get(int[] p, int from) {
                int n = p.length;
                int[] a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = p[(from + i) % n];
                }
                return a;
            }

            boolean contains(int[] full, int[] sub) {
                for (int j = 0, i = 0; ; ) {
                    while (i < full.length && full[i] != sub[j]) {
                        i++;
                    }
                    if (i++ == full.length) {
                        return false;
                    }
                    if (++j == sub.length) {
                        return true;
                    }
                }
            }

        }

        class Solve {
            Query[] queries;
            int[] next;
            int[] prev;
            List<Integer>[] elementToPositions;
            int[] nextSame;
            int n;
            int q;
            int m;
            int[] p;
            int[] a;

            public Solve(int n, int m, int q, int[] p, int[] a, Query[] queries) {
                this.n = n;
                this.m = m;
                this.q = q;
                this.p = p;
                this.a = a;
                this.queries = queries;
            }

            void solve() {
                build();

                int blockCount = (m + blockSize - 1) / blockSize;
                List<Query>[] byStartBlock = new List[blockCount];
                for (int i = 0; i < blockCount; i++) {
                    byStartBlock[i] = new ArrayList<>();
                }
                int[] dp = new int[m];
                for (Query query : queries) {
                    int lBlock = query.getLBlock();
                    int rBlock = query.getRBlock();
                    if (lBlock == rBlock) {
                        boolean ok = false;
                        for (int i = query.l; i <= query.r; i++) {
                            if (prev[i] >= query.l) {
                                dp[i] = dp[prev[i]] + 1;
                            } else {
                                dp[i] = 1;
                            }
                            ok |= dp[i] == n;
                        }
                        query.answer = ok ? OK : FAIL;
                        continue;
                    }
                    byStartBlock[lBlock + 1].add(query);
                }

                int[] realStart = new int[m];
                int[] len = new int[m];
                int[] extra = new int[m];
                int[] firstPosition = new int[n];
                for (int s = 0; s < blockCount; s++) {
                    List<Query> cur = byStartBlock[s];
                    cur.sort(Comparator.comparingInt(query -> query.r));
                    int START = s * blockSize;
                    Arrays.fill(firstPosition, -1);
                    for (int i = START; i < m; i++) {
                        if (firstPosition[a[i]] == -1) {
                            firstPosition[a[i]] = i;
                        }
                    }
                    int curR = START - 1;
                    int maxLen = 1;
                    for (Query query : cur) {
                        while (curR < query.r) {
                            curR++;
                            if (prev[curR] >= START) {
                                realStart[curR] = realStart[prev[curR]];
                                int curLen = len[prev[curR]] + 1;
                                extra[realStart[curR]] = Math.max(extra[realStart[curR]], curLen);
                                len[curR] = curLen;
                                maxLen = Math.max(maxLen, curLen);
                            } else {
                                int parent = firstPosition[a[curR]];
                                realStart[curR] = parent;
                                extra[realStart[curR]] = Math.max(extra[realStart[curR]], 1);
                                len[curR] = 1;
                            }
                        }
                        int curMaxLen = maxLen;
                        for (int i = START - 1; i >= query.l; i--) {
                            if (next[i] == -1 || next[i] > query.r) {
                                extra[i] = 1;
                            } else {
                                extra[i] = 1 + extra[next[i]];
                                if (a[realStart[next[i]]] == a[i]) {
                                    extra[i] = Math.max(extra[i], extra[realStart[next[i]]]);
                                }
                                if (nextSame[i] != -1 && nextSame[i] <= query.r) {
                                    extra[i] = Math.max(extra[i], extra[nextSame[i]]);
                                }
//                            extra[i] = Math.max(extra[i], extra[realStart[next[i]]]);
                            }
                            realStart[i] = i;
                            curMaxLen = Math.max(curMaxLen, extra[i]);
                        }
                        query.answer = curMaxLen >= n ? OK : FAIL;
                    }
                }

            }

            void build() {
                int[] pos = new int[n];
                for (int i = 0; i < n; i++) {
                    pos[p[i]] = i;
                }

                next = new int[m];
                int[] lastPos = new int[n];
                Arrays.fill(lastPos, -1);
                for (int i = m - 1; i >= 0; i--) {
                    int x = a[i];
                    int y = p[(pos[x] + 1) % n];
                    next[i] = lastPos[y];
                    lastPos[x] = i;
                }

                prev = new int[m];
                int[] firstPos = new int[n];
                Arrays.fill(firstPos, -1);
                for (int i = 0; i < m; i++) {
                    int x = a[i];
                    int y = p[(pos[x] - 1 + n) % n];
                    prev[i] = firstPos[y];
                    firstPos[x] = i;
                }

                elementToPositions = new List[n];
                for (int i = 0; i < n; i++) {
                    elementToPositions[i] = new ArrayList<>();
                }
                for (int i = 0; i < m; i++) {
                    elementToPositions[a[i]].add(i);
                }

                nextSame = new int[m];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < elementToPositions[i].size(); j++) {
                        int nextAt = j + 1 == elementToPositions[i].size() ? -1 : elementToPositions[i].get(j + 1);
                        nextSame[elementToPositions[i].get(j)] = nextAt;
                    }
                }
            }

        }

        class Query {
            int index;
            int l;
            int r;
            int answer;

            Query(int index, int l, int r) {
                this.index = index;
                this.l = l;
                this.r = r;
            }

            int getLBlock() {
                return getBlock(l);
            }

            int getRBlock() {
                return getBlock(r);
            }

            public String toString() {
                return "Query{" +
                        "index=" + index +
                        ", l=" + l +
                        ", r=" + r +
                        ", answer=" + answer +
                        '}';
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void print(int i) {
            writer.print(i);
        }

    }

    static class MiscUtils {
        public static void decreaseByOne(int[]... arrays) {
            for (int[] array : arrays) {
                for (int i = 0; i < array.length; i++) {
                    array[i]--;
                }
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = readInt();
            }
            return array;
        }

        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 int readInt() {
            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 boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

