三角形は意外にも偉大である。円は満3歳になれば真似して描くことができ、四角形は満4歳になれば描くことができる。しかし、三角形はそれよりもさらに1年経たなければ描くことができないと知られている（安孝燮、申熙英、『洪彰義 小児科学』、未来N (2020)、第12版）。

イハ（Iha）は満5歳になってからずいぶん経つため、無理なく紙にペンで一辺の長さが $m$ である「大きな正三角形」を1つ描いた。

イハの好奇心をもう少し探る前に、三角格子についての定義が必要である。座標平面において $x$ 軸が $y$ 軸と直角をなす直交座標系とは異なり、三角格子は次の図のように $x$ 軸と $y$ 軸のなす角度が $60$ 度である。ここに $x+y = m$ の形の直線を描くと、次の図のように $(0,0)$, $(m,0)$, $(0,m)$ を頂点とする正三角形が1つ作られる。この正三角形を「大きな正三角形」と呼ぶことにしよう。

図 F.1: 三角格子の両軸と $x+y = m$ の形の直線

イハはさらに多くの正三角形を描きたくなり、3つの辺のいずれかに平行でありながら大きな正三角形の内部を通過する直線を $q$ 本引いた後、大きな正三角形に含まれない部分は消してしまった。すると、正三角形が花のように咲き誇った！

イハは数多くの正三角形を見て幸せになったが、すぐに絵の中に正三角形が全部で何個あるのか気になり始めた。手で数えるには多すぎるように見えるので、イハの疑問に答えることができるプログラムを作成してみよう。

入力

1行目には、大きな正三角形の一辺の長さを表す整数 $m$ と、イハが新しく引いた直線の本数 $q$ が空白で区切られて与えられる。($1 \le m \le 200\,000$, $0 \le q \le 3m-3$) 大きな正三角形の頂点は、三角格子において $(0,0)$, $(m,0)$, $(0,m)$ である。

続く $q$ 行には、それぞれ2つの整数 $d$ と $l$ が空白で区切られて与えられる。($0 < l < m$) $d$ は $x$ 軸となす角度を意味し、$0$, $60$, $120$ のいずれかである。$d$ が $0$ であれば直線 $y = l$ が、$60$ であれば直線 $x = l$ が、$120$ であれば直線 $x+y = l$ が追加される。

入力として与えられる直線はすべて異なる。

出力

大きな正三角形の内部にある正三角形の個数を出力する。一部だけが大きな正三角形の内部にある正三角形は含めず、点は正三角形とはみなさない。大きな正三角形自体も、自分自身の内部にあるものとする。

入出力例

入力 1

2 3
0 1
60 1
120 1

出力 1

5

入力 2

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

出力 2

12

注記

2つの例の三角格子と直線をプロットすると、次のようになる。

図 F.2: 入出力例 1に対応する図

図 F.3: 入出力例 2に対応する図