La Vie En Rose

Zhang 교수는 다중 패턴 매칭 문제를 풀고 싶지만, 패턴 문자열 $p = p_{1} p_{2} \ldots p_{m}$을 하나만 가지고 있다. 그래서 그는 다음 방법으로 $p$에서 가능한 한 많은 패턴 문자열을 만들어 내려고 한다.

1. $1 \le i_1 < i_2 < \ldots < i_k < |p|$이고 모든 $1 \le j < k$에 대해 $|i_{j} - i_{j + 1}| > 1$인 인덱스 $i_1, i_2, \ldots, i_k$를 고른다.
2. 모든 $1 \le j \le k$에 대해 $p_{i_{j}}$와 $p_{i_{j} + 1}$을 교환한다.

이제 문자열 $s = s_{1} s_{2} \ldots s_{n}$이 주어졌을 때, Zhang 교수는 만들어진 모든 패턴이 $s$에서 나타나는 위치를 모두 찾으려고 한다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 10^5$, $1 \le m \le \min (50\,000, n)$). $n$은 $s$의 길이, $m$은 $p$의 길이이다.

둘째 줄에 문자열 $s$, 셋째 줄에 문자열 $p$가 주어진다. 두 문자열은 모두 알파벳 소문자로만 이루어져 있다.

길이 $n$의 이진 문자열을 출력한다. $i$번째 문자가 '1'인 것과 부분 문자열 $s_{i} s_{i+1} \ldots s_{i+m-1}$이 만들어진 패턴 중 하나인 것이 필요충분조건이다. 그렇지 않으면 '0'이어야 한다.