Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tuấn rất thích số là bội số của 45. Vì vậy cứ thấy bất kỳ một số nguyên dương ~N~ nào Tuấn cũng cố gắng biến đổi số đó bằng cách thay đổi vị trí các chữ số đó để được một bội số của 45.

Cho trước số nguyên dương ~N~, hãy cho biết có thể biến đổi số đó để hợp với sở thích của Tuấn được không?

Dữ liệu vào

• Dòng duy nhất chứa số nguyên dương ~N~. Số chữ số của ~N~ không quá ~10^4~ ký tự.

Kết quả

• Nếu có thể biến đổi được thì hãy in ra số lớn nhất thỏa mãn bài toán, ngược lại thì in ~-1~.

Giới hạn

• ~N~ là số nguyên dương có từ ~1~ đến ~10^4~ chữ số (không có chữ số ~0~ ở đầu).

Sample Input 1

45

Sample Output 1

45

Sample Input 2

153

Sample Output 2

315

Sample Input 3

555554444

Sample Output 3

-1