Egon chăm sóc một khu vườn có \(N\) cây táo. Công việc của anh gồm hai loại: bón phân cho cây và thống kê chiều cao của chúng.

Để bón phân, Egon có một số chai MegaBoostFertilizer. Khi được bón loại phân này, một cây lập tức cao thêm một xentimét. Mỗi chai có dung lượng \(c_i\), là số cây có thể được bón bằng chai đó, và chỉ dùng được cho những cây cao ít nhất \(h_i\) xentimét. Vì muốn tất cả cây đều cao nhất có thể, Egon luôn bón cho \(c_i\) cây thấp nhất trong số những cây cao ít nhất \(h_i\) xentimét.

Khi thống kê, Egon cần biết số cây có chiều cao nằm trong một khoảng cho trước. Anh rất bận chăm sóc khu vườn, nên nhờ bạn viết chương trình nhận danh sách công việc và tính các kết quả thống kê giúp anh.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số cây trong vườn và số công việc. Dòng thứ hai chứa \(N\) số nguyên thuộc đoạn \([1,N]\), mô tả chiều cao ban đầu của các cây, tính bằng xentimét.

\(M\) dòng tiếp theo mô tả các công việc theo thứ tự thời gian. Mỗi dòng bắt đầu bằng ký tự \(t_i\), là F hoặc C:

• Nếu \(t_i\) là F, tiếp theo là hai số nguyên \(c_i\) và \(h_i\). Egon bón phân cho \(c_i\) cây thấp nhất trong số những cây cao ít nhất \(h_i\) xentimét. Nếu có ít hơn \(c_i\) cây đủ cao, anh bón cho tất cả những cây đó rồi bỏ chai đi, dù vẫn còn phân trong chai.
• Nếu \(t_i\) là C, tiếp theo là hai số nguyên \(\mathit{min}_i\) và \(\mathit{max}_i\). Egon cần đếm số cây có chiều cao \(H\) thỏa mãn \(\mathit{min}_i \le H \le \mathit{max}_i\).

Dữ liệu ra

Với mỗi công việc loại C, in một dòng chứa số cây táo có chiều cao thuộc khoảng yêu cầu. Thứ tự các kết quả phải trùng với thứ tự những công việc loại C trong dữ liệu vào.

Ràng buộc

• \(1 \le N,M \le 100\,000\).
• \(1 \le c_i \le N\) và \(0 \le h_i \le 1\,000\,000\,000\).
• \(1 \le \mathit{min}_i \le \mathit{max}_i \le 1\,000\,000\,000\).

Phân nhóm

• Trong các bộ dữ liệu có tổng cộng 40 điểm, \(1 \le N \le 7\,000\) và số công việc loại F không vượt quá \(7\,000\).
• 60 điểm còn lại không có ràng buộc bổ sung.

Ví dụ

5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

3
0
5