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

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

4 секунди
512 мегабайтів
Дуже складна

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

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

Вхідні дані

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

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

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

  • 1 — подія першого типу.

  • 2 — подія другого типу.

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},

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

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

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

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