На день рождения Васе подарили натуральное число N. Поскольку Васе как раз исполнилось 15 лет, он захотел переставить в этом числе цифры так, чтобы полученное число делилось на 15, и при этом было как можно больше. Напишите программу, решающую эту задачу.
Выходные данные
Выведите одно натуральное число – ответ. Если решения не существует, выведите -1.
Система оценки
Подзадача 1 (до 50 баллов): число N состоит не более чем из 1000 цифр.
Подзадача 2 (до 50 баллов): число N состоит не более чем из 105 цифр.
Каждый тест в каждой подзадаче оценивается независимо.