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^4,\ 1 \le q \le 10^3)\).
• 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.

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

Giải thích: Sau R 6 3 và R 5 4 dãy là 1 4 1 1 4 3 2 4 2 3. Đoạn \([3, 8]\) = 1 1 4 3 2 4 có một số \(3\); đoạn \([7, 10]\) = 2 4 2 3 có một số \(4\).

Gợi ý

Dùng cây phân đoạn, mỗi nút lưu bảng đếm (giá trị → số lần xuất hiện) trên đoạn mà nút quản lý. Thao tác R cập nhật bảng đếm của \(O(\log n)\) nút trên đường từ lá lên gốc; thao tác Q cộng kết quả của \(O(\log n)\) nút phủ đoạn \([L, R]\).