Intrusive Donkey#12980

Intrusive Donkey

4 seconds
512 megabytes
Very hard

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:

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 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.

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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.