You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together. We repeatedly make k duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Input Format
String str Integer k
Output Format
String without k duplicates
Constraints
1 <= s.length <= 105 2 <= k <= 104 s only contains lower case English letters.
Notice
NA
Example
Input
abcd 2
Output
abcd