Quadradets P76718

0.56 La Ivet s’està avorrint molt. En lloc de posar-se a estudiar, ha decidit dibuixar creus a l’atzar en un full quadriculat de mides $n \times n$. Ara té curiositat per saber quants quadradets $2 \times 2$ ha dibuixat. Un quadradet no pot ser adjacent (horitzontalment, verticalment, o diagonalment) a cap altra creu. A l’exemple de la dreta, l’únic quadradet està pintat de verd.

Com que encara li sobra una mica de temps, la Ivet també vol comptar quants quasi-quadradets ha dibuixat. Un quasi-quadradet és un quadradet al qual li falta exactament una creu. A l’exemple de la dreta, els quatre quasi-quadradets estan pintats de vermell.

0.47

Donades totes les creus, podeu comptar el nombre de quadradets i de quasi-quadradets?

Entrada

L’entrada conté diversos casos. Cada cas comença amb la mida $n$ del tauler, seguida del nombre de creus $c$. Segueixen $c$ parells $x$ $y$ indicant la posició de cada creu. Podeu suposar $2 \le n \le 10^9$, $3 \le c \le \min(n^2, 10^5)$, que totes les $x$ i les $y$ es troben entre 1 i $n$, i que no hi ha dues o més creus a la mateixa posició. (El primer de tots els exemples d’entrada es correspon a la figura anterior.)

Sortida

Per a cada cas, escriviu el nombre de quadradets i de quasi-quadradets.

Puntuació

• Cas A:   Casos amb $n \le 30$, com l’exemple d’entrada 1.

• Cas B:   Casos de tot tipus.