Перестройка Офиса
Перестройка Офиса
Гаррисон и Андерсон работают в компании под названием "Перестройка Офиса". В конкурирующих компаниях работники хотят изменить реальность, в этой компании они пытаются предсказать будущее.
Имеется большая квадратная доска 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-го запроса.
Пример
3 7 R 2 C 3 R 2 R 1 C 2 C 1 R 3
12 10 0 5 5 4 0