Đây là phiên bản dữ liệu lớn của bài Truy vấn tần suất đoạn con liên tiếp. Cách duyệt trâu sẽ không còn đủ nhanh, bạn cần dùng cấu trúc dữ liệu phù hợp (gợi ý: cây phân đoạn).

Cho dãy gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\) được đánh chỉ số từ \(1\) đến \(n\) và \(q\) thao tác tiến hành trên dãy. Mỗi thao tác thuộc một trong hai dạng:

• R i x: thay đổi giá trị phần tử thứ \(i\), tức là gán \(a_i = x\).
• Q L R x: đếm xem trên đoạn từ chỉ số \(L\) đến chỉ số \(R\) (kể cả hai mút) có bao nhiêu phần tử có giá trị bằng \(x\).

Hãy thực hiện các thao tác theo đúng thứ tự và trả lời các truy vấn Q.

Đầu vào

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) \((1 \le n \le 10^5,\ 1 \le q \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng ở trên, với \(1 \le i \le n\), \(1 \le L \le R \le n\), \(1 \le x \le 10^9\).

Đầu ra

Với mỗi thao tác Q, in ra kết quả tương ứng trên một dòng.

Chấm điểm

• \(60\%\) số test có \(n \le 10^4,\ q \le 10^3\).
• \(40\%\) số test còn lại có \(n, q \le 10^5\).

Ví dụ

Đầu vào:

10 8
1 4 1 1 3 4 2 4 2 3
Q 5 7 5
R 6 3
R 5 4
Q 3 8 3
Q 7 10 4
R 8 3
Q 6 10 1
Q 4 10 1

Đầu ra:

0
1
1
0
1