Les triangles sont étonnamment formidables. Un enfant de 3 ans peut dessiner un cercle, et un enfant de 4 ans peut dessiner un carré. Cependant, on sait qu'il faut un an de plus pour pouvoir dessiner un triangle (Ahn Hyo-seop, Shin Hee-young, Hong Chang-ui Pediatrics, Mirae N (2020), 12e édition).

Iha, ayant dépassé l'âge de 5 ans depuis bien longtemps, a dessiné sans difficulté sur du papier, à l'aide d'un stylo, un « grand triangle équilatéral » de côté $m$.

Avant d'explorer la curiosité d'Iha, nous avons besoin d'une définition d'une grille triangulaire. Contrairement au système de coordonnées cartésiennes où l'axe des $x$ est perpendiculaire à l'axe des $y$, dans une grille triangulaire, l'angle entre l'axe des $x$ et l'axe des $y$ est de 60 degrés. Si l'on trace une droite de la forme $x+y = m$ sur cette grille, on obtient un triangle équilatéral ayant pour sommets $(0,0)$, $(m,0)$ et $(0,m)$, comme le montre la figure suivante. Appelons ce triangle le « grand triangle équilatéral ».

Figure F.1 : Les deux axes de la grille triangulaire et la droite de la forme $x+y = m$

Iha souhaitait dessiner encore plus de triangles équilatéraux. Elle a donc tracé $q$ droites parallèles à l'un des trois côtés et passant par l'intérieur du grand triangle équilatéral, puis elle a effacé les parties qui n'étaient pas contenues dans le grand triangle équilatéral. C'est alors que des triangles équilatéraux ont fleuri comme des fleurs !

Iha était heureuse de contempler ces nombreux triangles équilatéraux, mais elle s'est rapidement demandé combien de triangles équilatéraux il y avait au total dans son dessin. Comme ils semblent trop nombreux pour être comptés à la main, écrivons un programme capable de répondre à la question d'Iha.

Entrée

La première ligne contient deux entiers séparés par un espace : $m$, la longueur du côté du grand triangle équilatéral, et $q$, le nombre de nouvelles droites tracées par Iha ($1 \le m \le 200\,000$, $0 \le q \le 3m-3$). Les sommets du grand triangle équilatéral dans la grille triangulaire sont $(0,0)$, $(m,0)$ et $(0,m)$.

Chacune des $q$ lignes suivantes contient deux entiers $d$ et $l$ séparés par un espace ($0 < l < m$). L'entier $d$ représente l'angle que fait la droite avec l'axe des $x$, et sa valeur est l'une parmi $0$, $60$ ou $120$.

• Si $d = 0$, la droite $y = l$ est ajoutée.
• Si $d = 60$, la droite $x = l$ est ajoutée.
• Si $d = 120$, la droite $x+y = l$ est ajoutée.

Toutes les droites fournies en entrée sont distinctes.

Sortie

Affichez le nombre de triangles équilatéraux qui se trouvent entièrement à l'intérieur du grand triangle équilatéral.

Les triangles qui ne sont que partiellement à l'intérieur du grand triangle équilatéral ne sont pas comptés, et un point n'est pas considéré comme un triangle équilatéral. Le grand triangle équilatéral lui-même est compté (car il est contenu dans lui-même).

Exemples

Entrée 1

2 3
0 1
60 1
120 1

Sortie 1

5

Entrée 2

10 5
60 1
120 2
0 1
120 5
60 9

Sortie 2

12

Remarque

Si l'on dessine la grille triangulaire et les droites pour les deux exemples, on obtient les figures suivantes :

Figure F.2 : Figure correspondant à l'exemple 1

Figure F.3 : Figure correspondant à l'exemple 2