Matcom Online Grader

Fito y Martina están trabajando en una compañia llamada “Adjustment Office” y tienen ahora un problema interesante que resolver. Les han otorgado un tablero cuadrado gigante de n x n, donde inicialmente cada celda(x,y) del tablero contiene escrito el valor x + y $(1 ≤ x, y ≤ n)$.

Ellos saben que en el futuro habrán dos tipos de operaciones sobre el tablero:

• “R r” — Sumar todos los valores de la fila r , imprimir el resultado y escribir cero en todas las celdas de la fila r ;

• “C c” — Sumar todos los valores de la columna c , imprimir el resultado y escribir cero en todas las celdas de la columna c ;

Ellos han previsto cuáles serán las preguntas y necesitan saber si han predicho los resultados correctamente. Ayúdalos computando los resultados de las preguntas.

Input

La primera linea de la entrada contiene dos enteros n y q $(1 ≤ n ≤ 10^6, 1 ≤ q ≤ 10^5)$ — el tamaño del tablero y la cantidad de preguntas.

Cada una de las q líneas contiene la descripción de una pregunta. Cada pregunta es “R r” $(1 ≤ r ≤ n)$ o  “C c” $(1 ≤ c ≤ n)$.

Output

La salida debe contener q líneas. La iésima debe contener — el resultado de la iésima pregunta.

Sample test(s)