Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Пете на день рождения подарили массив из n чисел. Сейчас он хочет отсортировать его по неубыванию. Но выполнять обычную сортировку скучно, поэтому Петя придумал ограничение: можно менять местами любые два числа, но только если хотя бы одно из них — счастливое. Ваша задача — отсортировать массив, учитывая заданное ограничение. Найдите любую возможную последовательность обменов, количество операций в которой не превышает 2n.