创作新歌很难，所以我们请了一位 AI（ChatDoReMi）为我们创作一些新歌。结果……非常糟糕！事实证明，大语言模型完全不适合作曲。谁能想到呢？但也许我们可以利用自己的创造力从中挽救一些东西。

如果一个字符串可以通过连接某些（可能是空的）音符序列产生，则称该字符串为“交响的”（symphonic），其中每个音符都是 “do”、“re”、“mi”、“fa”、“so”、“la”、“ti” 之一（当然，不包含引号）。例如：

• “dodo”、“doremifasolatido”、“redososomiso”、“doremitiladoremisofadoredo” 和 “”（空字符串）都是交响的；
• “dod”、“r”、“soda” 和 “icpcamritapuri” 不是交响的。

给定一个由 ChatDoReMi 提供给我们的“参考字符串” $s$，你必须能够衡量 $s$ 的某些子串距离“交响”还有多远——实际上，你还应该能够处理一些更新，因为我们可能会要求 ChatDoReMi 改进其响应。

形式上，你必须处理 $q$ 次查询，每次查询属于以下两种类型之一：

• “? $i$ $j$” 表示你需要考虑从位置 $i$ 开始到位置 $j$ 结束（包含 $i$ 和 $j$，且为 1-indexed）的子串。为了使该子串变为交响的，最少需要删除多少个字母？注意，每次查询都是一个独立的假设性问题——实际上并没有删除任何字母。
• “# $i$ $j$ $new$” 表示你需要将 $s$ 的第 $i$ 个到第 $j$ 个字符（同样包含 $i$ 和 $j$，且为 1-indexed）替换为字符串 $new$；保证 $|new| = j - i + 1$。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $q$，其中 $n$ 是 $s$ 的长度。 第二行包含字符串 $s$。 接下来 $q$ 行，描述查询。每个查询由单行组成，格式为 “? $i$ $j$” 或 “# $i$ $j$ $new$”，如上所述。

• $1 \le n \le 5 \cdot 10^5$
• $1 \le q \le 3 \cdot 10^5$
• 对于每次查询，$1 \le i \le j \le n$
• 所有 “#” 查询中 $new$ 的总长度 $\le 10^5$
• 每个字符串均由小写英文字母组成。

输出格式

对于每个 “?” 查询，输出一行，包含一个表示答案的整数。

样例

输入 1

8 10
eldorado
? 1 3
? 1 8
# 6 7 it
? 1 8
# 3 3 t
? 1 8
# 1 8 streamer
? 1 8
# 1 8 symphony
? 1 8

输出 1

3
4
6
6
6
6

说明

• 对于第一次查询，考虑的子串是 “eld”。我们必须删除所有三个字母（将其变为空字符串）以使其变为交响的。
• 对于第二次查询，考虑的子串是 “eldorado”。我们必须至少删除 4 个字母才能使其变为交响的：eldorado $\to$ eldordo $\to$ eldodo $\to$ ldodo $\to$ dodo。
• 在第三次查询后，$s$ 变为 “eldorito”。
• 对于第四次查询，考虑的子串是 “eldorito”。我们必须至少删除 6 个字母才能使其变为交响的：eldorito $\to$ eldorto $\to$ eldoro $\to$ eldoo $\to$ edoo $\to$ edo $\to$ do。
• 在第五次查询后，$s$ 变为 “eltorito”。
• 对于第六次查询，考虑的子串是 “eltorito”。我们必须至少删除 6 个字母才能使其变为交响的：eltorito $\to$ eltorio $\to$ eltrio $\to$ eltri $\to$ etri $\to$ tri $\to$ ti。