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

문제

Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string $p = p_{1} p_{2} \ldots p_{m}$. So, he wants to generate as many pattern strings as possible from $p$ using the following method: 

  1. select some indices $i_1, i_2, \ldots, i_k$ such that $1 \le i_1 < i_2 < \ldots < i_k < |p|$ and $|i_{j} - i_{j + 1}| > 1$ for all $1 \le j < k$.
  2. swap $p_{i_{j}}$ and $p_{i_{j} + 1}$ for all $1 \le j \le k$.

Now, for a given a string $s = s_{1} s_{2} \ldots s_{n}$, Professor Zhang wants to find all occurrences of all the generated patterns in $s$.

입력

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le \min (50\,000, n)$): the lengths of $s$ and $p$, respectively.

The second line contains the string $s$, and the third line contains the string $p$. Both strings consist only of lowercase English letters.

출력

Output a binary string of length $n$. The $i$-th character must be '1' if and only if the substring $s_{i} s_{i+1} \ldots s_{i+m-1}$ is one of the generated patterns. Otherwise, the character must be '0'.

예제 입력 1

4 1
abac
a

예제 출력 1

1010

예제 입력 2

4 2
aaaa
aa

예제 출력 2

1110

예제 입력 3

9 3
abcbacacb
abc

예제 출력 3

100100100