Древние ассасины часто прятали свои секреты за загадками, которые могут решить только истинные ассасины.
Так например, чтобы открыть комнату с реликвиями испанского братства времен Агилара де Нерха, нужно из набора цифр составить наибольшее возможное число, которое будет делится на три без остатка. При этом, число может начинаться с ведущих нулей, и при равных значениях большим считается более длинное. Например, «00021» считается большим, чем «021».
Каллум Линч нашел исходный набор цифр, из которых нужно составить ключ, но он оказался довольно длинным. Ваша задача помочь ему по данному набору цифр найти наибольшее число, состоящее из этих цифр, которое делится на три без остатка.
В единственной строке входного файла находится строка, состоящая из цифр от 0 до 9 — набор цифр, из которых предлагается собрать решение загадки. Длина строки не меньше трех и не превосходит 105.
В выходной файл выведите наибольшее число, которое можно составить из данных цифр, чтобы оно делилось на три без остатка.
Первая группа тестов состоит из тестов, для которых выполняется ограничение на длину строки ≤ 10. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 балла.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение на длину строки ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 балла.
Третья группа тестов состоит из тестов, для которых выполняется ограничение на длину строки ≤ 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Четвертая группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 36 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».
105
510
2222
222
000
000
54321
54321