你这家伙，是杀人犯呢。——蕾米莉亚·斯卡蕾特 一个人的话又不是大量屠杀，所以没关系。——博丽灵梦 退治完妖怪，灵梦从红魔馆抢来一个字符串。这是一个长度为 ，仅由小写字母构成的字符串 ，下标从 开始。灵梦有 点灵力，计划消耗灵力对字符串进行至多一次修改操作，使最终得到的字符串字典序最小。操作分为两步： 第一步，从字符串 中选取若干位置。对于每个被选中的位置 ，需要消耗 点灵力。 第二步，对于每个选中的位置，将对应字符复制一次，新复制的字符紧接原字符之后插入。例如，对于字符串 ，我们已经选中了橙色的两个位置，复制操作后，得到 。 灵梦的灵力值有限，所以她希望你帮她计算出，在消耗灵力值不超过 的情况下，最后能够得到的字典序最小的字符串是什么。 从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序较小的字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述:

第一行输入两个整数 代表字符串的长度、灵梦的灵力值。 第二行输入一个长度为 ，仅有小写字母构成的字符串 。 第三行输入 个整数 ，其中，第 个整数 代表选中位置 需要消耗的灵力值。

输出描述:

输出一个字符串，代表最后能够得到的字典序最小的字符串。