ACM 2016 - Round #1Ended |
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.
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)$.
La salida debe contener q líneas. La iésima debe contener — el resultado de la iésima pregunta.