Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = [N - 2] * (N - 1)
    W = [N - 2] * (N - 1)

    ans = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            # print("*** ", W[x - 1])
            ans -= W[x - 1]
            if x - 1 < Wmin:
                for j in range(Hmin):
                    H[j] = x - 2
                Wmin = x - 1
        else:
            # print("*** ", H[x - 1])
            ans -= H[x - 1]
            if x - 1 < Hmin:
                for j in range(Wmin):
                    W[j] = x - 2
                Hmin = x - 1

    print(ans)


main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([0] * (N - 1))
    W = np.array([0] * (N - 1))

    black = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            if x - 1 <= Wmin:
                W[x - 1:Wmin] = Hmin - 1
                Wmin = x - 1
            # print("***", W[x - 1], Wmin, Hmin)
            black -= W[x - 1]
        else:
            if x - 1 <= Hmin:
                H[x - 1:Hmin] = Wmin - 1
                Hmin = x - 1
            # print("***", H[x - 1], Wmin, Hmin)
            black -= H[x - 1]

    print(black)


main()
### BUGGY CODE ###

a, b = map(int, input().split())
l_value = max([a, b])
s_value = min([a, b])
temp_list = []
for i in range(1, s_value + 1):
  if s_value % i == 0:
    temp_list.append(i)
dev_list = []
for i in temp_list:
  if i == 1 or i == 2:
    dev_list.append(i)
  else:
    for j in range(2, i):
      if i % j == 0:
        break
      elif j == i - 1:
        dev_list.append(i)
ans = 0
for dev in dev_list:
  if l_value % dev == 0:
    ans += 1
print(ans)

### FIXED CODE ###

# -*- Coding: utf-8 -*-
a, b = map(int, input().split())
def my_gcd(a, b):
  if b == 0:
    return a
  else:
    return my_gcd(b, a % b)

gcd = my_gcd(a, b)
sqrt_gcd = int(gcd ** 0.5)
div_list = []
i = 2
res_gcd = gcd

while i <= sqrt_gcd:
  if res_gcd % i == 0:
    div_list.append(i)
    res_gcd = res_gcd / i
  else:
    i += 1
  if res_gcd == 1:
    break
if res_gcd > 1:
  div_list.append(gcd)
uni_cd = list(set(div_list))
ans = 1 + len(uni_cd)
print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())#行数H、列数W、爆弾数M
hcnt = [0 for i in range(H)]#何行目に何個あるか
wcnt = [0 for i in range(W)]#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

import sys
A, B = map(int, sys.stdin.readline().split())

a, b = [], []
for i in range(A, 0, -1):
    if A%i ==0:
        a.append(A//i)
    
for i in range(B, 0, -1):
    if B%i ==0:
        b.append(B//i)

a,b = set(a), set(b)
L = a&b
#print(L)
cnt =0
for l in L:
    tmp = 0
    for i in range(l-1, 1, -1):
        if l%i==0:
            tmp +=1
            break
    if tmp ==0:
        cnt+=1
print(cnt)

### FIXED CODE ###

import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))
### BUGGY CODE ###

n=int(input())
ans=0
def c(i,j):
  ret=0
  for k in range(1,n+1):
    if str(k)[0]==str(i) and str(k)[-1]==str(j):
      ret+=1
  return ret
for i in range(1,10):
  for j in range(1,10):
    ans+=c(i,j)*c(j,i)
print(ans)

### FIXED CODE ###

def main(n):
  def c(i,j):
    ret=0
    for k in range(1,n+1):
      if str(k)[0]==str(i) and str(k)[-1]==str(j):
        ret+=1
    return ret
  ans=0
  for a in range(1,10):
    for b in range(a,10):
      d=c(a,b)*c(b,a)
      ans+=d
      if a!=b:
        ans+=d
  print(ans)
if __name__=='__main__':
  n=int(input())
  main(n)
### BUGGY CODE ###

