Bitaro được tặng một chiếc máy JOI nhân dịp sinh nhật. Máy gồm một quả bóng, \(N\) ô phát sáng và \(M\) nút bấm. Các ô được đánh số từ \(1\) đến \(N\). Khi bật nguồn, ô \(i\) (\(1 \le i \le N\)) phát sáng với màu \(C_i\), là xanh lam (B) hoặc đỏ (R). Các nút bấm được đánh số từ \(1\) đến \(M\).

Khi Bitaro nhấn nút \(j\) (\(1 \le j \le M\)), máy thực hiện theo thứ tự sau:

1. Đặt quả bóng lên ô \(A_j\).
2. Đổi màu ô \(A_j\) thành đỏ, bất kể màu trước đó của ô này.
3. Lặp lại quá trình dưới đây cho đến khi quả bóng được lấy ra khỏi máy.

Gọi \(p\) là số hiệu ô đang chứa quả bóng. Nếu ô \(p\) có màu xanh lam, đổi ô này thành màu đỏ. Sau đó, nếu \(p = 1\), lấy quả bóng ra khỏi máy; nếu không, chuyển quả bóng sang ô \(p - 1\).

Nếu ô \(p\) có màu đỏ, đổi ô này thành màu xanh lam. Sau đó, nếu \(p = N\), lấy quả bóng ra khỏi máy; nếu không, chuyển quả bóng sang ô \(p + 1\).

Thích thú với chiếc máy, Bitaro lên kế hoạch thực hiện \(Q\) thí nghiệm. Trong thí nghiệm thứ \(k\) (\(1 \le k \le Q\)), Bitaro bật nguồn để các ô có lại màu ban đầu \(C_i\), rồi nhấn lần lượt các nút \(L_k, L_k + 1, \ldots, R_k\). Sau mỗi lần nhấn nút, cậu đợi đến khi quả bóng được lấy ra khỏi máy rồi mới nhấn nút tiếp theo.

Cho thông tin về chiếc máy và các thí nghiệm, hãy tìm số ô màu đỏ sau khi mỗi thí nghiệm kết thúc.

Dữ liệu vào

Dữ liệu vào có dạng:

N M
C_1C_2...C_N
A_1 A_2 ... A_M
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dòng thứ hai là xâu gồm \(N\) ký tự B hoặc R, không có dấu cách giữa các ký tự.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số ô màu đỏ sau khi thí nghiệm thứ \(k\) kết thúc.

Ràng buộc

• \(3 \le N \le 120\,000\).
• \(1 \le M \le 120\,000\).
• \(C_i\) là B hoặc R (\(1 \le i \le N\)).
• \(1 \le A_j \le N\) (\(1 \le j \le M\)).
• \(1 \le Q \le 120\,000\).
• \(1 \le L_k \le R_k \le M\) (\(1 \le k \le Q\)).
• \(N, M, A_j, Q, L_k, R_k\) là các số nguyên.

Chấm điểm

1. \(3\) điểm: \(N \le 300\), \(M \le 300\), \(Q = 1\).
2. \(12\) điểm: \(N \le 7000\), \(M \le 7000\), \(Q = 1\).
3. \(10\) điểm: \(Q \le 5\).
4. \(11\) điểm: \(N = 10\) và \(C_i\) là R với mọi \(1 \le i \le N\).
5. \(26\) điểm: Tồn tại số nguyên \(t\) (\(0 \le t \le N\)) sao cho \(C_i\) là R với mọi \(i \le t\) và là B với mọi \(i > t\).
6. \(17\) điểm: \(A_j \le 20\) hoặc \(A_j > N - 20\) với mọi \(1 \le j \le M\).
7. \(21\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 1
RBRRB
4
1
1 1

1

5 3
RBRBR
1 3 4
2
2 3
1 3

5
0

10 3
BBRRBRBRRB
2 10 5
1
1 3

2

10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10

4
8
10
0
9

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

2
6
0
10
7

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

21
15
15
4
17
16
14
20
12
23

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.