eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Перестройка Офиса

Перестройка Офиса

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Гаррисон и Андерсон работают в компании под названием "Перестройка Офиса". В конкурирующих компаниях работники хотят изменить реальность, в этой компании они пытаются предсказать будущее.

Имеется большая квадратная доска n \times n. Изначально каждая клетка (x, y) этой доски содержит значение x + y~(1 \le x, y \le n). Офисные работники знают, что в будущем на доске будет производиться только два типа запросов:

  • "R~r" — сумма всех значений в строке r, вывести результат и установить все значения в строке r равными нулю;

  • "C~c" — сумма всех значений в столбце c, вывести результат и установить все значения в столбце c равными нулю.

Они предсказали запросы и ответы на них. Они хотят убедиться, что результаты предсказаны правильно. Помогите им вычислить результаты запросов.

Входные данные

Первая строка содержит два целых числа n и q~(1 \le n \le 10^6, 1 \le q \le 10^5) — размер квадрата и количество запросов.

Каждая из следующих q строк содержит описание запроса. Запросов может быть или строка "R~ r"~(1 \le r \le n) или "C~c"~(1 \le c \le n).

Выходные данные

Выведите q строк. В i-ой строке выведите результат i-го запроса.

Пример

Входные данные #1
3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3
Выходные данные #1
12
10
0
5
5
4
0
Источник 2015 ACM NEERC, Semifinals, December 6, Problem A