Вам задано натуральні числа \(N\) і \(Q\), а також рядок \(S\) довжини \(N\), що складається з малих англійських літер. Обробіть \(Q\) запитів. Кожен запит відноситься до одного з наступних двох типів.

• 1 x: Виконайте наступне \(x\) разів поспіль: видаліть останній символ \(S\) і додайте його до початку.

• 2 x: Вивести \(x\)-й символ \(S\).

Обмеження

• \(2 \le N \le 5 \times 10^5\)
• \(1 \le Q \le 5 \times 10^5\)
• \(1 \le x \le N\)
• \(|S|=N\)
• \(S\) складається з малих англійських літер.
• Принаймні один запит у форматі 2 x.
• \(N\), \(Q\), \(x\) — усі цілі числа.

Формат вхідних даних

Перший рядок містить цілі числа \(N,Q\)

Другий  рядок містить \(S\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть для кожного запиту у форматі 2 x відповідь в окремому рядку.

Приклад вхідних даних

3 3
abc
2 2
1 1
2 2

Приклад вихідних даних

b
a

Приклад вхідних даних

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Приклад вихідних даних

c
u
c
u