Покарає чи заб’є?

Limits: 2 sec., 256 MiB

За минулий тиждень Тойлет-мен наловив дуже багато злочинців, тож тепер його завдання — покарати всіх цих негідників.

Усього злочинців є \(n\), і вони розміщені зліва направо та пронумеровані числами від 1 до \(n\) включно. У початковий момент часу в \(i\)-го злочинця рівень здоров’я є рівним \(h_i\). Коли Тойлет-мен карає якогось злочинця, рівень його здоров’я зменшується на одиницю. При цьому, якщо рівень перед покаранням є рівним 0, то він не змінюється, тобто здоров’я ніколи не стає від’ємним.

Тойлет-мен хоче обробити \(m\) запитів. Запити бувають трьох типів:

• L \(c\) — покарати перших \(c\) злочинців \((1 \le c \le n)\).

• R \(c\) — покарати останніх \(c\) злочинців \((1 \le c \le n)\).

• Q \(x\) — визначити, який поточний рівень здоров’я в \(x\)-го злочинця \((1 \le x \le n)\).

Допоможіть Тойлет-менові опрацювати всі його запити.

Input

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

У другому рядку задано через пробіли \(n\) цілих чисел \(h_1, \ldots, h_n\) — початкові рівні здоров’я злочинців.

У наступних \(m\) рядках задано запити у форматі, наведеному вище. Запити потрібно виконувати в тому порядку, у якому вони задані.

Output

Для кожного запиту третього типу виведіть одне ціле число — відповідь до цього запиту.

Constraints

\(1 \le n, m \le 2\cdot10^5\),

\(1 \le h_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 7 4 1 3 4 Q 2 L 2 R 3 Q 1 Q 2 Q 3 Q 4	1 3 0 2 3

Notes

Після другого запиту рівні здоров’я злочинців будуть [3, 0, 3, 4]. Після третього — [3, 0, 2, 3].