Fun with Strings
Limits: 3 sec., 256 MiB
Marichka has given Zenyk a pretty hard task, and he has no idea how to solve it. (Well, he didn’t go the Uzhgorod Summer Camp, so that’s probably the reason.)
Initially, there is a string \(s\) of length \(n\) characters. Zenyk has to process \(m\) queries on that string. There are three types of queries:
i
\(p\) \(c\) — insert character \(c\) right after the \(p\)-th character. If \(p\) is 0, insert \(c\) at the beginning of the string.d
\(p\) — remove the \(p\)-th character from the string.q
\(a\) \(b\) — find and print the length of the largest common prefix of strings \(s[a..|s|]\) and \(s[b..|s|]\).
Zenyk has got no time to solve this problem, so your task is to help him do that.
Input
The first line contains two integers \(n\) and \(m\). The second line contains a string of length \(n\). The next \(m\) lines contain queries, one query per line, in the format described above.
It’s guaranteed that the string always consists only of lowercase English letters and all indices in the input are valid.
Output
For each query of the third type print the answer to the query.
Constraints
\(1 \le n, m \le 5 \times 10^4\).
Samples
Input (stdin) | Output (stdout) |
---|---|
7 6 abacaba q 2 6 i 1 c i 5 b q 1 4 d 2 q 4 7 | 2 4 0 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|