Mã chia hết (Divisible Code)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mã số được biểu diễn bởi xâu thập phân $S$ gồm từ $2$ đến $18$ chữ số, chữ số đầu tiên khác $0$.

Bạn phải xóa đúng một chữ số của $S$ và giữ nguyên thứ tự các chữ số còn lại. Xâu thu được được hiểu là biểu diễn thập phân của một số nguyên không âm; các chữ số $0$ ở đầu, nếu có, không làm thay đổi giá trị của số.

Hãy tìm giá trị lớn nhất chia hết cho $3$ có thể thu được sau khi xóa đúng một chữ số. Nếu không tồn tại kết quả như vậy, in -1.

Input

Một dòng duy nhất chứa xâu $S$.

Output

In một số nguyên duy nhất là giá trị lớn nhất thỏa mãn yêu cầu, hoặc -1 nếu không tồn tại.

Subtask

• Subtask 1 — 50%: $2\le |S|\le 8$, $S_1\ne 0$; $S$ chỉ gồm các chữ số từ 0 đến 9.
• Subtask 2 — 50%: $2\le |S|\le 18$, $S_1\ne 0$; $S$ chỉ gồm các chữ số từ 0 đến 9.

Ví dụ

Ví dụ 1

Input

96312

Output

9612

Giải thích

Xóa chữ số 3 thu được $9612$, chia hết cho $3$ và lớn hơn các kết quả hợp lệ khác.

Ví dụ 2

Input

11

Output

-1

Giải thích

Sau khi xóa một chữ số chỉ có thể thu được số $1$, không chia hết cho $3$.