Bessie có một xâu nhị phân ẩn \(b_1b_2\dots b_N\) (\(1\le N\le 2\cdot 10^5\)). Thông tin duy nhất được cung cấp về \(b\) là một xâu nhị phân \(r_1r_2\dots r_{N-K+1}\) (\(1\le K\le N\)), trong đó \(r_i\) là số dư khi chia cho hai số lượng bit \(1\) trong cửa sổ độ dài \(K\) của \(b\) có chỉ số ngoài cùng bên trái là \(i\).

Hãy in số lượng bit \(1\) nhỏ nhất và lớn nhất có thể có trong xâu nhị phân ẩn của Bessie.

Dữ liệu vào

Có \(T\) (\(1\le T\le 10^3\)) bộ test độc lập cần giải quyết. Mỗi bộ test được mô tả như sau:

Dòng đầu tiên chứa \(N\) và \(K\).

Dòng thứ hai chứa xâu nhị phân \(r_1\dots r_{N-K+1}\), trong đó \(r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}\).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in số lượng bit \(1\) nhỏ nhất và lớn nhất có thể có trong xâu nhị phân ẩn của Bessie, cách nhau bởi đúng một dấu cách.

Ví dụ

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000

3 3
2 3
1 4
0 4
1 5
1 3
0 5

Phân nhóm

• Input 2: \(N\le 8\).
• Inputs 3–4: \(K\le 8\) và tổng \(N\) trên tất cả các bộ test không vượt quá \(10^4\).
• Inputs 5–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Sliding Window Summation”, tác giả Benjamin Qi: https://usaco.org/index.php?page=viewproblem2&cpid=1544