One day Om Nom found a thread with n beads of different colors. He decided to cut the first several beads from this thread to make a bead necklace and present it to his girlfriend Om Nelly.

<image>

Om Nom knows that his girlfriend loves beautiful patterns. That's why he wants the beads on the necklace to form a regular pattern. A sequence of beads S is regular if it can be represented as S = A + B + A + B + A + ... + A + B + A, where A and B are some bead sequences, " + " is the concatenation of sequences, there are exactly 2k + 1 summands in this sum, among which there are k + 1 "A" summands and k "B" summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn't mind if A or B is an empty sequence.

Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn't change their order.

Input

The first line contains two integers n, k (1 ≤ n, k ≤ 1 000 000) — the number of beads on the thread that Om Nom found and number k from the definition of the regular sequence above.

The second line contains the sequence of n lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

Output

Print a string consisting of n zeroes and ones. Position i (1 ≤ i ≤ n) must contain either number one if the first i beads on the thread form a regular sequence, or a zero otherwise.

Examples

Input

7 2
bcabcab


Output

0000011

Input

21 2
ababaababaababaababaa


Output

000110000111111000011

Note

In the first sample test a regular sequence is both a sequence of the first 6 beads (we can take A = "", B = "bca"), and a sequence of the first 7 beads (we can take A = "b", B = "ca").

In the second sample test, for example, a sequence of the first 13 beads is regular, if we take A = "aba", B = "ba".
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
const long long INFL = LLONG_MAX;
const long double pi = acos(-1);
int N, K;
string s;
int ans[1001001];
int z[1001001];
int main() {
  ios_base::sync_with_stdio(0);
  cout.precision(15);
  cout << fixed;
  cout.tie(0);
  cin.tie(0);
  cin >> N >> K >> s;
  int L = 0, R = 0;
  for (int i = 1; i < N; i++) {
    if (i > R) {
      L = R = i;
      while (R < N && s[R - L] == s[R]) R++;
      z[i] = R - L;
      R--;
    } else {
      int k = i - L;
      if (z[k] < R - i + 1) {
        z[i] = z[k];
      } else {
        L = i;
        while (R < N && s[R - L] == s[R]) R++;
        z[i] = R - L;
        R--;
      }
    }
  }
  for (int lenAB = 1; lenAB <= N; lenAB++) {
    int all = 1;
    int cur = lenAB;
    for (int(i) = 0, j123 = K - 1; (i) < j123; (i)++) {
      if (cur >= N) {
        all = 0;
        break;
      }
      if (cur + lenAB - 1 < N) {
        all &= (z[cur] >= lenAB);
      } else {
        all &= (z[cur] == N - cur);
      }
      cur += lenAB;
    }
    if (lenAB == 2) {
    }
    if (all) {
      int l = lenAB * K - 1;
      int r = l + min(lenAB, z[K * lenAB]);
      if (l < N) {
        ans[l]++;
        ans[min(N, r) + 1]--;
      }
    }
  }
  for (int(i) = 0, j123 = N; (i) < j123; (i)++)
    if (i >= 1) ans[i] += ans[i - 1];
  for (int(i) = 0, j123 = N; (i) < j123; (i)++) cout << (ans[i] > 0);
  cout << '\n';
}
