Chủ tịch K dự định tổ chức một chuỗi hội nghị trong \(N\) ngày. Mỗi ngày có đúng một hội nghị, được tổ chức tại một trong ba địa điểm: địa điểm chính A hoặc một trong hai địa điểm phụ B, C.

Thông tin địa điểm được cho bởi xâu \(S\) gồm các ký tự A, B, C và ?. Với ngày thứ \(i\) (\(1 \le i \le N\)):

• Nếu ký tự thứ \(i\) của \(S\) là A, B hoặc C, hội nghị ngày đó được tổ chức tại địa điểm tương ứng.
• Nếu ký tự thứ \(i\) là ?, địa điểm tổ chức hội nghị ngày đó chưa được quyết định.

Vì hội nghị vào ngày đầu tiên và ngày thứ \(N\) dự kiến có nhiều người tham gia, hai hội nghị này đã được ấn định tổ chức tại địa điểm A.

Chủ tịch K cần chọn một trong ba địa điểm A, B, C cho mỗi hội nghị chưa có địa điểm. Để giảm việc di chuyển, ông muốn tối thiểu hóa số chỉ số \(j\) (\(1 \le j \le N-1\)) mà địa điểm của ngày thứ \(j\) khác địa điểm của ngày thứ \(j+1\).

Ông xét \(Q\) kịch bản độc lập. Trong kịch bản thứ \(k\), trong số các hội nghị chưa có địa điểm, ông phải chọn đúng \(X_k\) hội nghị tổ chức tại A, đúng \(Y_k\) hội nghị tại B và đúng \(Z_k\) hội nghị tại C. Hãy tìm số chỉ số \(j\) nhỏ nhất có thể theo yêu cầu trên cho từng kịch bản.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa xâu \(S\).
• Dòng thứ ba chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa ba số nguyên \(X_k,Y_k,Z_k\), ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) chứa số chỉ số \(j\) nhỏ nhất mà địa điểm hội nghị của ngày thứ \(j\) và ngày thứ \(j+1\) khác nhau, khi phân công các hội nghị chưa có địa điểm theo kịch bản thứ \(k\).

Ràng buộc

• \(2 \le N \le 300000\).
• \(S\) là xâu độ dài \(N\), chỉ gồm các ký tự A, B, C, ?.
• Ký tự đầu tiên và ký tự thứ \(N\) của \(S\) đều là A.
• \(1 \le Q \le 200000\).
• \(0 \le X_k\), \(0 \le Y_k\), \(0 \le Z_k\) với mọi \(1 \le k \le Q\).
• \(X_k+Y_k+Z_k\) bằng số ký tự ? trong \(S\) với mọi \(1 \le k \le Q\).
• \(N,Q,X_k,Y_k,Z_k\) đều là số nguyên.

Chấm điểm

1. \(4\) điểm: \(N \le 50\) và số ký tự ? trong \(S\) không quá \(13\).
2. \(7\) điểm: \(N \le 500\).
3. \(13\) điểm: \(N \le 5000\), \(Q \le 10\).
4. \(18\) điểm: \(N \le 5000\).
5. \(12\) điểm: \(Q \le 10\).
6. \(8\) điểm: \(S\) không chứa C và \(Z_k=0\) với mọi \(1 \le k \le Q\).
7. \(13\) điểm: \(Z_k=0\) với mọi \(1 \le k \le Q\).
8. \(25\) điểm: Không có ràng buộc bổ sung.

Ví dụ

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

3
4
4

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

4
4
2
2

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.