Загадка древних Ассасинов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
divisible.in
вывод
divisible.out

Древние ассасины часто прятали свои секреты за загадками, которые могут решить только истинные ассасины.

Так например, чтобы открыть комнату с реликвиями испанского братства времен Агилара де Нерха, нужно из набора цифр составить наибольшее возможное число, которое будет делится на три без остатка. При этом, число может начинаться с ведущих нулей, и при равных значениях большим считается более длинное. Например, «00021» считается большим, чем «021».

Каллум Линч нашел исходный набор цифр, из которых нужно составить ключ, но он оказался довольно длинным. Ваша задача помочь ему по данному набору цифр найти наибольшее число, состоящее из этих цифр, которое делится на три без остатка.

Входные данные

В единственной строке входного файла находится строка, состоящая из цифр от 0 до 9 — набор цифр, из которых предлагается собрать решение загадки. Длина строки не меньше трех и не превосходит 105.

Выходные данные

В выходной файл выведите наибольшее число, которое можно составить из данных цифр, чтобы оно делилось на три без остатка.

Система оценки

Первая группа тестов состоит из тестов, для которых выполняется ограничение на длину строки  ≤ 10. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 балла.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение на длину строки  ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 балла.

Третья группа тестов состоит из тестов, для которых выполняется ограничение на длину строки  ≤ 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.

Четвертая группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 36 баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».

Примеры

Входные данные
105
Выходные данные
510
Входные данные
2222
Выходные данные
222
Входные данные
000
Выходные данные
000
Входные данные
54321
Выходные данные
54321