Strange Cipher Code

Interview

Time limit1sMemory limit1024 MB

Summary

Split a string into case-insensitive runs of equal letters, map each run to 1 if its length is at least K and 0 otherwise, and drop later runs whose letter already appeared.

Level: Easy3 of 10
Topics: String, Implementation, Simulation, Hash map
Solved: No attempts yet

Problem

Hwang Tolic, a cat living at The Catholic University of Korea, likes Eom Comgong, the cat next door. Eom Comgong converts strings made only of alphabet letters into a strange cipher. To convert a string into the strange cipher, the following steps are followed.

First, the input string is split into blocks by grouping consecutive occurrences of the same alphabet letter from left to right, ignoring case. Then, starting from the left, each block is processed with the rules below.

If a block has length at least K, replace the block with the single integer 1.
If a block has length less than K, replace the block with the single integer 0.
If a block's alphabet letter has already been replaced by 0 or 1 before, delete the block.

Hwang Tolic wants to win Eom Comgong's heart and plans to write code that converts a given string into the strange cipher. Help Hwang Tolic win that heart!

Input

A string S and a positive integer K are given. (1 ≤ K ≤ length of string S ≤ 2,000)

Output

Print the string produced by the cat language rules.

Examples3

Example 1
Input
```
AAAABBBC 3
```
Expected output
```
110
```
Example 2
Input
```
aaabaaaaa 3
```
Expected output
```
10
```

Example 3

Input

QQqqqqwwwffFAACCvvVaaaAhhHMOSS 8

Expected output

0000000000