题目背景

“命运就像滚石...只有拥有「黄金精神」之人，才能让它停下。” —— 布鲁诺·布加拉提

滚石可以预言所有人的结局，或是幸福，或是悲伤，也有可能是未知。

题目描述

现在有 $n$ 个滚石，每个滚石都有相对应的预言：

• H 幸福结局
• S 悲伤结局
• U 未知结局

定义一串滚石 $[l,r]$ 预言是幸福的，需满足以下 $2$ 种条件其中任意一个：

• 区间 $[l,r]$ 内全是H。
• 区间 $[l,r]$ 内全是U。

我们可以把像这样的一串滚石称为幸福子串。

很庆幸，现在做的每件事都会影响滚石的预言，所以有以下 $3$ 个操作：

1. 第 $k$ 个滚石的预言结局变为 $S_1$(只能是H,S,U)。
2. 区间 $[l,r]$ 内预言状态为U的滚石变为 $S_2$(只可能是H,S)。
3. 访问区间 $[l,r]$ 内最长幸福子串的长度。

输入格式

输入共 $m+2$ 行。

第 $1$ 行 $2$ 个整数 $n$,$m$，其中 $m$ 表示操作次数。

第 $2$ 行为一个长度为 $n$ 的字符串 $S$，表示滚石串。

第 $3$ 到 $m+2$ 行，每行第一个数 $opt$ 表示操作类型。

• 当 $opt=1$ 时对应操作 $1$，输入 $K,S_1$；
• 当 $opt=2$ 时对应操作 $2$，输入 $l,r,S_2$；
• 当 $opt=3$ 时对应操作 $3$，输入 $l,r$ 并输出对应答案。

输出格式

输出每个操作 $3$ 对应答案，每个答案单独一行。

输入输出样例 #1

输入 #1

10 5
HHUUHSSUHH
3 1 10
1 3 H
3 1 10
2 3 8 H
3 1 10

输出 #1

2
3
5

说明

数据范围

• 对于 $16\%$ 的数据，$1 \leq n,m \leq 100$。
• 对于 $40\%$ 的数据，$1 \leq n,m \leq 10^3$。
• 对于 $80\%$ 的数据，$1 \leq n,m \leq 10^5$。
• 对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6$，$1 \le l \le r \le n$，$S_i \in \{H,S,U\}$，$S_{1_i} \in \{H,S,U\}$，$S_{2_i} \in \{H,S\}$。