У Далекому-Далекому королівстві Віслюк просто не може перестати говорити. Іноді він відчуває, що обов’язково має повторити одну зі своїх попередніх думок. Він повторює свою фразу специфічним чином: кожна літера подвоюється (наприклад, aabcb перетворюється на aaaabbccbb). Дано рядок довжини , що представляє початкову фразу Віслюка. Є два типи подій:
Віслюк змінює свою фразу, повторюючи якусь її частину. Точніше, він обирає підрядок з позицій до і подвоює його. (Наприклад, якщо рядок aabc, і Віслюк повторює частину з 2 до 3, результатом буде aaabbc).
Шрек не може запам’ятати все, що настирливий Віслюк говорить. Його цікавить, яка літера стоїть на -ій позиції в поточній фразі Віслюка.
Зауважте, що події першого типу змінюють фразу Віслюка. Шреку потрібна допомога, щоб упоратися з нескінченними питаннями Віслюка й не збожеволіти!
У першому рядку задано два цілі числа та — довжина рядка та кількість подій.
У другому рядку задано рядок що складається з маленьких латинських літер — початкова фраза Віслюка.
У наступних задані події, описані в умові.
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},
Всі індекси будуть в межах до на момент кожного запиту.
Для кожної події другого типу виведіть відповідь в окремому рядку.
Приклад
Приклад 1
У першому прикладі, фраза Віслюка змінюється з abac на abbaac.
У другому прикладі, фраза Віслюка спочатку змінюється з shrek на sshhrek, а потім на sssshhhhrreekk.