Giải bài trực tuyến

Một từ trong tiếng Việt được cấu tạo nên từ các âm tiết. Khi cho một câu trong tiếng Việt, việc tách các âm tiết thành các từ riêng biệt là một công việc cần thiết nhưng không đơn giản. Chẳng hạn câu: “Ông già đi nhanh quá” có thể được tách thành “/Ông/ già đi /nhanh / quá/” hoặc “Ông già/ đi / nhanh /quá”. Bạn là trợ lý của giáo sư có danh tiếng, công việc của bạn là giúp giáo sư viết một chương trình tách từ. Phần cốt lõi của chương trình là việc mô tả một cấu trúc dữ liệu cho phép thực hiện ba thao tác cơ bản trên 1 dãy n đơn âm cho trước (các đơn âm được đánh số lần lượt từ 1 tới n, theo thứ tự từ trái qua phải). Hai đơn âm cạnh nhau có thể được nối, hoặc không nối với nhau, một từ là một dãy đơn âm liên tiếp (cực đại) nối với nhau. Các thao tác trên cấu trúc dữ liệu bao gồm:

J i j: Nối từ đơn âm thứ i tới đơn âm thứ j với nhau

D i j: Tách các đơn âm từ đơn âm thứ i tới đơn âm thứ j (i ≤ j )

C: Đòi hỏi trả về số lượng từ ( số lượng dãy đơn âm nối nhau)

Chẳng hạn với n = 4 và trạng thái hiện tại của dãy đơn âm đang là ( 1_2 3_4 ) :

J 2 3 { Dãy đơn âm sẽ biến đổi thành: 1_2_3_4 }

D 2 4 { Dãy đơn âm sẽ biến đổi thành: 1_2 3 4 }

C { Trả về giá trị: 3 , do có ba từ là 1_2, 3 và 4 }

Input

Dòng đầu ghi số K là số từ trong dãy ban đầu và số M là số lượng thao tác.

Dòng tiếp theo ghi K số nguyên dương lần lượt là độ dài của các từ tính từ trái qua phải

M dòng tiếp theo mỗi dòng bắt đầu bằng 1 chữ cái (J/D/C). Trong trường hợp chữ cái bắt đầu là J hoặc D tiếp theo ghi số hiệu từ mà thao tác cần thực hiện.

Output

Ứng với mỗi thao tác C trong input, ghi ra 1 số trên 1 dòng trong file output là số lượng từ tại thời điểm tương ứng.

Example

Input:
2 3
2 2
J 2 3
D 2 4
C

Output:
3

Giới hạn:
Số đơn âm không quá 50000.
M ≤ 100000