In the land of Far Far Away, Donkey just can’t stop talking. Sometimes, he feels that he should definitely repeat one of his previous thoughts. He repeats his phrase in a specific way, where each letter is doubled (for example, aabcb turns into aaaabbccbb). Given a string of length representing Donkey’s initial phrase, there are two types of events:
Donkey changes his phrase, repeating some part of it. More specifically, he chooses some substring from positions to and doubles it. (For example, if the string is aabc and Donkey repeats the part from 2 to 3, the resulting phrase becomes aaabbc).
Shrek cannot hold in his mind everything that intrusive Donkey said. He is interested what is the -th letter in Donkey’s current phrase.
Note that event of first type changes Donkey’s phrase. Shrek needs help managing Donkey’s endless questions so he can keep his peace of mind!
First line contains two integers and — the length of string and the number of events.
Second line contains string of lowercase English letters — the initial Donkey’s phrase.
Next lines contain events as described in the problem statement.
1 — the first type of event.
2 — the second type of event.
1 \le n, q \le 2 \cdot 10^5,
1 \le l \le r \le 10^{18},
1 \le i \le 10^{18},
the length of the phrase will not be greater than 10^{18},
All indices will be up to at the moment of the query.
For each event of the second type, print the answer in a separate line.
Example
Example 1
In the first sample, the phrase of the Donkey changes from abac to abbaac.
In the second sample, the phrase of the Donkey changes from shrek to sshhrek, and then to sssshhhhrreekk.