#P18181. Generated String

Generated String

Generated String

给定一个长度为 nn 的模板字符串 S=s1s2⋯snS=s_1s_2\cdots s_n。选择若干个非空子串,并按给出的顺序连接,可以得到一个生成字符串。

具体地,一个生成字符串由正整数 kk 和 kk 对下标 (li,ri)(l_i,r_i) 描述:

$$f\bigl(k,(l_1,r_1),\ldots,(l_k,r_k)\bigr) =S[l_1:r_1]+\cdots+S[l_k:r_k].$$

这里 S[l:r]=slsl+1⋯srS[l:r]=s_ls_{l+1}\cdots s_r,加号表示字符串连接。各片段可以重叠、重复,片段之间不要求按模板下标递增排列。

维护一个初始为空的字符串多重集 AA,依次执行以下 qq 个操作:

  • + k l1 r1 ... lk rk:将这些片段描述的生成字符串插入 AA。
  • - t:删除第 tt 个操作插入的那个字符串实例。保证第 tt 个操作是插入,且该实例目前尚未被删除。
  • ? k l1 r1 ... lk rk m u1 v1 ... um vm:令前 kk 个片段生成字符串 PP,后 mm 个片段生成字符串 QQ。询问 AA 中有多少个字符串同时以 PP 开头、以 QQ 结尾。

多重集中的相同字符串按实例分别计数;删除一个实例不会删除其他相同内容的实例。查询的前缀和后缀可以重叠,例如某个字符串可以同时是自己的前缀和后缀。

输入格式

第一行两个整数 n,qn,q,满足 1≤n,q≤1051\le n,q\le10^5。

第二行是长度为 nn 的字符串 SS,只包含小写英文字母。

接下来 qq 行,第 ii 行给出第 ii 个操作,格式如上。所有片段均满足 1≤l≤r≤n1\le l\le r\le n,各生成字符串的片段数都是正整数。删除操作的 tt 指输入中的操作编号,而不是第几次插入。

保证以下三项之和不超过 3×1053\times10^5:所有插入操作的片段数、所有查询前缀的片段数、所有查询后缀的片段数。

每个输入文件只有一组数据。

输出格式

对每个 ? 操作输出一行一个整数,表示满足条件的字符串实例数量。

样例

输入:

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