← 返回题目列表

Codeforces · 121/B

B. 幸运转型

中文机器翻译题面 查看原题

Petya 喜欢幸运数字。大家都知道,幸运数字是正整数,其十进制表示只包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 的数字由 n 位数字组成,没有前导零。他将其表示为不带前导零的数字数组。我们称其为d。计数从 1 开始,从最高位开始。 Petya 想要执行以下操作 k 次:找到最小 x (1 ≤ x < n),使得 dx = 4 且 dx + 1 = 7,如果 x 是奇数,则分配 dx = dx + 1 = 4,否则分配 dx = dx + 1 = 7。请注意,如果没有找到 x,则操作算作已完成,并且数组根本不会改变。

您将获得数字数组形式的初始数字和数字 k。帮助 Petya 求出完成 k 次运算的结果。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 109) — 数字中的位数和已完成操作的数量。第二行包含n个不带空格的数字,表示从d1开始的数字数组d。保证数字的第一位不为零。

输出

在单行中打印结果(不带空格)——完成 k 次操作后的数字。

示例

输入 #1

7 4
4727447

输出 #1

4427477

输入 #2

4 2
4478

输出 #2

4478

注意

在第一个样本中,数字按以下顺序变化:4727447 → 4427447 → 4427477 → 4427447 → 4427477。

在第二个样本中:4478 → 4778 → 4478。