Tại vùng đất Miền Trung Tây Nguyên, để mô phỏng sự sống, người ta sử dụng xâu nhị phân \(S\) độ dài \(n\) để mã hóa một dãy \(n\) tế bào. Các tế bào được đánh số từ \(1\) đến \(n\), tế bào thứ \(i\) được mã hóa bởi kí tự thứ \(i\) của xâu \(S\), kí hiệu là \(S_i\). Trong mọi thời điểm, \(S_i\) nhận một trong hai giá trị là \(0\) hoặc \(1\).

Dãy tế bào này sẽ biến đổi theo thời gian. Ở mỗi lần biến đổi, tất cả \(n\) tế bào sẽ thay đổi đồng thời dựa vào trạng thái của tế bào này, tế bào liền trước và tế bào liền sau tại thời điểm trước đó. Cụ thể, tế bào thứ \(i\) biến đổi như sau:

• Gọi \(L\) là trạng thái của tế bào thứ \(i-1\) trước khi biến đổi (coi \(L=0\) nếu \(i=1\))
• Gọi \(M\) là trạng thái của tế bào thứ \(i\) trước khi biến đổi
• Gọi \(R\) là trạng thái của tế bào thứ \(i+1\) trước khi biến đổi (coi \(R=0\) nếu \(i=n\))
• Tế bào thứ \(i\) sẽ biến đổi dựa trên bộ ba \(LMR\) theo quy tắc:
  • Nếu bộ ba là 111 hoặc 001, đảo ngược giá trị của \(S_i\) (tức \(S_i \leftarrow 1-S_i\))
  • Nếu bộ ba là 010 hoặc 110, \(S_i\) không thay đổi
  • Nếu bộ ba là 101 hoặc 011, \(S_i\) trở thành \(1\)
  • Khác tất cả các trường hợp trên, \(S_i\) trở thành \(0\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((2 \leq n \leq 20, k \leq 10^{18})\)
• Dòng thứ hai chứa xâu ký tự \(S\)

Output

Gồm một dòng duy nhất chứa xâu ký tự \(S\) sau \(k\) lần biến đổi.

Example

3 3
001

101

6 3
101100

101100

Scoring

• Subtask \(1\) \((10\%\) số điểm): \(q \leq 10\,000\)
• Subtask \(2\) \((15\%\) số điểm): Không có truy vấn ? u nào nằm trước các truy vấn loại khác
• Subtask \(3\) \((20\%\) số điểm): Không tồn tại truy vấn C u
• Subtask \(4\) \((25\%\) số điểm): Với mọi truy vấn A u, nếu rừng đang có \(n\) đỉnh, dữ liệu đảm bảo \(u = n\)
• Subtask \(5\) \((30\%\) số điểm): Không có ràng buộc nào thêm