Надокучливий Віслюк

Обмеження: 4 сек., 512 МіБ

У Далекому-Далекому королівстві Віслюк просто не може перестати говорити. Іноді він відчуває, що обов’язково має повторити одну зі своїх попередніх думок. Він повторює свою фразу специфічним чином: кожна літера подвоюється (наприклад, aabcb перетворюється на aaaabbccbb). Дано рядок \(s\) довжини \(n\), що представляє початкову фразу Віслюка. Є два типи подій:

• Віслюк змінює свою фразу, повторюючи якусь її частину. Точніше, він обирає підрядок з позицій \(l\) до \(r\) і подвоює його. (Наприклад, якщо рядок aabc, і Віслюк повторює частину з 2 до 3, результатом буде aaabbc).

• Шрек не може запам’ятати все, що настирливий Віслюк говорить. Його цікавить, яка літера стоїть на \(i\)-ій позиції в поточній фразі Віслюка.

Зауважте, що події першого типу змінюють фразу Віслюка. Шреку потрібна допомога, щоб упоратися з нескінченними питаннями Віслюка й не збожеволіти!

Вхідні дані

У першому рядку задано два цілі числа \(n\) та \(q\) — довжина рядка \(s\) та кількість подій.

У другому рядку задано рядок \(s\) що складається з маленьких латинських літер — початкова фраза Віслюка.

У наступних \(q\) задані події, описані в умові.

• 1 \(l\) \(r\) — подія першого типу.

• 2 \(i\) — подія другого типу.

Вихідні дані

Для кожної події другого типу виведіть відповідь в окремому рядку.

Обмеження

\(1 \le n, q \le 2 \cdot 10^5\),

\(1 \le l \le r \le 10^{18}\),

\(1 \le i \le 10^{18}\),

Довжина фрази Віслюка ніколи не буде більшою за \(10^{18}\),

Всі індекси будуть в межах до \(|s|\) на момент кожного запиту.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6	b a b a a c

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 shrek 1 1 2 2 7 1 1 7 2 7	k h

Примітки

У першому прикладі, фраза Віслюка змінюється з abac на abbaac.

У другому прикладі, фраза Віслюка спочатку змінюється з shrek на sshhrek, а потім на sssshhhhrreekk.