回文串

题号：NC273697
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

	文文得到一个字符串，于是请教你这个字符串有多少个子串是回文串，但这个问题很快就被你解决了。于是文文加强了这个问题，具体如下： 

	有一个长度为  的字符串 ，有  次操作，每次操作都是一下两种形式： 

	1.给定  询问区间是否是特殊回文串。

	2.给定  将区间全部改为 。

	特殊回文串定义：最多一对字符失配的回文串。即对于字符串  来说，记  为字符串  的长度，满足 ，的数量小于等于 。 

	如aaba，abcedba，abccba，aa都是特殊回文串。abde，abbcb则不是。 

第一行输入两个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ )， $q$ ( $1 \le q \le 2 \cdot 10^5$ )。

第二行输入长度为 $n$ 的且仅包含小写字母的字符串 $S$ 。

接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：

操作 $1$ ：格式： $1$ $l$ $r$ 含义：询问区间[ $l,r$ ]代表的字符串是否是特殊回文串。

操作 $2$ ：格式： $2$ $l$ $r$ $c$ 含义：将区间[ $l,r$ ]内的每个字符都改为小写字母 $c$ 。

输出所有 $1$ 操作的答案，如果是特殊回文串就输出YES，否则输出NO。每行一个答案。

示例1

复制

10 5
cabcbabcba
1 7 9
1 7 8
1 1 6
1 5 5
1 1 3

复制

YES
YES
NO
YES
YES

示例2

复制

10 4
caabaabaca
1 1 1
1 1 5
2 4 4 a
1 1 5

复制

YES
NO
YES