Problem: There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.

Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it. Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.

Q queries are given. We ask you to process them in order. There are two kinds of queries. Their input format and description are as follows:

* `1 x`: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
* `2 x`: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.



How many black stones are there on the grid after processing all Q queries?

Constraints

* 3 \leq N \leq 2\times 10^5
* 0 \leq Q \leq \min(2N-4,2\times 10^5)
* 2 \leq x \leq N-1
* Queries are pairwise distinct.

Input

Input is given from Standard Input in the following format:


N Q
Query_1
\vdots
Query_Q


Output

Print how many black stones there are on the grid after processing all Q queries.

Examples

Input

5 5
1 3
2 3
1 4
2 2
1 2


Output

1


Input

200000 0


Output

39999200004


Input

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282


Output

31159505795

Solution (in PYTHON3):

Solution:
N, Q = map(int, input().split())

N -= 2 # 枠を取り除いたサイズに直す

#ここから33行目まで準備。Binary indexed tree(BIT)というデータ構造を使う。

BIT = [[0 for i in range(N+1)] for _ in range(2)] #BITを2つ用意
# BITでできること。
#  1, 要素の更新をO(logn)で行う
#  2, 累積和をO(logn)で求める。
# 　※ 両方ともそれなりに早くできるのがメリット。
#     普通の配列だと、1と2がそれぞれO(1),O(n)かかる。
#     一方、累積和で記録した配列だと、1と2がO(n)とO(1)かかる。
# 原理は例えばhttp://hos.ac/slides/20140319_bit.pdf参照。(これと別にsegment treeも載ってますが、同じような考え方です。)

# 以下、実装用の関数。以下のWeb記事から引用させていただきました。
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0

n = N # (直すのサボりました、ごめんなさい)

def BIT_query(idx,BIT):# 1, BITのidx番目までの要素の和を求める。
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x,BIT):# 2, BITのidx番目の要素に、xを足す。
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return
# なお、配列番号idxが1から始まることに注意。(BITの0番目には0を入れておき、「0番目までの和」としておいたほうが都合が良い。)

# 以下、本処理。
# お約束: たて座標を「右から左へ」、よこ座標を「下から上へ」カウントする。(いつもと反対なので注意)
#        座標は1からスタートさせる
#        2つのBITが表す累積和には、それぞれよこ、たて座標における「たて刺し」、「よこ刺し」が刺さる深さ（がNからどれだけ減ったか、負数）を格納する。
#        (もととなる配列の要素ではなく、累積和で表すことに注意。)

now = N * N # 現在の黒玉の数。
max_x = [0, 0] # それぞれ、これまでに刺さった「たて刺し」のうちの最大のよこ座標と、これまでに刺さった「よこ刺し」のうちの最大のたて座標を記録。最初は0とする。
for _ in range(Q):
  # 51行目まで整形作業
  s, x = map(int, input().split())
  # s=0が「たて刺し」、s=1が「よこ刺し」を表すようにする
  s -= 1 
  # 最初に両端を削った分の調整（スタートを0にしているわけではないので注意）
  x -= 1
  # いつもと逆向きに数える
  x = N+1 - x
  
  #どこまで刺さるか
  depth = N + BIT_query(x, BIT[s]) 
  now -= depth #刺さった分だけ、黒玉を減らす
  
  if x > max_x[s]: # 深さの更新処理。今までに刺さったものよりも大きい座標の場合のみ。
    BIT_update(N-depth+1, max_x[s] - x, BIT[1-s]) 
    # 反対側のBITを更新する。今刺さった深さの地点N-depth+1に、max_x[s]-xを足す。累積和なので、N-depth+1より大きい座標すべてにおいて深さが更新される。
    max_x[s] = x
    
print(now)   

# 追記：
#  刺さる深さを普通の配列で持つと、毎回O(N)回更新するためTLEするかと思い、BITを使いました。

#  しかし57行目にあるように、更新が必要なのはそれまでよりも大きい座標のところに「刺し」が入る時のみです。
#  ここで、これまでの「刺し」の最大座標よりも小さい座標に刺さる「刺し」の深さは、それ以降変化することはありません。
#  また、最大座標よりも大きい座標での「刺し」の深さは、全て同じ値になり、その値１つを記録しておけば十分です。

#  このため、普通の配列に「刺し」の最大座標よりも小さい座標についての深さを記録しておき、
#  「刺し」の最大座標よりも大きい部分については一括して１つの値で管理しておけば、
#   BITなしでも上記の目的が果たせます。