Tối tiểu hóa xâu nhị phân

Cho một xâu nhị phân độ dài $n$ (chỉ gồm các ký tự '0' và '1').

Trong một bước, bạn được phép hoán đổi hai ký tự kề nhau của xâu. Hỏi xâu nhỏ nhất theo thứ tự từ điển mà bạn có thể thu được nếu thực hiện không quá $k$ bước? Bạn có thể không thực hiện bước nào nếu muốn.

Lưu ý rằng bạn có thể hoán đổi cùng một cặp ký tự kề nhau (ở vị trí $i$ và $i+1$) nhiều lần tùy ý, và mỗi lần hoán đổi được tính là một bước riêng biệt.

Bạn phải trả lời $q$ truy vấn độc lập nhau.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $q$ — số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $k$ — độ dài xâu và số bước tối đa được phép thực hiện.
  • Dòng thứ hai chứa xâu nhị phân độ dài $n$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng xâu nhỏ nhất theo thứ tự từ điển thu được sau khi thực hiện không quá $k$ bước.

Ràng buộc

• $1\le q\le {10}^4$
• $1\le n\le {10}^6$
• $1\le k\le n^2$
• Tổng $n$ trên tất cả các truy vấn không vượt quá ${10}^6$.

Ví dụ