假设我们固定了一个长度为 $n$ 的排列 $p$。我们称一个长度为 $n$ 的字符串 $t$ 为 $p$-drome，如果对于该字符串的所有字符，满足 $t_i = t_{p_i}$。

给定一个字符串 $s$ 和一个排列 $p$。对于 $s$ 的每一个长度为 $n$ 的子串，你需要判断它是否为 $p$-drome。

输入格式

第一行包含三个整数 $n, m$ 和 $c$：排列的长度、字符串的长度以及字符串的字母表大小（$1 \le n \le m \le 500\,000$；$1 \le c \le 500\,000$）。

第二行包含 $n$ 个整数 $p_i$：排列本身（$1 \le p_i \le n$；当 $i \neq j$ 时 $p_i \neq p_j$）。

第三行包含 $m$ 个整数 $s_i$：初始字符串（$1 \le s_i \le c$）。

输出格式

输出 $m - n + 1$ 个字符，中间不含空格：如果子串 $s_i \dots s_{i+n-1}$ 是 $p$-drome，则第 $i$ 个字符为“1”，否则为“0”。

样例

输入 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