Divide by Three

## 题目描述 ## 在一个黑板上写着一个正整数 _n_ 。它有不超过10^5位（~~话说黑板上是怎么写下这个数的~~） 。老师给你了一个任务，把它~~魔~~改成一个 _美丽数_ ，而且因为你很懒，你非常非常的想用最小的步数把它改成一个 _美丽数_ 。 _美丽数_ ，就是一个不含前导0，是3的倍数且位数大于零的正整数。举个~~栗子~~例子，0、99、10110都是 _美丽数_ ，但00、03、122都不是。 你决定写一个程序来帮助你的老师来完成这个无聊的任务。你的要求就是用最小的步数来完成这个任务。 如果不可能通过删数来达到 _美丽数_ ，输出-1。如果有多个最优解答案，输出任意一个即可。 ## 输入输出格式 ### 输入格式： 第一行包含一个数n，一个位数小于100000位的正整数。 ### 输出格式： 输出删数后的美丽数。如果不可能得到美丽数，输出-1即可。 感谢@deadpool123 提供的翻译

A positive integer number $ n $ is written on a blackboard. It consists of not more than $ 10^{5} $ 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.

The first line of input contains $ n $ — a positive integer number without leading zeroes ( $ 1<=n&lt;10^{100000} $ ).

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

1033

33

10

0

11

-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.