Cho một xâu ~S~ chỉ gồm các kí tự 0, 1, …, 9. Hãy tìm cách bỏ đi ít nhất các kí tự sao cho xâu còn lại giữ nguyên thứ tự tạo thành một số có nghĩa (đứng đầu là số khác 0) lớn nhất và chia hết cho 3.

Dữ liệu:

Vào từ file TDIV.INP: gồm một dòng duy nhất chữa xâu kí tự ~S~ độ dài của xâu không quá 10^5 chỉ gồm các kí tự 0, 1, …, 9.

Dữ liệu ra:

Ghi ra file TDIV.OUT số có nghĩa lớn nhất chia hết cho 3 nếu không tạo được số nào thì ghi ra -1.

Ví dụ đầu vào:

1024

Đầu ra:

102

Ví dụ đầu vào 2:

020

Đầu ra:

0

Ràng buộc:

• 25% số điểm tương ứng với số test có tổng các chữ số trong xâu chia hết cho 3;
• 20% số điểm tương ứng với số test có đáp án tối ưu chỉ cần xóa đi đúng một chữ số từ xâu ban đầu;
• 25% số điểm tương ướng với số test có độ dài của xâu không quá 300;
• 30% số điểm còn lại tương ứng với số test của bài không có ràng buộc gì thêm.