Недавно Линэрд и Скинэрд отправились в магазин, где Линэрд купил себе перестановку \(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\).
Выходные данные
В единственной строке выведите строку длины \(q\), состоящую из \(0\) и \(1\), при этом на \(i\)-й позиции должна стоять \(1\), если у подотрезка массива \(a\) c \(l_i\)-й по \(r_i\)-ю позицию включительно есть подпоследовательность, которая является циклическим сдвигом \(p\), и \(0\) в противном случае.
Примечание
В первом примере отрезок с \(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\), его подпоследовательности не совпадает ни с каким циклическим сдвигом перестановки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5
|
110
|
|
2
|
2 4 3
2 1
1 1 2 2
1 2
2 3
3 4
|
010
|