시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 1 1 1 100.000%

문제

Let's suppose that we have fixed a permutation $p$ with length $n$. We say that a string $t$ is a $p$-drome if it has the length $n$, and for all the characters of this string, it is true that $t_i = t_{p_i}$.

You have a string $s$ and a permutation $p$. For each substring of $s$ of length $n$, you have to find out if it is a $p$-drome or not.

입력

On the first line, you are given three integers $n$, $m$, and $c$: the length of the permutation, the length of the string and the size of the alphabet of the string ($1 \le n \le m \le 500\,000$; $1 \le c \le 500\,000$).

On the second line, you are given $n$ integers $p_i$: the permutation itsekf ($1 \le p_i \le n$; $p_i \ne p_j$ if $i \ne j$).

On the third line, you are given $m$ integers $s_i$: the initial string ($1 \le s_i \le c$).

출력

Print $m-n+1$ characters without spaces: $i$-th character must be "1" if substring $s_i \ldots s_{i+n-1}$ is a $p$-drome, and "0" otherwise.

예제 입력 1

3 5 1
1 2 3
1 1 1 1 1

예제 출력 1

111

예제 입력 2

3 7 3
3 2 1
1 2 1 3 1 2 1

예제 출력 2

10101