Màu Sắc Theo Thời Gian

Có một dãy gồm $n$ ô, mỗi ô mang một màu nguyên dương. Có $m$ thao tác được thực hiện theo thứ tự. Thao tác $Q$ $l$ $r$ hỏi có bao nhiêu màu khác nhau đang xuất hiện từ vị trí $l$ đến $r$, tính cả hai đầu mút. Thao tác $R$ $p$ $c$ thay màu tại vị trí $p$ thành $c$; thay đổi này có hiệu lực với mọi thao tác phía sau. Mỗi truy vấn phải dùng trạng thái của dãy sau toàn bộ phép thay màu đứng trước nó.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên là các màu ban đầu.
• Mỗi trong $m$ dòng tiếp theo có dạng $Q$ $l$ $r$ hoặc $R$ $p$ $c$.

Output

• Với mỗi thao tác $Q$, in trên một dòng số màu phân biệt trong đoạn được hỏi.

Constraints

• $1\le n,m\le 1.33333\cdot 10^5$.
• Mọi màu ban đầu và màu trong thao tác $R$ thuộc $[1,10^6]$.
• Trong $Q$ $l$ $r$: $1\le l\le r\le n$; trong $R$ $p$ $c$: $1\le p\le n$.
• Input có ít nhất một thao tác $Q$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 7
1 2 1 3 2
Q 1 5
R 3 2
Q 1 3
R 4 1
Q 2 5
R 1 2
Q 1 4

3
2
2
2