C. Поделись на три!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Число называется красивым, если оно записано так, что содержит хотя бы одну цифру, не содержит лишних лидирующих нулей и число делится нацело на 3. Например, 0, 99, 10110 — красивые, а 00, 03, 122 — не являются красивыми.

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

Если невозможно получить какое-либо красивое число, то выведите -1. Если ответов несколько, то выведите любой.

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

В единственной строке задано целое положительное число n (1 ≤ n < 10100000). Заданная запись числа n не содержит лишних лидирующих нулей.

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

Выведите единственное число — любое красивое число, полученное вычеркиванием минимального количества цифр. Если ответ не существует, то выведите  - 1.

Примеры
Входные данные
1033
Выходные данные
33
Входные данные
10
Выходные данные
0
Входные данные
11
Выходные данные
-1
Примечание

В первом примере для получения числа, которое делится нацело на 3, достаточно удалить только первую цифру. Однако тогда в числе будет присутствовать лишний лидирующий ноль, который недопустим. Следовательно, минимальное количество цифр, которые надо стереть, равно двум.