Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
У Пети есть число из n цифр без лидирующих нулей. Он представил его в виде массива цифр d (нумерация с 1, начиная от старших цифр). Петя хочет k раз выполнить следующую операцию: найти минимальное x (1 ≤ x < n) такое, что dx = 4 и dx + 1 = 7, если x нечетное, то присвоить dx = dx + 1 = 4, иначе присвоить dx = dx + 1 = 7. Учтите, что если x не нашлось, то операция засчитывается как выполненная, и массив не меняется вообще.
Вам дано исходное число (в виде массива цифр) и число k. Помогите Пете узнать результат выполнения k операций.
Примечание
В первом примере число меняется в следующей последовательности: 4727447 → 4427447 → 4427477 → 4427447 → 4427477.
Во втором примере: 4478 → 4778 → 4478.