def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    w[x][y] = 0
                    for z in range(h-max(x,y)):
                        if c[y+z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    if x == y:
                        dp[x][y] = 0
                    elif x == 0:
                        dp[x][y] = dp[x][y-1]+w[x][y-1]
                    else:
                        dp[x][y] = dp[x-1][y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
N = int(input())
count = 0
flag = False
# n = int(math.sqrt(N))
n = N // 5

for i in range(1, N + 1):
    
    for j in range(1, n):
        for l in range(1, n):
            for r in range(1, n):
                if j + l + r > N // 2:
                    continue
                if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
                    if j == l == r:
                        flag = True
                        count = 1
                        break
                    else:
                        flag = True
                        count = 3
                        break
            if flag:
                break
        if flag:
            break            
    print(count)
    count = 0
    flag = False

### FIXED CODE ###

# # import math
N = int(input())
# # count = 0
# # flag = False
# # # n = int(math.sqrt(N))
n = 105

# # for i in range(1, N + 1):
    
# #     for j in range(1, n):
# #         for l in range(1, n):
# #             for r in range(1, n):
# #                 if j + l + r > N // 2:
# #                     continue
# #                 if j ** 2 + l ** 2 + r ** 2 + j * l + j * r + l * r == i:
# #                     if j == l == r:
# #                         flag = True
# #                         count = 1
# #                         break
# #                     else:
# #                         flag = True
# #                         count = 3
# #                         break
# #             if flag:
# #                 break
# #         if flag:
# #             break            
# #     print(count)
# #     count = 0
# #     flag = False
ans = [0] * 10050
for j in range(1, n):
    for l in range(1, n):
        for r in range(1, n):
            value = j * j  + l * l + r * r + j * l + j * r + l * r
            if value < 10050:
                ans[value] += 1

for i in range(N):
    print(ans[i + 1])
# n = int(input())
# ans = [0 for _ in range(10050)]
# for i in range(1,105):
#     for j in range(1,105):
#         for k in range(1,105):
#             v = i*i+j*j+k*k+i*j+j*k+k*i;
#             if v<10050:
#                 ans[v]+=1   
# for i in range(n):
#     print(ans[i+1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        for i,(x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                xcost = min(xcost, abs(x - lx))
                ycost = min(ycost, abs(y - ly))
            xc[s][i] = xcost * p
            yc[s][i] = ycost * p

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs=xc[xs]
            ycs=yc[s-xs]
            ans[k]=min(ans[k], sum(min(xcs[i], ycs[i]) for i in range(n)))
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        xcs = xc[s]
        ycs = yc[s]
        for i, (x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                if abs(x - lx) < xcost: xcost = abs(x - lx)
                if abs(y - ly) < ycost: ycost = abs(y - ly)
            xcs[i] = xcost * p
            ycs[i] = ycost * p
    # print(xc)

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs = xc[xs]
            ycs = yc[s - xs]
            cur = 0
            for i in range(n): cur += min(xcs[i], ycs[i])
            if cur < ans[k]: ans[k] = cur
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()
### BUGGY CODE ###

n=int(input())
A = list(map(int, input().split()))
for i in range(0,n-1):
    for j in range(i+1,n):
        if A[i]==A[j]:
            print("NO")
            break
    else:
        continue
    break
else:
    print("YES")

### FIXED CODE ###

import collections
n=int(input())
A = list(map(int, input().split()))
c=collections.Counter(A)
if len(c)==len(A):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import heapq
def main():
	N, M = map(int, input().split())
	A = list(map(int, input().split()))
	heapq.heapify(A)
	for _ in range(M):
		B, C = list(map(int, input().split()))
		for _ in range(B):
			if A[0] > C:
				break
			heapq.heappop(A)
			heapq.heappush(A, C)
	print(sum(A))


if __name__ == '__main__':
	main()

### FIXED CODE ###

import heapq
def main():
	N, M = map(int, input().split())
	A = list(map(int, input().split()))
	heapq.heapify(A)
	BC = [0]*M
	for i in range(M):
		BC[i] = list(map(int, input().split()))
	BC.sort(key = lambda x: -x[1])
	for B, C in BC:
		if A[0] >= C:
			break
		for _ in range(B):
			if A[0] >= C:
				break
			heapq.heapreplace(A, C)
	print(sum(A))


if __name__ == '__main__':
	main()
### BUGGY CODE ###

MOD=1000000007
N=input()
A = [int(x) for x in input().split()]
l=len(A)
s=0
for i in range(l):
    B=A[i+1:l]
    s+=A[i]*sum(B)
print(s%MOD)

### FIXED CODE ###

MOD=1000000007
N=input()
A = list(map(int,input().split()))
l=len(A)
s=0
B=sum(A)
for i in range(l):
    B-=A[i]
    s+=A[i]*B
print(s%MOD)
### BUGGY CODE ###

a=input()
b=input()

answer=0
i=0
while i<len(a):
 if a[i]!=b[i]:
  answer = answer+ 1
  i =i+1

print(answer)

### FIXED CODE ###

a=input()
b=input()

answer=0
i=0
while i<len(a):
 if a[i]!=b[i]:
  answer = answer+ 1
 i =i+1

print(answer)
### BUGGY CODE ###

# E - Two Currencies

n, m, s = map(int, input().split())
#adj = {u: [] for u in range(1, n+1)}
edge = []
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    #adj[u].append((v, a, b)) # 行き先, 料金, 時間
    #adj[v].append((u, a, b))
    edge.append((u, v, a, b)) # from, to, 料金, 時間
    max_silver += a # 料金の総和
exch = {}
max_rate = 0
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間
    max_rate = max(max_rate, c)
max_silver += max_rate - 1
s = min(s, max_silver)

# (都市,銀貨)を頂点とする最短経路問題

dist = {(1, s): 0}
for i in range(n * max_silver):
    for e in edge:
        u, v, a, b = e
        for sil in range(a, max_silver+1):
            if (u, sil) in dist:
                if (v, sil - a) not in dist or \
                    dist[(v, sil - a)] > dist[(u, sil)] + b:
                    dist[(v, sil - a)] = dist[(u, sil)] + b
            if (v, sil) in dist:
                if (u, sil - a) not in dist or \
                    dist[(u, sil - a)] > dist[(v, sil)] + b:
                    dist[(u, sil - a)] = dist[(v, sil)] + b
    for u in range(1, n+1):
        for sil in range(0, max_silver+1):
            c, d = exch[u]
            if (u, sil) in dist:
                if (u, sil + c) not in dist or \
                    dist[(u, sil + c)] > dist[(u, sil)] + d:
                    dist[(u, sil + c)] = dist[(u, sil)] + d

for u in range(2, n+1):
    x = min(dist[(u, sil)] for sil in range(0, max_silver+1)
            if (u, sil) in dist)
    print(x)


### FIXED CODE ###

# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])
### BUGGY CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        char = s[i-1]
        if char == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        char = s[i-1]
        if char == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])
### BUGGY CODE ###

class Gcd:

    def __init__(self, K):
        self.table = [[None] * K for i in range(K)]
        return

    def gcd(self, x, y):
        if self.table[x - 1][y - 1] is not None:
            return self.table[x - 1][y - 1]

        if x == y:
            self.table[x - 1][y - 1] = x
            return x
        elif x > y:
            z = x % y
            if z == 0:
                self.table[x - 1][y - 1] = y
                return y
            else:
                z = self.gcd(z, y)
                self.table[x - 1][y - 1] = z
                return z
        else:
            return self.gcd(y, x)

def quest_c():
    K = int(input())

    gcd = Gcd(K)
    sum = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            d = gcd.gcd(a, b)
            for c in range(1, K + 1):
                sum += gcd.gcd(d, c)
    print(sum)

if __name__ == '__main__':
    quest_c()

### FIXED CODE ###

class Gcd:

    def __init__(self, K):
        self.table = [[None] * K for i in range(K)]
        return

    def gcd(self, x, y):
        if self.table[x - 1][y - 1] is not None:
            return self.table[x - 1][y - 1]

        if x == y:
            self.table[x - 1][y - 1] = x
            return x
        elif x > y:
            z = x % y
            if z == 0:
                self.table[x - 1][y - 1] = y
                return y
            else:
                z = self.gcd(z, y)
                self.table[x - 1][y - 1] = z
                return z
        else:
            return self.gcd(y, x)

def quest_c():
    K = int(input())

    gcd = Gcd(K)
    sum = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            d = gcd.gcd(a, b)
            if d == 1:
                sum += K
            else:
                for c in range(1, K + 1):
                    sum += gcd.gcd(d, c)
    print(sum)

if __name__ == '__main__':
    quest_c()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

b = []
b.append(a[0])
ans = 0
for i in range(1,n):
    if a[i] < max(b):
        humi = (max(b)-a[i])
        a[i] += humi
    else:
        humi = 0
    b.append(a[i])
    ans += humi

print(ans)


### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))

high = [0]*n
for i in range(1,len(a)):
    if a[i] <= a[i-1]:
        dai = a[i-1] - a[i]
        a[i] += dai
        high[i] = dai


print(sum(high))
### BUGGY CODE ###

from collections import deque
MOD = 998244353
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

S = list()
for lr in LR:
    for i in range(lr[0], lr[1]+1):
        S.append(i)

dp = [0]*(N+1) # dp[i] : iに行く方法
dp[1] = 1

memo1 = deque()
memo2 = deque()

for i in range(1, N+1):
    # for s in S:
    #     if i + s <= N:
    #         dp[i + s] += dp[i]
    #         dp[i + s] %= MOD
    while(len(memo1)):
        # l = m[1]
        # r = m[2]
        m = memo1.popleft()
        if m[1] <= i and i <= m[2]:
            dp[i] += m[0]
            dp[i] %= MOD
        
        if not(m[2] < i):
            memo2.append(m)
    
    while(len(memo2)):
        tmp = memo2.popleft()
        memo1.append(tmp)
    
    for lr in LR:
        memo1.append([dp[i], lr[0] + i, lr[1] + i])
    
print(dp[N])

### FIXED CODE ###

MOD = 998244353
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])
# print(acc)
# print(dp[N])
### BUGGY CODE ###

