CodeEff/ECCO huggingface dataset:
# Original solution
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    visited[0] = True
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        if cur == t:
            return cost
        visited[cur] = True
        for nex in range(1, M + 1):
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return -1
            
while True:
    N, M = list(map(int, input().split()))
    if N | M == 0:
        break
    C = [[INF] * (M + 1) for _ in range(M + 1)]
    T = [[INF] * (M + 1) for _ in range(M + 1)]
    for _ in range(N):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[[False] * (M + 1) for  _ in range(M + 1)] for _ in range(2)]
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        if not checked[r][p][q]:
            A[r][p][q] = dijkstra(p, q, A[r])
            checked[r][p][q] = True
        print(A[r][p][q])

# Optimized solution
import heapq
INF = 1 << 20
N, M = 3001, 101

def dijkstra(s, t, G):
    visited = [False] * (M + 1)
    visited[0] = True
    pq = [(0,s)]
    while True:
        cost, cur = heapq.heappop(pq)
        if visited[cur]:
            continue
        if cur == t:
            return cost
        visited[cur] = True
        for nex in [x for x in range(1, M + 1) if G[cur][x] != -1 and not visited[x]]:
            heapq.heappush(pq, (cost + G[cur][nex], nex))
    return -1
            
while True:
    N, M = list(map(int, input().split()))
    if N | M == 0:
        break
    C = [[-1] * (M + 1) for _ in range(M + 1)]
    T = [[-1] * (M + 1) for _ in range(M + 1)]
    for _ in range(N):
        a, b, c, t = list(map(int, input().split()))
        C[a][b] = C[b][a] = c
        T[a][b] = T[b][a] = t
    A = (C, T)
    checked = [[[False] * (M + 1) for  _ in range(M + 1)] for _ in range(2)]
    for _ in range(eval(input())):
        p, q, r = list(map(int, input().split()))
        if not checked[r][p][q]:
            A[r][p][q] = dijkstra(p, q, A[r])
            checked[r][p][q] = True
        print(A[r][p][q])
# Original solution
import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxsize for i in range(m+1)]
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in range(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxsize:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxsize
    mincost = sys.maxsize
    for i in range(1, m+1):
      if i in defnode:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print(cost[goal])
      return
    node = minnode

while True:
  n, m = list(map(int, input().split()))
  if n == 0 and m == 0:
    break
  cost = [[sys.maxsize for i in range(m+1)] for j in range(m+1)]
  time = [[sys.maxsize for i in range(m+1)] for j in range(m+1)]
  for i in range(n):
    a, b, c, t = list(map(int, input().split()))
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)

