Гаррисон и Андерсон работают в компании под названием "Перестройка Офиса". В конкурирующих компаниях работники хотят изменить реальность, в этой компании они пытаются предсказать будущее. Имеется большая квадратная доска $n \times n$. Изначально каждая клетка $(x, y)$ этой доски содержит значение $x + y~(1 \le x, y \le n)$. Офисные работники знают, что в будущем на доске будет производиться только два типа запросов: \begin{itemize} \item "$R~r$" --- сумма всех значений в строке $r$, вывести результат и установить все значения в строке $r$ равными нулю; \item "$C~c$" --- сумма всех значений в столбце $c$, вывести результат и установить все значения в столбце $c$ равными нулю. \end{itemize} Они предсказали запросы и ответы на них. Они хотят убедиться, что результаты предсказаны правильно. Помогите им вычислить результаты запросов. \InputFile Первая строка содержит два целых числа $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)$. \OutputFile Выведите $q$ строк. В $i$-ой строке выведите результат $i$-го запроса.