Tân Kỳ-Bài 4: Hoán vị số

Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số 30. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được các giải mã các con số đó: hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của 30.

Yêu cầu:

Viết chương trình để giúp các chuyên gia giải mã các số bí ẩn đó.

Dữ liệu vào:

Từ tệp văn bản HV.inp gồm một dòng duy nhất chứa số nguyên dương ~N~, với ~N~ có chứa tối đa ~10^7~ chữ số là số cần giải mã.

Kết quả:

Ghi ra tệp HV.out gồm một số nguyên duy nhất là số lớn nhất chia hết cho ~30~ tìm được bằng cách hoán vị các chữ số của ~N~. Nếu không tìm thấy thì đưa ra ~-1~.

Ví dụ:

Giới hạn:

• Có 50% số test : ~N≤10^9~
• Có 50% số test còn lại: ~N~ có tối đa ~10^7~ chữ số