Truy vấn mảng

Cho dãy gồm $N$ phần tử $a_1, a_2, \dots, a_N$. Bạn cần thực hiện $P$ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Loại 1: Dịch chuyển phần tử ở vị trí thứ $N$ về vị trí thứ 1, các phần tử còn lại dịch sang phải một vị trí;
• Loại 2: Tìm đoạn con độ dài $K$ có nhiều phần tử giá trị bằng 1 nhất. In ra số lượng phần tử giá trị 1 trong đoạn tìm được.

• Dòng 1: Chứa ba số nguyên dương $N, K, P$ ($1 \le N, K, P \le 100000$);
• Dòng 2: Chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 1; 1 \le i \le N$);
• Dòng 3: Chứa một xâu bao gồm $P$ ký tự, ký tự thứ $i$ ($1 \le i \le N$) mô tả truy vấn thứ $i$ với ký tự '!' mô tả truy vấn loại 1 và ký tự '?' mô tả truy vấn loại 2.

• Đối với mỗi truy vấn loại 2, in ra một dòng riêng biệt gồm một số nguyên là câu trả lời cho truy vấn tương ứng theo đúng thứ tự đầu vào.

• Subtask 1: 28% số điểm có xâu mô tả truy vấn chỉ bao gồm đúng một ký tự '?';
• Subtask 2: 07% số điểm có $1 \le N, K, P \le 100$;
• Subtask 3: 09% số điểm có $1 \le N, K, P \le 1000$;
• Subtask 4: 56% số điểm không có thêm ràng buộc bổ sung.