题目背景

题目提供者：朝田诗乃

众所周知，女装只有零次和无数次。

题目描述

给定一个长度为 $n$ 的序列 $a$。

有如下定义：若一个序列中所有数字都一样，那么这个序列被称作“诗乃序列”。

对于每次询问，给定 $l$ 和 $r$，求序列 $a$ 中左右端点都在 $[l,r]$ 中的最长“诗乃序列”长度。

这题难倒了 Abbi。Abbi 决定女装。当 Abbi 女装时，序列会出现神奇的变化：它可以在询问的区间 $[l,r]$ 中挑一个它喜欢的位置 $p$，将区间 $[l,p]$ 和 $(p,r]$ 分别翻转。

Abbi 想知道，最多进行 $k$ 次女装后（可选择进行不足 $k$ 次或不进行女装），能得到的最长的“诗乃序列”的长度是多少？

输入格式

第一行，$n$、$m$，表示序列长度和操作个数。

第二行，$n$ 个数，第$i$个数表示序列初始值 $a_i$。

接下来 $m$ 行，每行描述一个操作，格式如下：

1. $R$ $l$ $r$ $x$：表示将区间 $[l,r]$ 上的数字全部变成 $x$。
2. $Q$ $l$ $r$ $k$：表示询问在 $[l,r]$ 中进行最多 $k$ 次女装所能得到的最长“诗乃序列”长度。

注意：询问独立，即每次询问后会将序列复原，不实际执行反转操作。

输出格式

对于每个 Q 操作，输出询问答案。

10 4
3 3 3 3 2 3 3 3 2 2
Q 1 6 1
Q 1 6 0
R 8 8 2
Q 5 10 1

5
4
4

提示

时空限制：1s/512MB。

数据范围：

• 对于 $20\%$ 的数据，$1 ≤ n,m ≤ 100$。
• 对于另外 $10\%$ 数据，所有询问的 $k=0$。
• 对于另外 $10\%$ 数据，没有 R 操作。
• 对于 $100\%$ 的数据，$1≤n,m≤200000$，$0≤k≤1000$，$1≤a_i,x≤10^9$，$1≤l≤r≤n$。

特殊限制：对于后 $80\%$ 的数据，保证能卡飞 ODT。

样例解释：

对于第一次询问，询问的区间为：

3 3 3 3 2 3

女装 $1$ 次，将区间 $[1,4]$ 和 $[5,6]$ 分别翻转，得到：

3 3 3 3 3 2

此时可得到最长“诗乃序列”，长度为 $5$。可以证明没有别的女装方法能得到更长的“诗乃序列”。

此后询问以此类推。

建议使用读入优化。