Số tốt nhất

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

Đề bài

Cho một số tự nhiên $N$. Số $N$ được viết dưới dạng một dãy chữ số và chỉ gồm các chữ số từ $1$ đến $9$.

Bạn được phép xóa một số chữ số của $N$, có thể không xóa chữ số nào. Các chữ số còn lại phải giữ nguyên thứ tự tương đối ban đầu.

Ví dụ, từ số $52731$ có thể tạo thành $573$ bằng cách xóa chữ số $2$ và chữ số $1$, nhưng không thể tạo thành $753$ vì thứ tự các chữ số đã thay đổi.

Hãy tạo ra số có giá trị lớn nhất có thể và chia hết cho $3$ bằng cách xóa một số chữ số của $N$.

Nếu không thể tạo được số nào chia hết cho $3$, in 0.

Input

Một dòng duy nhất chứa số tự nhiên $N$.

Mỗi chữ số của $N$ nằm trong khoảng từ $1$ đến $9$.

Output

In số lớn nhất chia hết cho $3$ có thể tạo được theo yêu cầu. Nếu không tồn tại, in 0.

Subtask

• Subtask 1 (30%): $N$ có không quá $10$ chữ số.
• Subtask 2 (30%): $N$ có không quá $100$ chữ số.
• Subtask 3 (40%): $N$ có không quá $10^5$ chữ số.

Ví dụ 1

Input

369

Output

369

Giải thích

$369$ đã chia hết cho $3$ nên có thể giữ nguyên toàn bộ số.

Ví dụ 2

Input

232

Output

3

Giải thích

Trong các số có thể tạo được và chia hết cho $3$, số lớn nhất là $3$.

Ví dụ 3

Input

25

Output

0

Giải thích

Không thể giữ lại một dãy chữ số không rỗng nào để tạo thành số chia hết cho $3$.

Ví dụ 4

Input

1234

Output

234

Giải thích

Xóa chữ số $1$ thu được $234$, và $234$ chia hết cho $3$.