Загадка древних Ассасинов

시간 제한2초메모리 제한1024 MB

요약

주어진 숫자들을 골라 재배열해 3으로 나누어지는 가장 큰 수를 만들되, 앞에 오는 0도 허용한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 정렬, 정수론
정답자: 아직 제출이 없습니다

문제

Древние ассасины часто прятали свои секреты за загадками, которые могут решить только истинные ассасины.

Так например, чтобы открыть комнату с реликвиями испанского братства времен Агилара де Нерха, нужно из набора цифр составить наибольшее возможное число, которое будет делится на три без остатка. При этом, число может начинаться с ведущих нулей, и при равных значениях большим считается более длинное. Например, <<00021>> считается большим, чем <<021>>.

Каллум Линч нашел исходный набор цифр, из которых нужно составить ключ, но он оказался довольно длинным. Ваша задача помочь ему по данному набору цифр найти наибольшее число, состоящее из этих цифр, которое делится на три без остатка.

입력

В единственной строке входного файла находится строка, состоящая из цифр от $0$ до $9$ --- набор цифр, из которых предлагается собрать решение загадки. Длина строки не меньше трех и не превосходит $10^5$ .

출력

В выходной файл выведите наибольшее число, которое можно составить из данных цифр, чтобы оно делилось на три без остатка.

예제4

예제 1
입력
```
105
```
예상 출력
```
510
```
예제 2
입력
```
2222
```
예상 출력
```
222
```
예제 3
입력
```
000
```
예상 출력
```
000
```
예제 4
입력
```
54321
```
예상 출력
```
54321
```