Перебудова Офісу

Гаррісон і Андерсон працюють у компанії під назвою "Перебудова Офісу". У той час як в інших компаніях працівники прагнуть змінити реальність, у цій компанії вони намагаються передбачити майбутнє.

Є велика квадратна дошка розміром $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$-го запиту.

Приклади