文件读写

• 输入文件cancel.in
• 输出文件cancel.out

限制

• 1000ms
• 512MB

题目描述

课间，程老师带学生玩一种叫消消乐的小游戏。他在黑板上写下一串由小写字母组成的字母串，又在旁边写下一个整数 $k$，然后向全班宣布了游戏规则，请大家来玩。

游戏的黑板上始终摆着一个字母串。游戏过程中只有一种操作：如果当前字母串里存在连续 $k$ 个位置上的字母完全相同，就把这连续 $k$ 个字母作为一段，整体从黑板上擦掉。擦掉的瞬间，这一段左边剩下的字母和右边剩下的字母会直接拼到一起，形成一个新的、更短的字母串。拼合是一个需要留意的过程：原来分别位于被擦段左右两侧的字母，在拼合之后成为紧挨着的邻居；如果新的邻居关系使得字母串里再次出现连续 $k$ 个相同字母，那么这些字母同样满足操作条件，可以继续被擦掉。游戏就按照这个规则一轮接一轮地进行，每一轮擦掉一段恰好 $k$ 个的相同字母，直到黑板上不存在任何连续 $k$ 个相同字母为止。到这一步，黑板上的字母串达到稳定，游戏结束。每一次操作，黑板上的字母串长度都恰好减少 $k$ 个字母，因此游戏总会经过有限步走到结束，不会无限地进行下去。

有几处细节需要说明。其一，每次操作擦掉的是恰好 $k$ 个字母；如果某一段连续相同字母的长度超过 $k$，那么这一长段是按 $k$ 个一批、一批一批擦掉的，并不是整段一次性擦光。其二，擦掉一段之后左右立刻拼合，拼合新产生的连续 $k$ 个相同字母也要接着擦掉，不能跳过。其三，同一时刻黑板上可能同时存在多处满足条件的连续 $k$ 个相同字母，先擦哪一处由玩家自行决定，规则并不指定顺序。

可以证明：无论选择哪一处、按什么顺序擦除，最终稳定后黑板上剩下的字母串都是唯一的。

程老师把初始字母串 $s$ 和整数 $k$ 交给你，请你算出游戏稳定后黑板上剩下的字母串。

输入格式

从文件 cancel.in 中读入数据。

第一行一个字符串 $s$，表示初始字母串。

第二行一个整数 $k$，表示一次擦除的字母个数。

输出格式

输出到文件 cancel.out 中。

一行一个字符串，表示游戏稳定后黑板上剩下的字母串；若黑板最终为空，输出 EMPTY。

数据范围

特殊性质 A：$k = 2$。

特殊性质 B：任意一次擦除之后，都不会因为字母拼接而产生新的连续 $k$ 个相同字母。

对于 $100\%$ 的数据，$1 \le |s| \le 10^6$，$2 \le k \le 10^6$，$s$ 只含小写英文字母。

abba
2

EMPTY

aaabaaaa
3

ba

abccba
3

abccba

样例解释

样例 1：abba 中先擦掉中间的两个 bb，剩下的 aa 拼到一起又满足条件，被擦掉，黑板为空，输出 EMPTY。

样例 2：aaabaaaa 开头的 aaa 被擦掉，剩下 baaaa；末尾的 aaaa 按每次 $3$ 个擦掉，剩 $1$ 个 a，最终剩下 ba。