Năm 2019 là một năm rất thành công của phim truyền hình Việt Nam, rất nhiều bộ phim đã được
khán giả yêu thích và đón nhận. Năm nay, đạo diễn Vinh mới hoàn thành việc quay một bộ phim
truyền hình dài tập mới gồm \(n\) phân đoạn, mỗi phân đoạn kéo đài \(1\) phút. Trước khi đến với công
chúng, bộ phim cần trải qua giai đoạn hậu kì. Sau khi kiểm tra lại \(n\) phút phim, đạo diễn Vinh đánh
dấu phân đoạn \(i\) với giá trị \(a_i (1\le i \le n,0 \le a_i \le 2)\), trong đó:

• \(a_i=0\) có ý nghĩa phân đoạn thứ \(i\) là phân đoạn không quan trọng, có thể cắt đi mà không
  làm ảnh hưởng đến nội dung của bộ phim;
• \(a_i = 1\) có ý nghĩa phân đoạn thứ \(i\) là phân đoạn quan trọng, không thể cắt đi;
• \(a_i = 2\) có ý nghĩa phân đoạn thứ \(i\) là phân đoạn quan trọng và rất kịch tính.
  Đạo diễn muốn giữ nguyên thứ tự của các phân đoạn, cắt bỏ đi một số phân đoạn không cẩn thiết rồi
  cắt các phân đoạn côn lại thành \(k\) tập phim thỏa mãn hai điều kiện sau
  1) Mỗi tập phim phải được kết thúc bằng phân đoạn kịch tính (\(a_i = 2\)) đề gây hiệu ứng cho
  khán giả tiếp tục theo dõi tập sau.
  2) Chênh lệch độ dài giữa tập dài nhất và tập ngắn nhất là nhỏ nhất có thể được.

Input

• Vào từ thiết bị vào chuẩn có khuôn dạng:
• Dòng đâu tiên ghi 2 số nguyên dương \(n\) và \(k\);

• Dòng thứ hai ghi \(n\) số \(a_1, a_2,..., a_n\);

• Dữ liệu đảm bảo có ít nhất \(k\) giá trị \(a_i = 2\) và \(a_n = 2\)

Output

• Ghi ra thiết bị ra chuẩn theo khuôn dạng:

• Dòng đầu tiên ghi số \(T\) là chênh lệch nhỏ nhất giữa tập dài nhất và tập ngắn nhất;

• Dòng thứ hai ghi \(n\) số \(b_i\) với ý nghĩa: \(b_i = 0\) không sử dụng phân đoạn thứ \(i\), còn \(b_i > 0\)
  tương ứng với phân đoạn thứ \(i\) nằm ở tập \(b_i\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10; k \le n\);

• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100; k \le min (3,n)\);

• Subtask \(3\) (\(20\%\) số điểm): \(n \le 1000; \le min (10,n)\);

• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5;k \le min (1000,n)\);

• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^6; k \le min(1000,n)\).

Example

12 2
1 2 0 1 1 1 2 1 0 1 2 2

1
1 1 0 1 1 1 1 2 2 2 2 2