Fenechka#5274
Sasha is on a creative quest. She wants to weave another bracelet (Fenechka), but has difficulty choosing colors. Currently, all threads that she plans to use are laid out in a row. During her deliberations, Sasha occasionally replaces one colored thread with another, and to check if the pattern is as she intends, she needs to verify whether some sequences of thread colors are equal.
The first line contains two integers and (1 \le n, k \le 100\,000): the number of threads in the bracelet and the number of queries, respectively. The second line contains a string of characters, describing the initial colors of the threads. Each color is represented by a lowercase or uppercase Latin letter or a digit. The following lines describe the queries, which are of two types:
"* " — replace the thread at position with a thread of color ,
"? " — check whether the sequence of colors of threads starting at positions and and of length are equal.
For each query of the second type, output "+" if the sequences are equal, or "-" otherwise.
Beispiel 1