# Optimized solution
import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxsize] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in range(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxsize:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxsize
    mincost = sys.maxsize
    for i in range(1, m+1):
      if i in defnode:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print(cost[goal])
      return
    node = minnode

while True:
  n, m = list(map(int, input().split()))
  if n == 0 and m == 0:
    break
  cost = [[sys.maxsize] * (m+1) for j in range(m+1)]
  time = [[sys.maxsize] * (m+1) for j in range(m+1)]
  for i in range(n):
    a, b, c, t = list(map(int, input().split()))
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(input())
  for i in range(k):
    p, q, r = list(map(int, input().split()))
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0200

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(1, V):
        for i in range(1, V):
            for j in range(1, V):
                if dp[i][k][0] + dp[k][j][0] < dp[i][j][0]:
                    dp[i][j][0] = dp[i][k][0] + dp[k][j][0]
                if dp[i][k][1] + dp[k][j][1] < dp[i][j][1]:
                    dp[i][j][1] = dp[i][k][1] + dp[k][j][1]


def main(args):
    while True:
        n, m = list(map(int, input().split()))
        if n == 0 and m == 0:
            break
        dp = [[[float('inf'), float('inf')]] * (m+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][i] = [0, 0]
        for _ in range(n):
            a, b, cost, time = list(map(int, input().split()))
            dp[a][b] = [time, cost]
            dp[b][a] = [time, cost]

        warshallFloyd(m+1, dp)

        k = int(eval(input()))
        for _ in range(k):
            p, q, r = list(map(int, input().split()))
            if r == 0:          #  cost
                print((dp[p][q][1]))
            else:               #  time
                print((dp[p][q][0]))



if __name__ == '__main__':
    main(sys.argv[1:])

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0200

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(1, V):
        for i in range(1, V):
            for j in range(1, V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    while True:
        n, m = list(map(int, input().split()))
        if n == 0 and m == 0:
            break
        dp_time = [[float('inf')] * (m+1) for _ in range(m+1)]
        dp_cost = [[float('inf')] * (m+1) for _ in range(m+1)]
        for i in range(m+1):
            dp_time[i][i] = 0
            dp_cost[i][i] = 0

        for _ in range(n):
            a, b, cost, time = list(map(int, input().split()))
            dp_time[a][b] = time
            dp_time[b][a] = time
            dp_cost[a][b] = cost
            dp_cost[b][a] = cost

        warshallFloyd(m+1, dp_time)
        warshallFloyd(m+1, dp_cost)

        k = int(eval(input()))
        for _ in range(k):
            p, q, r = list(map(int, input().split()))
            if r == 0:
                print((dp_cost[p][q]))
            else:
                print((dp_time[p][q]))



if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

# Optimized solution
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                rows[x:min_col] = [min_row] * (min_col - x)
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                cols[x:min_row] = [min_col] * (min_row - x)
                min_row = x
            black -= cols[x] - 1

    print(black)

main()
# Original solution
n,q=list(map(int,input().split()))
nowbl=(n-2)**2
mu=[n-1]*n 
mh= [n-1]*n 

nowu=n-1 ; nowh=n-1
for i in range(q):
    a,b=list(map(int,input().split()))
    a-=1;b-=1
    if a==0:
        if mu[b]==1:
            continue
        nowbl-= mu[b]-1
        mu[b]=0
        if nowu< b:
            continue
        nowu=b
        for i in range(1,nowh):
            mh[i]= min(mh[i],b)
        
    if a==1:
        a=b
        if mh[a]==1:
            continue
        nowbl-= mh[a]-1
        mh[a]=0
        if nowh< a:
            continue
        nowh= a 
        for i in range(1,nowu):
            mu[i]= min(mu[i],a)
print(nowbl)
        
        


# Optimized solution
n,q=list(map(int,input().split()))
x= n-2
y= n-2
dx={}
dy={}

for _ in range(q):
    a,b=list(map(int,input().split()))
    b-=1
    if a==1:
        if y< b:
            dy[b]=0;continue
        # y= b-1
        for i in range(b+1,y+1):
            dy[i] = x
        y=b-1

    if a==2:
        if x < b:
            dx[b]=0;continue
        # x=b-1
        for i in range(b+1,x+1):
            dx[i] =y
        x=b-1
print((x*y + sum(dx.values()) + sum(dy.values()) ))
# Original solution
from bisect import bisect_left as bl

N, Q = list(map(int, input().split()))
ans = 0
q1 = []
q2 = []
query = []
for _ in range(Q):
    n, p = list(map(int, input().split()))
    query.append((n, p))
    if n == 1:
        q1.append(p)
    else:
        q2.append(p)
q1.sort()
q2.sort()
board = [N - 2, N - 2]
for n, p in query:
    if n == 1:
        if p > board[1] + 1:
            continue
        index = bl(q1, p)
        ans += board[0] * (len(q1) - index)
        board[1] = p - 2
        q1 = q1[:index]
    else:
        if p > board[0] + 1:
            continue
        index = bl(q2, p)
        ans += board[1] * (len(q2) - index)
        board[0] = p - 2
        q2 = q2[:index]
print(((N - 2) ** 2 - ans))

# Optimized solution
from bisect import bisect_left as bl

N, Q = list(map(int, input().split()))
ans = 0
q1 = []
q2 = []
query = []
for _ in range(Q):
    n, p = list(map(int, input().split()))
    query.append((n, p))
    if n == 1:
        q1.append(p)
    else:
        q2.append(p)
q1.sort()
q2.sort()
board = [N - 2, N - 2]
count1 = len(q1)
count2 = len(q2)
for n, p in query:
    if n == 1:
        if p > board[1] + 1:
            continue
        index = bl(q1, p)
        ans += board[0] * (count1 - index)
        board[1] = p - 2
        count1 = index
    else:
        if p > board[0] + 1:
            continue
        index = bl(q2, p)
        ans += board[1] * (count2 - index)
        board[0] = p - 2
        count2 = index
print(((N - 2) ** 2 - ans))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(top):
                verti[i] = x-1
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(left):
                horiz[i] = x-1
        else:
            ans -= verti[x-1]
print(ans)

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
last_top = (N-2, N-2)
last_left = (N-2, N-2)
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(left, last_left[0]+1):
                horiz[i] = last_top[1]
            last_left = (left, x-1)
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(top, last_top[0]+1):
                verti[i] = last_left[1]
            last_top = (top, x-1)
        else:
            ans -= verti[x-1]
print(ans)
# Original solution
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    black = (N-2)**2
    chList = [[N-2] * N for _ in range(2)]

    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        black -= ch
        for i in range(2, min(ch+2, N)):
            chList[1-y][i] = min(max(x-2, 0), chList[1-y][i])

    # ------ 出力 ------#
    print(("{}".format(black)))

if __name__ == '__main__':
    main()


# Optimized solution
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 二分探査
def binary_search(list, item):
    # 1:以上 2:以下　
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    black = (N-2)**2
    m = [N, N]
    chList = [[-1] * N for _ in range(2)]
    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        if ch == -1:
            ch = m[1-y] - 2
            m[y] = x
            i = 0
            while x+i <= N-1 and chList[y][x+i] == -1:
                chList[y][x+i] = m[1-y] - 2
                i = i + 1
        black -= ch

    # ------ 処理 ------#
    # black = (N-2)**2
    # div = [{2: N-2}, {2: N-2}]
    # for que in queList:
    #     x = que[1]
    #     y = que[0]-1
    #     kl = list(div[y].keys())
    #     d = binary_search(kl, x)
    #     ch = div[y][kl[d]]
    #     black -= ch
    #     if d == 0:
    #         div[y][x] = div[y][kl[d]]
    #         div[y] = dict(sorted(div[y].items(), key=lambda x:x[0]))
    #         div[1-y][list(div[1-y].keys())[d]] = max(x-2, 0)

    # ------ 出力 ------#
    print(("{}".format(black)))

if __name__ == '__main__':
    main()
# Original solution
n, q = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        for i in range(x, cnt[num]):
            wh[num][i] = cnt[1 - num]
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)


# Optimized solution
n, q = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        wh[num][x:cnt[num]] = [cnt[1 - num]] * (cnt[num] - x)
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)
# Original solution
N,Q = list(map(int, input().split()))
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q)-1
  while right-left>0:
    index = (left+right)//2
    if q[index][0] < n:
      left = index+1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = list(map(int, input().split()))
  if n == 1:
    index = binary_search(q1[::-1],x)
    q = q1[-index-1]
    answer -= q[1]
    if index == 0:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2[::-1],x)
    q = q2[-index-1]
    answer -= q[1]
    if index == 0:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)

