Một điểm rút tiền ATM có các loại tiền giấy lần lượt như sau: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng (mỗi loại có tối đa 1000 tờ).

Một khách hàng cần rút ra một số tiền M đồng. Giả sử sau khi kiểm tra đầy đủ thông tin, ngân hàng cho phép khách rút tiền. Tuy nhiên, do quy định hệ thống ATM, số tiền rút phải lớn hơn hoặc bằng 50.000 đồng (mệnh giá thấp nhất được dùng).

Hãy tìm cách trả tiền sao cho:

• Tổng số tiền đúng bằng M
• Dùng số tờ ít nhất có thể
• Nếu có nhiều cách thì chỉ cần in một cách bất kỳ

Input

Một số nguyên dương M — là số tiền cần rút (không quá 850 triệu).

Output

• Nếu không có cách rút đúng yêu cầu, in ra: KHONG THUC HIEN DUOC
• Nếu có:
  • Dòng 1: Số lượng tờ tiền ít nhất phải trả
  • Dòng 2: Gồm 6 số nguyên là số tờ cần dùng tương ứng với các mệnh giá: 10.000đ, 20.000đ, 50.000đ, 100.000đ, 200.000đ, 500.000đ

  Ví dụ

  Input

  9870000

  Output

  23
  0 1 1 1 1 19
  

  Giải thích

  Tổng số tờ: 19 + 1 + 1 + 1 + 1 = 23

  Chi tiết theo thứ tự từ thấp đến cao:

  • 10.000đ: 0 tờ
  • 20.000đ: 1 tờ
  • 50.000đ: 1 tờ
  • 100.000đ: 1 tờ
  • 200.000đ: 1 tờ
  • 500.000đ: 19 tờ

  Ràng buộc

  • 50000 ≤ M ≤ 850000000
  • Mỗi loại tiền chỉ có tối đa 1000 tờ