На доске записано целое положительное число n, не содержащее лишних лидирующих нулей и состоящее не более чем из 105 цифр. Необходимо стереть минимальное количество цифр таким образом, чтобы получить красивое число.
Число называется красивым, если оно записано так, что содержит хотя бы одну цифру, не содержит лишних лидирующих нулей и число делится нацело на 3. Например, 0, 99, 10110 — красивые, а 00, 03, 122 — не являются красивыми.
Напишите программу, которая по заданному числу n найдет такое красивое число, которое можно получить из заданного путем вычеркивания минимального количества цифр, или сообщит, что ответа не существует. Вычеркивать из n можно произвольный набор цифр, например, эти цифры не обязаны идти подряд.
Если невозможно получить какое-либо красивое число, то выведите -1. Если ответов несколько, то выведите любой.
Выходные данные
Выведите единственное число — любое красивое число, полученное вычеркиванием минимального количества цифр. Если ответ не существует, то выведите - 1.
Примечание
В первом примере для получения числа, которое делится нацело на 3, достаточно удалить только первую цифру. Однако тогда в числе будет присутствовать лишний лидирующий ноль, который недопустим. Следовательно, минимальное количество цифр, которые надо стереть, равно двум.