Copiado al portapapeles
Descripción
Yhorel consiguió un gato en una excursión a Tarija, ese gato tiene algo particular, es un gato brillante, puede hablar, puede pensar, puede programar y hasta sabe inglés (Ese gato es algo malo).
El gato tiene algo en particular, tiene tendencias malvadas, su dueño Yhorel tiene un tablero de ajedrez y su gato llamado Michi(Un nombre muy original) quiere poner una cantidad de torres de ajedrez para simular un macabro juego: En las celdas del tablero de ajedrez vacías se imagina que hay personas(En cada casilla imagina que hay una persona), y el Michi quiere poner muchas torres para ver que personas se salvan de sus ataques con las torres(El Michi quiere ver el mundo arder).
Yhorel tiene un tablero de ajedrez cuadrado de tamaño $n × n$ y el Michi tiene $m$ torres.
Inicialmente el tablero de ajedrez de Yhorel está vacío, en consecuencia de eso el michi colocará las torres en el tablero una torre tras otra.
Una celda del tablero está bajo ataque de una torre, si hay al menos una torre ubicada en la misma fila o en la misma columna con esta celda. Si hay una torre ubicada en la celda, esta celda también está bajo ataque. Se le dan las posiciones del tablero donde el Michi pondrá torres.
Yhorel está preocupado por su Michi, no es normal que el Michi se imagine eso, así que para cada torre tienes que determinar el número de celdas que $no$ $están$ $bajo$ $ataque$ después de que el Michi ponga una torre en el tablero.
Entrada
La primera línea de la entrada contiene dos números enteros $n$ y $m$ $(1 ≤ n ≤ 100000, 1 ≤ m ≤ min(100000, n^{2}))$ el tamaño del tablero de Yhorel y el número de torres que tiene el Michi.
Cada una de las siguientes $m$ líneas contiene números enteros $x_{i}$ y $y_{i}$ $(1 \leq x_{i}, y_{i} \leq n)$ el número de la fila y el número de la columna donde el michi colocará la $i$-ésima torre.
El michi pone torres en el tablero en el orden en que aparecen en la entrada.
Se garantiza que cualquier celda no contendrá más de una torre.
Salida
En las $m$ líneas imprimir $m$ enteros, el $i$-ésimo de ellos debe ser igual al número de celdas que no están bajo ataque después de que se colocan las primeras $i$ torres.
Ejemplo Entrada
3 3 1 1 3 1 2 2
Ejemplo Salida
4 2 0
Ayuda
Respecto al primer caso de entrada en la siguiente imagen se muestra el estado del tablero después de colocar cada una de las tres torres. Las celdas que se pintaron con color gris no están bajo ataque.
EJEMPLO ENTRADA 2
5 2
1 5
5 1
EJEMPLO SALIDA 2
16
9
EJEMPLO ENTRADA 3
100000 1
300 400
EJEMPLO SALIDA 3
9999800001
Usar long