Chia hết 36

Cho một số tự nhiên $N$. Bạn được phép hoán vị (sắp xếp lại) vị trí các chữ số của $N$ để tạo thành một số tự nhiên mới.

Hãy tìm số tự nhiên có giá trị nhỏ nhất có thể tạo thành sao cho số đó chia hết cho $36$ và không có chữ số $0$ vô nghĩa ở đầu. Nếu không thể tạo ra bất kỳ số nào thỏa mãn điều kiện, hãy in ra $-1$.

Dữ liệu vào

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

Dữ liệu ra

• Một số duy nhất là kết quả của bài toán (số nhỏ nhất chia hết cho $36$ được tạo thành). Nếu không tồn tại số thỏa mãn, in ra $-1$.

Ràng buộc

• Số lượng chữ số của $N$ nằm trong khoảng từ $1$ đến ${10}^5$.
• $N\ge 0$ và không có chữ số $0$ vô nghĩa ở đầu (trừ trường hợp $N=0$).
• Có $80\%$ số test tương ứng với $80\%$ số điểm thỏa mãn: số chữ số của $N\le {10}^3$.
• $20\%$ số test còn lại tương ứng với $20\%$ số điểm không có ràng buộc gì thêm.

Ví dụ