Treasure

Interview

Time limit1sMemory limit512 MB

Summary

Repeatedly delete the first run of exactly K equal consecutive letters until no such run remains, and print the final string.

Level: Medium6 of 10
Topics: Stack, String, Implementation, Simulation
Solved: No attempts yet

Problem

Andrei is an adventurer who tries to find a treasure full of gold coins. When he arrives at the last clue, which will tell him where the treasure is, he sees that on the clue there are two numbers, N and K, and a string of N lowercase English letters. Andrei should take the current string and should eliminate the first sequence of exactly K identical letters which appear on consecutive positions. He will repeat this process until there will be no sequence which has K consecutive identical letters.

Andrei asks you to solve this problem as soon as possible so that he will be the first who discovers the treasure.

Find the final string after you successively eliminate the first sequence of K identical letters which appear on consecutive positions, until there is no such sequence left.

Input

The first line of the input contains two integers, N, representing the number of characters of the string, and K, representing the length of a sequence of identical characters.

The second line of the input contains the string of N lowercase English letters.

Output

The first line of the output contains a string of lowercase English letters, the string which will be obtained after all the possible eliminations are made.

Constraints

2 ≤ K ≤ N ≤ 200,000
The initial string contains only lowercase English letters
It is guaranteed that the final string is not empty!

Examples2

Example 1
Input
```
5 2
abbac
```
Expected output
```
c
```
Example 2
Input
```
12 3
aabbbaabbaac
```
Expected output
```
abbaac
```