Cho một số tự nhiên ~S~ và một số tự nhiên ~K~. Hãy thay đổi tối đa ~K~ chữ số của ~S~ để tạo ra một số tự nhiên ~X~ ~(X > 0)~ nhỏ nhất chia hết cho ~3~ (không có số ~0~ ở đầu).

Dữ liệu

• Dòng đầu tiên chứa một số tự nhiên ~S~ có không quá ~15~ chữ số;
• Dòng thứ hai chứa một số tự nhiên ~K~ ~(1 \le K ≤ 15)~.

Kết quả

• Một số tự nhiên là số ~X~ mới thoả mãn yêu cầu đề bài.

Chấm điểm

• Có 40% số test ứng với 40% số điểm có: ~K = 1~;
• 30% số test khác ứng với 30% số điểm có: ~S ≤ 10^5~;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Input

2024
1

Sample Output

2004