Language#2739

Language

1 second

256 megabytes

Very hard

Upon arriving in Antarctica, Skipper, Rico, Private, and Kowalski discovered that they could not understand what the local penguins were saying. Skipper tasked Private, being the smartest, with figuring out the locals' language to receive operational information from them.

Private recorded all the phrases he heard from the locals as a single long sequence of sounds, using lowercase Latin letters. Thus, he obtained a string $s$ consisting of $n$ lowercase Latin letters. Then Private began to analyze this string: he changed characters, rearranged substrings from one place to another, compared substrings with each other... At some point, Private got completely confused and asked for your help. Private carefully recorded all the operations performed on the string on a sheet of paper, resulting in a list of $m$ entries of the following types:

$S i c$ — Private replaced the letter at the $i$ -th position of the string with the letter $c$ .
$M i j k$ — Private cut out the substring from position $i$ to $j$ of the original string and inserted it after the character at position $k$ . Here, the number $k$ specifies the position of a character in the string after the substring $s [i .. j]$ has been removed. If $k = 0$ k = 0, it means the cut-out substring should be placed at the beginning of the resulting string.
$C i j l$ — Private compared the substrings $s [i .. i + l - 1]$ s[i..i+l-1] and $s [j .. j + l - 1]$ s[j..j+l-1].
$P$ — Private copied the current version of the string to the result sheet.

Unfortunately, Private lost the result sheet, and without it, understanding the locals' language will be impossible. Help him restore the results of the operations performed.

Input

The first line of input contains two numbers $n$ and $m$ — the length of the string recorded by Private and the number of operations performed on it, respectively ( $1 \leq n, m \leq 1 0^{5}$ 1 \le n,\ m \le 10^5). The second line contains $n$ lowercase Latin letters — the original string recorded by Private. The next $m$ lines contain descriptions of Private's actions in the format given above. All indices are guaranteed to be within the permissible range, and when specifying a substring, $i \leq j$ i \le j.

Characters in the string are numbered from $1$ to $n$ , and the character at the $i$ -th position is denoted as $s [i]$ . Recall that the substring $s [i .. j]$ of the string $s$ is the string composed of the characters $s [i]$ , $s [i + 1]$ s[i+1], ..., $s [j]$ .

Output

Output one line for each comparison or copying operation. For each comparison operation carried out by Private, output $"+"$ if the compared substrings were equal, and $"-"$ otherwise. For each copying operation, output the current state of the string at that moment. It is guaranteed that the total size of the output data (excluding line breaks) will not exceed one megabyte.

Examples

Example 1