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 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.
### Constraints
- `1 <= s.length <= 10^5`
- `2 <= k <= 10^4`
- `s` consists only of lowercase English letters.
### Input Format
First line contains the string `s`.
Second line contains the integer `k`.
### Output Format
Print the resulting string. If empty, print an empty line.
Sample Cases
Example 1Sample Case
Input: abcd
2
Output: abcd
Example 2Sample Case
Input: deeedbbcccbdaa
3
Output: aa
Example 3Sample Case
Input: a
2
Output: a
Example 4Sample Case
Input: d
3
Output: d
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.