Дерево Фенвика


Sasha is in the process of creative search. She wants to weave another Fenechka, but has difficulty in choosing colors. Now all n thread that she plans to use for weaving, are lined in a row. In the process of meditation Sasha from time to time replace one color thread with the other, as well as to verify what pattern is obtained, that means to check that some thread color sequences are equal.

Write a program that automates the testing.


First line contains two integers n and k (1n, k100000) - the number of threads in Fenechka and number of queries. Second line contains the line with n symbols - the colors of the treads initially. Each color is represented with a lowercase or uppercase letter of the Roman alphabet or a digit. The following k lines gives two types of queries:

  • "*** i c**" - replace the thread number i with the thread of color c,
  • "**? i j len**" - check whether the color sequence of the thread starting at positions i and j with the length len are equal.


For each query of the second type print "+" if the sequences are equal, or "-" otherwise.

Time limit 1 second
Memory limit 122.49 MiB
Input example #1
7 4
? 1 5 3
* 6 c
? 2 6 2
? 3 5 3
Output example #1
Source 15 Международная олимпиада для школьников ЛКШ для параллелей B,A',A