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

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

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

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

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

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

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

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

对于30%的数据，n,m \leq 10000

对于60%的数据，n,m \leq 50000

对于所有数据，n,m \leq 120000

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