Divide by Three

题面翻译

题目描述

在一个黑板上写着一个不超过 $10^5$ 位的非负整数 $n$。你想通过删掉它的一些数字把它改成一个美丽数。

美丽数就是一个不含前导 $0$，是 $3$ 的倍数且位数大于零的非负整数。$0$、$99$、$10110$ 都是美丽数，但 $00$、$03$、$122$ 都不是。

请你写一个程序来完成这个任务，要求删去数字最少，其中删掉的数字不必相邻。

如果不可能通过删数来达到美丽数，输出 $-1$。如果有多个最优解，输出任意一个即可。

输入格式

第一行包含一个数 $n$，其中 $1\leq n\leq 10^{100000}$。

输出格式

输出删数后的美丽数。如果不可能得到美丽数，输出 $-1$ 即可。

# Divide by Three

## 题面翻译

### 题目描述
在一个黑板上写着一个不超过 $10^5$ 位的非负整数 $n$。你想通过删掉它的一些数字把它改成一个美丽数。

美丽数就是一个不含前导 $0$，是 $3$ 的倍数且位数大于零的非负整数。$0$、$99$、$10110$ 都是美丽数，但 $00$、$03$、$122$ 都不是。

请你写一个程序来完成这个任务，要求删去数字最少，其中删掉的数字不必相邻。

如果不可能通过删数来达到美丽数，输出 $-1$。如果有多个最优解，输出任意一个即可。

### 输入格式
第一行包含一个数 $n$，其中 $1\leq n\leq 10^{100000}$。

### 输出格式
输出删数后的美丽数。如果不可能得到美丽数，输出 $-1$ 即可。