B. Lynyrd Skynyrd
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Линэрд и Скинэрд отправились в магазин, где Линэрд купил себе перестановку $$$p$$$ длины $$$n$$$, а Скинэрд купил себе массив $$$a$$$ длины $$$m$$$, состоящий из чисел от $$$1$$$ до $$$n$$$.

Линэрду и Скинэрду скучно, поэтому они решили задать вам $$$q$$$ вопросов, имеющих следующий вид: «есть ли у подотрезка массива $$$a$$$ c $$$l$$$-й по $$$r$$$-ю позицию включительно подпоследовательность, которая является циклическим сдвигом $$$p$$$?».

Перестановка длины $$$n$$$ — это последовательность из $$$n$$$ чисел, в которой каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

Циклический сдвиг перестановки $$$(p_1, p_2, \ldots, p_n)$$$ — это перестановка $$$(p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, p_{i - 1})$$$ для какого-то $$$i$$$ от $$$1$$$ до $$$n$$$. Так, например, у перестановки $$$(2, 1, 3)$$$ есть три различных циклических сдвига: $$$(2, 1, 3)$$$, $$$(1, 3, 2)$$$, $$$(3, 2, 1)$$$.

Подпоследовательность подотрезка массива $$$a$$$ с $$$l$$$-й по $$$r$$$-ю позицию включительно — это последовательность $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ для каких-то $$$i_1, i_2, \ldots, i_k$$$ таких, что $$$l \leq i_1 < i_2 < \ldots < i_k \leq r$$$.

Входные данные

В первой строке даны три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$) — длина перестановки $$$p$$$, длина массива $$$a$$$ и число запросов.

В следующей строке даны $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, $$$i$$$-е из них — $$$i$$$-й элемент перестановки. Каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

В следующей строке даны $$$m$$$ целых чисел от $$$1$$$ до $$$n$$$, $$$i$$$-е из них — $$$i$$$-й элемент массива $$$a$$$.

В следующих $$$q$$$ строках дано описание запросов. В $$$i$$$-й из этих строк даны два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$), означающие, что $$$i$$$-й вопрос относится к отрезку массива с $$$l_i$$$-й по $$$r_i$$$-ю позицию включительно.

Выходные данные

В единственной строке выведите строку длины $$$q$$$, состоящую из $$$0$$$ и $$$1$$$, при этом на $$$i$$$-й позиции должна стоять $$$1$$$, если у подотрезка массива $$$a$$$ c $$$l_i$$$-й по $$$r_i$$$-ю позицию включительно есть подпоследовательность, которая является циклическим сдвигом $$$p$$$, и $$$0$$$ в противном случае.

Примеры
Входные данные
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5
Выходные данные
110
Входные данные
2 4 3
2 1
1 1 2 2
1 2
2 3
3 4
Выходные данные
010
Примечание

В первом примере отрезок с $$$1$$$-й по $$$5$$$-ю позицию это $$$1, 2, 3, 1, 2$$$. В нём есть подпоследовательность $$$1, 3, 2$$$, которая является циклическим сдвигом перестановки. В отрезке с $$$2$$$-й по $$$6$$$-ю позицию есть подпоследовательность $$$2, 1, 3$$$, совпадающая с перестановкой. Отрезок с $$$3$$$-й по $$$5$$$-ю позицию это $$$3, 1, 2$$$, в нём есть только одна подпоследовательность длиной $$$3$$$ ($$$3, 1, 2$$$), но она не совпадает ни с каким циклическим сдвигом перестановки.

Во втором примере у перестановки циклические сдвиги это $$$1, 2$$$ и $$$2, 1$$$. Отрезок с $$$1$$$-й по $$$2$$$-ю позицию это $$$1, 1$$$, его подпоследовательности не совпадает ни с каким циклическим сдвигом перестановки. Отрезок с $$$2$$$-й по $$$3$$$-ю позицию это $$$1, 2$$$, он совпадает с перестановкой. Отрезок с $$$3$$$-й по $$$4$$$-ю позицию это $$$2, 2$$$, его подпоследовательности не совпадает ни с каким циклическим сдвигом перестановки.