Triangles are surprisingly great. A circle can be traced by a 3-year-old, and a square can be drawn by a 4-year-old. However, it is known that a triangle can only be drawn after another year has passed (Hyo-Seop Ahn, Hee-Young Shin, Hong Chang-ui Pediatrics, Mirae N (2020), 12th edition).

Since Yiha is well past 5 years old, she easily drew a "large equilateral triangle" with side length $m$ on paper with a pen.

Before exploring Yiha's curiosity further, we need a definition of a triangular grid. Unlike the Cartesian coordinate system where the $x$-axis and $y$-axis are perpendicular, in a triangular grid, the angle between the $x$-axis and $y$-axis is 60 degrees. If we draw a line of the form $x+y = m$ here, an equilateral triangle with vertices $(0,0)$, $(m,0)$, and $(0,m)$ is formed, as shown in the figure below. Let's call this equilateral triangle the "large equilateral triangle".

Figure F.1: Both axes of the triangular grid and the line of the form x+y = m

Yiha wanted to draw even more equilateral triangles, so she drew $q$ lines that are parallel to one of the three sides and pass through the interior of the large equilateral triangle, and then erased the parts not contained in the large equilateral triangle. Then, equilateral triangles bloomed like flowers!

Yiha was happy looking at the numerous equilateral triangles, but soon wondered how many equilateral triangles there are in total in the drawing. Since there seem to be too many to count by hand, let's write a program to answer Yiha's question.

Input

The first line contains two space-separated integers $m$, the side length of the large equilateral triangle, and $q$, the number of new lines Yiha drew ($1 \le m \le 200\,000$, $0 \le q \le 3m-3$). The vertices of the large equilateral triangle are $(0,0)$, $(m,0)$, and $(0,m)$ in the triangular grid.

Each of the next $q$ lines contains two space-separated integers $d$ and $l$ ($0 < l < m$). Here, $d$ represents the angle the line makes with the $x$-axis, and is one of $0$, $60$, or $120$.

• If $d$ is $0$, the line $y = l$ is added.
• If $d$ is $60$, the line $x = l$ is added.
• If $d$ is $120$, the line $x+y = l$ is added.

All lines given in the input are distinct.

Output

Output the number of equilateral triangles inside the large equilateral triangle. Equilateral triangles that are only partially inside the large equilateral triangle are not included, and a single point is not considered an equilateral triangle. The large equilateral triangle itself is also considered to be inside itself.

Examples

Input 1

2 3
0 1
60 1
120 1

Output 1

5

Input 2

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

Output 2

12

Note

Drawing the triangular grid and lines for the two examples gives the following:

Figure F.2: Figure corresponding to Example 1

Figure F.3: Figure corresponding to Example 2