# Optimized solution
N,Q = list(map(int, input().split()))
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q) - 1
  while right > left:
    index = (left + right) // 2
    if q[index+1][0] > n:
      left = index + 1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = list(map(int, input().split()))
  if n == 1:
    index = binary_search(q1,x)
    q = q1[index]
    answer -= q[1]
    if index == len(q1)-1:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2,x)
    q = q2[index]
    answer -= q[1]
    if index == len(q2)-1:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)
# Original solution
class BinaryIndexedTree:  # 0-index !!!
    """
    init(n):     要素数nを与えて0で初期化
    add(i, x):   i番目の値にxを追加 O(logN)
    sum(i):      区間[0,i)の和を返す O(logN)
    query(l, r): 区間[l,r)の和を返す O(logN)
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def set(self, i, x):
        now = self.query(i, i + 1)
        self.add(i, -now + x)

    def sum(self, i):  # 0-index  sum of [0,i)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        tmp = t1[x]
        ans -= tmp - 2
        if x < w:
            w = x
            for i in range(h + 1):
                t2[i] = w
    else:
        tmp = t2[x]
        ans -= tmp - 2
        if x < h:
            h = x
            for i in range(w + 1):
                t1[i] = h
print(ans)


# Optimized solution
n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)
# Original solution
n, q = list(map(int, input().split()))
query = []
for _ in range(q):
    t, x = list(map(int, input().split()))
    query.append((t-1, x))
black = (n-2)**2
rc = [[n, n] for _ in range(n)]
mrc = [n, n]
for t, x in query:
    black -= rc[x][t]-2
    if x < mrc[t]:
        mrc[t] = x
        for i in range(rc[x][t]):
            rc[i][1-t] = x 
print(black)

# Optimized solution
from collections import deque
n, q = list(map(int, input().split()))
query = []
for _ in range(q):
    t, x = list(map(int, input().split()))
    query.append((t-1, x))
black = (n-2)**2
rc = [deque([(n, n)]), deque([(n, n)])]
mrc = [n, n]

def bisect(li, x):
    ok = -1
    ng = len(li)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if li[mid][0]<x:
            ok = mid
        else:
            ng = mid
    return ok+1

for t, x in query:
    tmp = rc[t][bisect(rc[t], x)][1]
    black -= tmp-2
    if x < mrc[t]:
        mrc[t] = x
        rc[1-t].appendleft((tmp, x))
print(black)
# Original solution
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools

def main():
    N, Q = MI()
    #i行の一番右をline_right[i],　j列目の一番下をcolumn_under[j]とする。
    line_right = [N] * N
    column_under = [N] * N
    bla = pow(N - 2, 2)
    x_min = N
    y_min = N
    for i in range(Q):
        query = LI()
        if query[0] == 1:
            w = query[1]
            x = column_under[w]
            bla -= x - 2
            if w < x_min:
                for j in range(x):
                    line_right[j] = w
                x_min = w
        else:
            y = query[1]
            z = line_right[y]
            bla -= z - 2
            if y < y_min:
                for j in range(z):
                    column_under[j] = y
                y_min = y
    print(bla)
if __name__ == "__main__":
    main()



# Optimized solution
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools

def main():
    N, Q = MI()
    #i行の一番右をline_right[i],　j列目の一番下をcolumn_under[j]とする。
    line_right = deque([(N, N)])
    line_right_keys = deque([N])
    column_under = deque([(N, N)])
    column_under_keys = deque([N])
    bla = pow(N - 2, 2)
    x_min = N
    y_min = N
    for i in range(Q):
        query = LI()
        if query[0] == 1:
            w = query[1]
            x = bisect.bisect_left(column_under_keys, w)
            bla -= column_under[x][1] - 2
            if w < x_min:
                line_right.appendleft((column_under[x][1], w))
                line_right_keys.appendleft(column_under[x][1])
                x_min = w
        else:
            y = query[1]
            z = bisect.bisect_left(line_right_keys, y)
            bla -= line_right[z][1] - 2
            if y < y_min:
                column_under.appendleft((line_right[z][1], y))
                column_under_keys.appendleft(line_right[z][1])
                y_min = y
    print(bla)
if __name__ == "__main__":
    main()
# Original solution
N, Q = list(map(int, input().split()))

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miCol = N
miRow = N

for _ in range(Q):
    q, x = list(map(int, input().split()))

    if q == 1:
        ans -= row[x]
        for i in range(miCol + 1):
            col[i] = min(col[i], x - 2)
        miRow = min(miRow, x)
    if q == 2:
        ans -= col[x]
        for i in range(miRow + 1):
            row[i] = min(row[i], x - 2)
        miCol = min(miCol, x)

print(ans)


# Optimized solution
N, Q = list(map(int, input().split()))

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miRow = N
miCol = N

for _ in range(Q):
    q, x = list(map(int, input().split()))

    if q == 1:
        for i in range(x, miRow + 1):
            row[i] = min(row[i], miCol - 2)
        miRow = min(x, miRow)
        ans -= row[x]

    if q == 2:
        for i in range(x, miCol + 1):
            col[i] = min(col[i], miRow - 2)
        miCol = min(x, miCol)
        ans -= col[x]

print(ans)