CF792C.Divide by Three

A positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautiful number by erasing some of the digits, and you want to erase as few digits as possible.

The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, 0, 99, 10110 are beautiful numbers, and 00, 03, 122 are not.

Write a program which for the given n will find a beautiful number such that n can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number n.

If it's impossible to obtain a beautiful number, print -1. If there are multiple answers, print any of them.

一个正整数 $n$ 被写在黑板上，它最多包含 $10^5$ 位数字。你需要通过擦除其中一些数字，将其变为一个“优美的数”，且希望擦除的数字尽可能少。

一个数被称为“优美”的，当且仅当它至少包含一位数字、不含有前导零，且是 $3$ 的倍数。例如，$0$、$99$、$10110$ 是优美的数，而 $00$、$03$、$122$ 不是。

请编写一个程序：对于给定的 $n$，找出一个优美的数，使得 $n$ 可以通过擦除尽可能少的数字（可任意选择擦除哪些数字，不要求连续）得到该数。

如果无法得到优美的数，则输出 $-1$；如果有多个满足条件的答案，输出任意一个即可。

The first line of input contains n — a positive integer number without leading zeroes (1 ≤ n < 10100000).

输入的第一行包含一个正整数 $n$，其十进制表示不含前导零（$1 \leq n < 10^{100000}$）。

Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print  - 1.

输出一个数字——即通过删除尽可能少的数字所得到的任意一个“优美数”。如果不存在这样的数，则输出 -1。

In the first example it is enough to erase only the first digit to obtain a multiple of 3. But if we erase the first digit, then we obtain a number with a leading zero. So the minimum number of digits to be erased is two.

在第一个例子中，只需删除第一位数字即可得到一个 3 的倍数。但如果删除第一位数字，得到的数字将带有前导零。因此，需要删除的最少数字个数为两个。