Кролики и грядки

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

У Айбара есть сад, который состоит из K подряд идущих грядок. В саду живут n кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано запросов, которые надо обработать. Они бывают следующих типов:

Кролик номер x(1<=l<=r<=n)

перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
Посчитать количество кроликов на отрезке от грядки l
до грядки r(1<=l<=r<=K)

включительно.

Формат входного файла
В первой строке входных данных даны два числа - n и K. \\ Далее во второй строке указаны чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число q и q строк описывающих запросы. Запросы задаются в следующем формате:

L x- сдвинуть кролика номер
на одну грядку налево
R x- сдвинуть кролика номер
на одну грядку направо
G l r- Посчитать и вывести количество кроликов на отрезке от грядки до грядки

включительно.

Формат выходного файла
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000Подзадача2 1 <= n, K, q <= 5 * 10^5отсутствуютзапросысдвигакроликаПодза дача3 1 <= n, K, q <= 5 * 10^5$
Пример:
Вход

3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7

Ответ

1
3

0