题目描述

给定一个长度为 $n$ 的模板字符串 $S = s_1s_2\cdots s_n$。一个生成字符串指的是由模板字符串 $S$ 的若干子串连接而成的字符串。更正式地，每个生成字符串 $T = f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$ 可以被描述为一个正整数 $k$ 以及 $k$ 对整数 $(l_i, r_i)$，其中 $T = s[l_1:r_1]+s[l_2:r_2]+\cdots+s[l_k: r_k]$。这里我们用 $s[l: r]$ 表示子串 $s_ls_{l+1}\cdots s_r$，用 $+$ 表示字符串连接。

您需要维护一个由字符串构成的可重集合 $\mathbb{A}$，支持以下三种操作：

• $\texttt{+ } k\ l_1\ r_1\ l_2\ r_2\ \cdots\ l_k\ r_k$：将 $f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$ 加入可重集合 $\mathbb{A}$。
• $\texttt{- } t$：将第 $t$ 次操作加入的字符串从可重集合 $\mathbb{A}$ 里删除。保证第 $t$ 次操作是一次加入操作，且该字符串目前还没有被删除。
• $\texttt{? } k\ l_1\ r_1\ l_2\ r_2\ \cdots\ l_k\ r_k\ m\ u_1\ v_1\ u_2\ v_2\ \cdots u_m\ v_m$：求可重集合 $\mathbb{A}$ 里有几个字符串以 $f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$ 为开头，且以 $f(m, \{u_i\}_{i=1}^m, \{v_i\}_{i=1}^m)$ 为结尾。

输入格式

每个测试文件仅有一组测试数据。

第一行输入两个整数 $n$ 和 $q$（$1\leq n, q\leq 10^5$），表示 $S$ 的长度和操作的数量。

第二行输入一个由小写英文字母构成的字符串 $s_1s_2\cdots s_n$，表示模板字符串。

对于接下来的 $q$ 行，第 $i$ 行输入一个操作，格式如上所述。保证 $1\leq l_i\leq r_i\leq n$，$1\leq u_i\leq v_i\leq n$。另外保证所有 $\texttt{+}$ 类型的操作的 $k$ 之和，加上所有 $\texttt{?}$ 类型的操作的 $k$ 之和，加上所有 $\texttt{?}$ 类型的操作的 $m$ 之和不超过 $3 \times 10^5$。

输出格式

每次 $\texttt{?}$ 类型的操作输出一行一个整数表示答案。

8 7
abcaabbc
+ 3 1 3 2 4 3 8
+ 2 1 4 1 8
+ 1 2 4
? 1 5 6 1 7 8
- 3
+ 1 2 5
? 1 2 3 1 5 5

2
1