Migrated from Lutece 2579 奎恩哥的敬业串

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，主机单机圈内有那么一个主播 Mr.Quin，大伙都叫他奎恩哥。他十足敬业地为黑暗之魂 3 做攻略解说视频一直出到了第 21 期，猛男们决定送他一个字符串作为礼物以褒奖奎恩哥的敬业，所以送出的字符串必须是一个敬业串。当一个字符串串拥有一个子序列串包含单词 quin，我们称这个字符串为敬业串。比如：字符串 quiiiiin 是一个敬业串而 quniiiiii 不是。

但是粗心的猛男们可能会送出一个摸鱼串，这种字符串会直接导致奎恩哥摸鱼不做攻略，这是猛男们不愿意见到的。当一个字符串串拥有一个子序列串包含单词 quit，我们称这个字符串为摸鱼串，当一个字符串又是敬业串又是摸鱼串，奎恩哥也会毫不犹豫地选择摸鱼。猛男们下定决心绝对不会送出摸鱼串，他们可以对一个串进行数次删除操作，每次操作能删除一个字符，从而得到一个不是摸鱼串的字符串，当这个串是敬业串时猛男就会送给奎恩哥做礼物。

可是字符串从哪里来呢，肥仔韦天提供了一个包含 $n$ 个小写字符的字符串 $S$，他会：

1. 永久地修改字符串的第 $p$ 位字符，修改为一个小写字母 $c$；
2. 划出一个区间 $[L,~R]$ 向猛男们提问，若猛男们要以串 $S$ 的子串 $s_L s_{L+1}..s_R$ 为礼物，则至少得删除多少个字符，才能使其变成非摸鱼串的敬业串，如果无论删除多少字符都无法形成能送出的字符串的话请输出 $-1$。

Input

第一行包含两个正整数，$n$ 和 $Q$ （$4 \leq n \leq 200000, 1\leq Q\leq 100000$）。

接下来一行是一个包含 $n$ 个小写字符的字符串 $S$。

接下来 $Q$ 行，每行先读入一个正整数 $o$（$o\in \{1,2\}$）

• 若 $o$ 为 $1$，则读入正整数 $p$ 和一个小写字母 $c$，其中 $1\leq p\leq n$，表示肥仔韦天将永久地修改字符串的第 $p$ 位字符，修改为一个小写字母 $c$ 。
• 若 $o$ 为 $2$，则接下来继续读入两个正整数 $L$ 和 $R$，其中 $1\leq L\leq R\leq n$，表示韦天对猛男们的提问

Output

对韦天的每个 $o$ 为 $2$ 的询问进行回答，每个回答单独占一行。

Samples

8 5
quittntt
2 1 8
2 1 7
2 2 8
1 6 t
2 1 8

4
3
-1
-1

15 5
uiquitttquxitnu
2 3 4
2 1 14
2 4 15
2 1 13
2 10 15

-1
2
1
-1
-1

4 3
quit
2 1 4
1 4 n
2 1 4

-1
0

Resources

2021 UESTC ICPC Training for Dynamic Programming