def main():
    n,m=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(m)]
    S=[]
    for l in L:
        if l[0]==1: S.append(l[1])
    for l in L:
        if l[0] in S and l[1]==n:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(m)]
    S=[]
    G=[]
    for l in L:
        if l[0]==1: S.append(l[1])
        if l[1]==n: G.append(l[0])
    print("POSSIBLE"if len(set(S)&set(G))>0 else "IMPOSSIBLE")
main()
### BUGGY CODE ###

N, K = map(int, input().split())

if K==0:
    print(N)
else:
    while N!=0:
        if N>=abs(N-K):
            N = abs(N-K)
        elif N==0:
            break
        else:
            break
            
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
if N>=K:
  N = N%K

while N!=0:
  if N>=abs(N-K):
    N = abs(N-K)
  elif N==0:
    break  
  else:
    break
print(N)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
h = []
for a in A:
    heapq.heappush(h, a)

for i in range(M):
    B, C = map(int, input().split())
    for i in range(B):
        vmin = heapq.heappop(h)
        if vmin < C:
            heapq.heappush(h, C)
        else:
            heapq.heappush(h, vmin)
            break

print(sum(h))


### FIXED CODE ###

import math
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB.sort(reverse=True)

p = 0
for C, B in CB:
    while p < len(A) and A[p] >= C:
        p += 1
    if p >= len(A):
        break
    for i in range(B):
        if p >= len(A):
            break
        if A[p] < C:
            A[p] = C
            p += 1
        else:
            break
print(sum(A))