19265번 - Is It a p-drome? 다국어

문제

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.

제한

힌트