Гаррисон и Андерсон работают в компании под названием "Перестройка Офиса". В конкурирующих компаниях работники хотят изменить реальность, в этой компании они пытаются предсказать будущее.
Имеется большая квадратная доска n×n. Изначально каждая клетка (x,y) этой доски содержит значение x+y (1≤x,y≤n). Офисные работники знают, что в будущем на доске будет производиться только два типа запросов:
"R r" — сумма всех значений в строке r, вывести результат и установить все значения в строке r равными нулю;
"C c" — сумма всех значений в столбце c, вывести результат и установить все значения в столбце c равными нулю.
Они предсказали запросы и ответы на них. Они хотят убедиться, что результаты предсказаны правильно. Помогите им вычислить результаты запросов.
Первая строка содержит два целых числа n и q (1≤n≤106,1≤q≤105) — размер квадрата и количество запросов.
Каждая из следующих q строк содержит описание запроса. Запросов может быть или строка "R r" (1≤r≤n) или "C c" (1≤c≤n).
Выведите q строк. В i-ой строке выведите результат i-го запроса.