← 返回题目列表

Codeforces · 792/C

C. 除以三

中文机器翻译题面 查看原题

黑板上写着一个正整数n。它由不超过 105 位数字组成。你必须通过擦除一些数字来将它变成一个漂亮的数字,并且你想要擦除尽可能少的数字。

如果该数字至少由一位数字组成、没有前导零并且是 3 的倍数,则该数字被称为漂亮数字。例如,0、99、10110 是漂亮数字,而 00、03、122 则不是。

编写一个程序,对于给定的 n 会找到一个漂亮的数字,这样 n 就可以通过删除尽可能少的数字来转换为这个数字。您可以删除任意一组数字。例如,他们不必在数字n中依次走下去。

如果无法获得漂亮的数字,则打印 -1。如果有多个答案,请打印其中任何一个。

输入

输入的第一行包含 n — 一个不带前导零的正整数 (1 ≤ n < 10100000)。

输出

打印一个数字——通过删除尽可能少的数字而获得的任何漂亮的数字。如果没有答案,则打印 - 1。

示例

输入 #1

1033

输出 #1

33

输入 #2

10

输出 #2

0

输入 #3

11

输出 #3

-1

注意

在第一个示例中,仅删除第一位数字就足以获得 3 的倍数。但是如果我们删除第一位数字,那么我们将获得一个带有前导零的数字。所以要擦除的最少位数是两位。