题目描述

给定一个长度为 $n$ 的二进制字符串 $S$，你需要回答 $q$ 个查询，每个查询属于以下两种类型之一：

1. 给定两个整数 $l, r$ ($1 \leq l \leq r \leq n$)，翻转每个 $i \in [l, r]$ 的二进制位 $S_i$。

2. 给定三个整数 $l, a, b$ ($1 \leq l \leq n, 1 \leq a, b \leq n-l+1$)，你需要计算有多少个区间 $[u, v]$ ($1 \leq u \leq v \leq l$) 满足 $S_{a+x-1} = S_{b+x-1}$ 对每个 $x \in [u, v]$ 都成立，这些区间称为对称区间。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \leq n, q \leq 10^6$)，表示给定字符串 $S$ 的长度和查询的数量。 第二行包含给定的长度为 $n$ 的二进制字符串 $S$。

接下来的 $q$ 行每行包含一个查询，属于以下两种类型之一：

• $1 \ l \ r$ ($1 \leq l \leq r \leq n$)，表示对于每个二进制位 $S_i$ ($i \in [l, r]$)，翻转每个 $i \in [l, r]$ 的二进制位 $S_i$。

• $2 \ l \ a \ b$ ($1 \leq l \leq n, 1 \leq a, b \leq n-l+1$)，你需要计算有多少个区间 $[u, v]$ ($1 \leq u \leq v \leq l$) 满足 $S_{a+x-1} = S_{b+x-1}$ 对每个 $x \in [u, v]$ 都成立。

保证第 $2$ 类查询的数量不超过 $2500$。

输出格式

对于每个第 $2$ 类查询，输出一行包含一个整数，表示对称区间的数量。

10 3
1001001001
2 4 3 5
1 2 6
2 5 2 6

2
7

解释 #1

对于第一个查询，$S_{3..6} = 0100$，$S_{5..8} = 0010$，$2$ 个对称区间是 $[1, 1]$ 和 $[4, 4]$。

在第二个查询后，$S$ 变为 1110111001。

对于第三个查询，$S_{2..6} = 11011$，$S_{6..10} = 11001$，$7$ 个对称区间是 $[1, 1]$、$[1, 2]$、$[1, 3]$、$[2, 2]$、$[2, 3]$、$[3, 3]$ 和 $[5, 5]$。