Benny and String
Tag(s):

## Data Structures, Medium-Hard, Medium-Hard, Segment Trees

Problem
Editorial
Analytics

Benny loves strings! She also loves to play with string and make different queries on them.

In this problem Benny has a string $s$ of length $n$ consisting of lowercase Latin letters.

Let's define next letter for every lowercase Latin letter. For letters from 'a' to 'y' next letter is next one in Latin alphabet, and for 'z' the next one is 'a'.

Let's call the rotation of letter is when we replace it with the next one.

You have to answer the following queries about the string $s$:

• ? l r c — where $c$ is lowercase Latin letter, ($1 \leq l \leq r \leq n$). You have to output the length of the largest sequence consisting of consecutive letters $c$ in $s[l,r]$, where $s[l, r]$ — is the substring of string $s$ starting with $s_l$ and ending with $s_r$.
• + l r x — you have to rotate every letter in $s[l,r]$ exactly $x$ times, ($1 \leq l \leq r \leq n$), ($0 \leq x \leq 10^9$).
• * i c — set $s_i$ equal to $c$, where $c$ is some Latin lowercase letter, ($1 \leq i \leq n$).
• - i x — set $s_i$ equal to its value before processing the $x$-th query, ($1 \leq i \leq n$), ($1 \leq x \leq j$), where $j$ is the index of current query. All queries are indexed starting with 1.

Input format

The first line contains two integers $n$ and $q$ denoting the length of the string and the number of queries.

The next line contains string $s$.

The following $q$ lines contains queries.

Constraints

$1 \leq n, q \leq 10^5$
String $s$ consists of lowercase Latin letters.
There is at least one query of the first type.

Output format

For each query of the first type output an answer as a single integer.

SAMPLE INPUT
3 7
abc
? 1 3 c
* 2 c
? 1 3 c
+ 1 1 2
? 1 3 c
- 1 1
? 1 3 a

SAMPLE OUTPUT
1
2
3
1

Explanation

Let's take a look at how string $s$ will look like after each query:

abcaccaccccccccaccacc

Time Limit: 2.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Greedy Algorithms
• Algorithms > Graphs
• Algorithms > Advanced Algorithms