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

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

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

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

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

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

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

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

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

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

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

Примеры