Chia hết cho 3

Cho một số nguyên dương $n$ được viết trên bảng, gồm không quá ${10}^5$ chữ số và không có chữ số $0$ ở đầu.

Bạn cần biến $n$ thành một số đẹp bằng cách xóa đi một số chữ số, và muốn xóa càng ít chữ số càng tốt. Các chữ số bị xóa không nhất thiết phải liền nhau.

Một số được gọi là đẹp nếu nó thỏa mãn cả ba điều kiện:

• có ít nhất một chữ số;
• không có chữ số $0$ ở đầu (riêng số $0$ gồm đúng một chữ số được coi là hợp lệ);
• chia hết cho $3$.

Ví dụ, $0$, $99$, $10110$ là các số đẹp, còn $00$, $03$, $122$ thì không.

Hãy tìm một số đẹp bất kỳ nhận được từ $n$ bằng cách xóa đi ít chữ số nhất có thể. Nếu không thể tạo ra số đẹp nào, hãy in ra $-1$. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ không có chữ số $0$ ở đầu ($1\le n<{10}^{100000}$).

Dữ liệu ra

In ra một số đẹp bất kỳ nhận được bằng cách xóa ít chữ số nhất. Nếu không tồn tại, in ra $-1$.

Ràng buộc

• $n$ có không quá ${10}^5$ chữ số.
• $n$ không có chữ số $0$ ở đầu.

Ví dụ