B. Lynyrd Skynyrd
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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, \ldots, p_n)$$$ is a permutation $$$(p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, 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}, \ldots, a_{i_k}$$$ for some $$$i_1, i_2, \ldots, i_k$$$ such that $$$l \leq i_1 < i_2 < \ldots < i_k \leq r$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 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 \le l_i \le r_i \le 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.