描述

墨墨购买了一套 \(N\) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1. \(Q\ L\ R\) 代表询问你从第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。

2. \(R\ P\ Col\) 把第 \(P\) 支画笔替换为颜色 \(Col\)。

为了满足墨墨的要求，你知道你需要干什么了吗？

格式

输入格式

第 \(1\) 行两个整数 \(N\)，\(M\)，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 \(2\) 行 \(N\) 个整数，分别代表初始画笔排中第 \(i\) 支画笔的颜色。

第 \(3\) 行到第 \(2+M\) 行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式

对于每一个 \(Query\) 的询问，你需要在对应的行中给出一个数字，代表第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。

样例1

样例输入1

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

样例输出

4
4
3
4

限制

对于所有数据，\(n,m \leq 133333\)

所有的输入数据中出现的所有整数均大于等于 \(1\) 且不超过 \(10^6\)。

本题可能轻微卡常数