P4979 矿洞：坍塌

- Made By tomoo CYJian家里为什么那么有钱？因为他家$&@$%#开了矿！！ CYJian家虽然有矿，但是有矿也不能任性。这不，CYJian家的矿塌了...... **change:出题人仁慈地放大了空间限制**

CYJian家的矿塌了之后，就没有经济来源了（不要问我怎么没有存款）。 于是，CYJian迫切地想要修复他家的矿。 CYJian家的矿共出产$A,B,C$三种矿石，所以我们也只能用$A,B,C$三种材料来修复他们家的矿。我们已知共有$N$吨材料，每吨材料均为$A,B,C$三种材料中的一种，它们连成了一个串，如： $$ABCBCABCBACBCBAA$$ CYJian家对材料的要求非常严格，他每次会选择一段连续区间的材料作为修复的材料。因为不合要求的材料会使得矿再次塌陷，砸死CYJian，所以这个连续区间的材料必须满足一下$2$个要求： - 这段连续区间必须是同一种材料 - 这段连续区间的前一个材料与后一个材料必须不相同。 例如，有一段材料为$AACBBABBBCCCBBB$，则$(4$~$5)$ 区间的 $BB$ 和 $(5$~$5)$ 区间的 $B$ 均符合要求，而 $(10$~$12)$ 区间的 $CCC$ 不符合要求。 材料有灵性，所以材料会有变化。 现在有$N$吨材料，$K$个询问。每个询问是以下的$2$种形式之一： - A x y op 表示替换材料，将$x$到$y(1

无

无

- 对于$30$%的数据，$N\le1000,K\le2000$ - 对于$70$%的数据，$N\le5000,K\le5000$ - 对于$100$%的数据，$N\le500000,K\le500000,1