Intrusive Donkey

Limits: 4 sec., 512 MiB

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 \(s\) of length \(n\) 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 \(l\) to \(r\) 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 \(i\)-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!

Input

First line contains two integers \(n\) and \(q\) — the length of string \(s\) and the number of events.

Second line contains string \(s\) of lowercase English letters — the initial Donkey’s phrase.

Next \(q\) lines contain events as described in the problem statement.

• 1 \(l\) \(r\) — the first type of event.

• 2 \(i\) — the second type of event.

Output

For each event of the second type, print the answer in a separate line.

Constraints

\(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 \(|s|\) at the moment of the query.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6	b a b a a c

Input (stdin) сopy	Output (stdout) сopy
5 4 shrek 1 1 2 2 7 1 1 7 2 7	k h

Notes

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.