黑板上写着一个正整数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 的倍数。但是如果我们删除第一位数字,那么我们将获得一个带有前导零的数字。所以要擦除的最少位数是两位。