维护队列

你小时候玩过弹珠吗？

小朋友 A 有一些弹珠，A 喜欢把它们排成队列，从左到右编号为 $1$ 到 $N$。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A 有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是 A 还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行 $N$ 个整数，表示初始队列中弹珠的颜色。

接下来 $M$ 行，每行的形式为 Q L R 或 R x c：

• Q L R 表示 A 想知道从队列第 $L$ 个弹珠到第 $R$ 个弹珠中，一共有多少不同颜色的弹珠；
• R x c 表示 A 把 $x$ 位置上的弹珠换成了 $c$ 颜色。

输出格式

对于每个 Q 操作，输出一行表示询问结果。

样例输入

2 3
1 2
Q 1 2
R 1 2
Q 1 2

样例输出

2
1

样例解释

初始队列的颜色为 $1, 2$，第一次询问区间 $[1,2]$ 中有 $2$ 种颜色；随后把位置 $1$ 的弹珠改成颜色 $2$，队列变为 $2, 2$，再次询问区间 $[1,2]$ 只有 $1$ 种颜色。

数据范围

对于 $100\%$ 的数据：

• $1\le N\le 10^4$；
• $1\le M\le 10^4$；
• 修改操作不超过 $1000$ 次；
• 所有颜色均用 $1$ 到 $10^6$ 的整数表示。

来源与许可

本题为「维护队列」，题面与测试数据整理自 BZOJ 2453。

样例 1

输入

2 3
1 2
Q 1 2
R 1 2
Q 1 2

输出

2
1