Zhang 教授想要解决多模式匹配问题，但他只有一个模式串 $p = p_1p_2 \dots p_m$。因此，他希望通过以下方法从 $p$ 生成尽可能多的模式串：

1. 选择一些下标 $i_1, i_2, \dots, i_k$，满足 $1 \le i_1 < i_2 < \dots < i_k < |p|$ 且对于所有 $1 \le j < k$ 都有 $|i_j - i_{j+1}| > 1$。
2. 交换所有 $1 \le j \le k$ 的 $p_{i_j}$ 和 $p_{i_j+1}$。

现在，给定一个字符串 $s = s_1s_2 \dots s_n$，Zhang 教授想要找出所有生成的模式串在 $s$ 中的所有出现位置。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$, $1 \le m \le \min(50\,000, n)$)，分别表示 $s$ 和 $p$ 的长度。

第二行包含字符串 $s$，第三行包含字符串 $p$。两个字符串均仅由小写英文字母组成。

输出格式

输出一个长度为 $n$ 的二进制字符串。如果子串 $s_i s_{i+1} \dots s_{i+m-1}$ 是生成的模式串之一，则第 $i$ 个字符必须为 '1'，否则必须为 '0'。

样例

样例输入 1

4 1
abac
a

样例输出 1

1010

样例输入 2

4 2
aaaa
aa

样例输出 2

1110

样例输入 3

9 3
abcbacacb
abc

样例输出 3

100100100