D. Generated String
time limit per test
6 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a template string $$$S = s_1s_2\cdots s_n$$$ of length $$$n$$$. A generated string is a string formed by concatenating several substrings of $$$S$$$. Formally, each generated string $$$T = f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ is described by a positive integer $$$k$$$ and $$$k$$$ pairs of integers $$$(l_i, r_i)$$$, where $$$T = s[l_1:r_1]+s[l_2:r_2]+\cdots+s[l_k: r_k]$$$. Here $$$s[l: r]$$$ denotes the substring $$$s_ls_{l+1}\cdots s_r$$$, and $$$+$$$ denotes string concatenation.

Your task is to maintain a multiset $$$\mathbb{A}$$$ of strings, supporting the following three types of operations:

  • + $$$k\ l_1\ r_1\ l_2\ r_2\ \cdots\ l_k\ r_k$$$: Insert $$$f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ into the multiset $$$\mathbb{A}$$$.

  • - $$$t$$$: Erase the string inserted in the $$$t$$$-th operation from the multiset $$$\mathbb{A}$$$. It is guaranteed that the $$$t$$$-th operation is an inserting operation and the inserted string is not erased at this time.

  • ? $$$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$$$: Answer the number of strings in the multiset $$$\mathbb{A}$$$ that begin with string $$$f(k, \{l_i\}_{i=1}^k, \{r_i\}_{i=1}^k)$$$ and end with $$$f(m, \{u_i\}_{i=1}^m, \{v_i\}_{i=1}^m)$$$.
Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n, q\leq 10^5$$$), indicating the length of $$$S$$$ and the number of operations.

The second line contains a string $$$s_1s_2\cdots s_n$$$ consisting of lower-cased English letters, indicating the template string.

For the following $$$q$$$ lines, the $$$i$$$-th line contains an operation in the format described above. It is guaranteed that $$$1\leq l_i\leq r_i\leq n$$$, $$$1\leq u_i\leq v_i\leq n$$$. It's also guaranteed that the sum of $$$k$$$ in all operations of type +, plus the sum of $$$k$$$ in all operations of type ?, plus the sum of $$$m$$$ in all operations of type ?, will not exceed $$$3 \times 10^5$$$.

Output

For each operation of type ?, output one line containing one integer indicating the answer.

Example
Input
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
Output
2
1