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

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[set() for _ in range(w)] for _ in range(h)]

    dp[0][0].add(diff[0][0])

    from collections import deque
    que = deque()
    que.append((0, 0))

    while que:
        row, col = que.popleft()

        if row + 1 < h:
            que.append((row + 1, col))
            for num in dp[row][col]:
                dp[row + 1][col].add(num + diff[row + 1][col])
                dp[row + 1][col].add(abs(num - diff[row + 1][col]))

        if col + 1 < w:
            que.append((row, col + 1))
            for num in dp[row][col]:
                dp[row][col + 1].add(num + diff[row][col + 1])
                dp[row][col + 1].add(abs(num - diff[row][col + 1]))

    cand = list(dp[h - 1][w - 1])

    print(min(cand))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[1 << (80 * 160 + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0] |= 1 << diff[0][0]

    from itertools import product

    for row, col in product(range(h), range(w)):
        diff_cur = diff[row][col]
        prevset = 0

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        dp[row][col] |= (prevset << diff_cur)
        dp[row][col] |= (prevset >> diff_cur)
        temp = 0
        for i in range(diff_cur):
            if prevset >> i & 1:
                temp += (1 << diff_cur - i)
        dp[row][col] |= temp

    for i in range(12801):
        if dp[h - 1][w - 1] >> i & 1:
            print(i)
            sys.exit()


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

from collections import defaultdict
import math
N=int(input())

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret=set()
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)
  #print(div_set,bumbo)
  for d in div_set:
    #print(d,bumbo)
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
answer2=0
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    #print(bunshi,d)
    answer2+=div_dic2[(bumbo,d)]

#print(answer,answer2)
print(answer+answer2//2)

### FIXED CODE ###

from collections import defaultdict
N=int(input())

def pow25(x):
  f2=f5=0
  while x%2==0:
    x//=2
    f2+=1
  while x%5==0:
    x//=5
    f5+=1
  return f2,f5

pow25_dic=defaultdict(int)
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))    
    bunshi=10**9*seisu+shosu
  else:
    bunshi=10**9*int(a)
    
  pow25_dic[pow25(bunshi)]+=1
#print(pow25_dic)

pow25_key_list=[]
for key in pow25_dic:
  pow25_key_list.append(key)
#print(pow25_key_list)

answer=0
for i in range(len(pow25_key_list)):
  f2,f5=pow25_key_list[i]
  value=pow25_dic[(f2,f5)]
  if f2>=9 and f5>=9:    
    answer+=value*(value-1)//2
    
  for j in range(i+1,len(pow25_key_list)):
    f2_2,f5_2=pow25_key_list[j]
    if f2+f2_2>=18 and f5+f5_2>=18:
      value2=pow25_dic[(f2_2,f5_2)]
      answer+=value*value2
      
print(answer)
### BUGGY CODE ###

def main():
    import numpy as np
    from itertools import product
    H, W, K = map(int, input().split())
    G = np.array([list(map(int, list(input()))) for _ in range(H)])
    #print(np.count_nonzero(G[:, 1:1]))
    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        rows = []
        for i in range(len(div) - 1):
            rows.append(np.sum(G[div[i]: div[i + 1]], axis=0).tolist())

        w = 0
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


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

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

odd = [vec[i] for i in range(0, n, 2)]
odd = [(n, odd.count(n)) for n in set(odd)]
odd.sort(key=lambda tpl: tpl[1], reverse=True)

even = [vec[i] for i in range(1, n, 2)]
even = [(n, even.count(n)) for n in set(even)]
even.sort(key=lambda tpl: tpl[1], reverse=True)

if odd[0][0] == even[0][0]:
    if odd[0][1] > even[0][1]:
        print(
            sum([cnt for _, cnt in odd[1:]]) + even[0][1] +
            sum([cnt for _, cnt in even[2:]]))
    else:
        print(
            sum([cnt for _, cnt in even[1:]]) + odd[0][1] +
            sum([cnt for _, cnt in odd[2:]]))
else:
    print(sum([cnt for _, cnt in odd[1:]]) + sum([cnt for _, cnt in even[1:]]))


### FIXED CODE ###

from collections import defaultdict

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

evens = defaultdict(lambda: 0)
odds = defaultdict(lambda: 0)
for i in range(0, n, 2):
    evens[numbers[i]] += 1
    odds[numbers[i + 1]] += 1

evens = list(evens.items())
odds = list(odds.items())

evens.sort(key=lambda pair: pair[1], reverse=True)
odds.sort(key=lambda pair: pair[1], reverse=True)

if len(evens) == 1 and len(odds) == 1:
    if evens[0][0] == odds[0][0]:
        print(n // 2)
    else:
        print(0)
    exit()

if len(evens) == 1 or len(odds) == 1:
    pairs = evens if len(evens) > len(odds) else odds
    if evens[0][0] == odds[0][0]:
        del pairs[1]
    else:
        del pairs[0]
    print(sum([v for _, v in pairs]))
    exit()

if evens[0][0] == odds[0][0]:
    if evens[0][1] == odds[0][1]:
        if evens[1][1] > odds[1][1]:
            del evens[1]
            del odds[0]
        else:
            del evens[0]
            del odds[1]
    elif evens[0][1] > odds[0][1]:
        del evens[0]
        del odds[1]
    else:
        del evens[1]
        del odds[0]
else:
    del evens[0]
    del odds[0]
print(sum([v for _, v in evens]) + sum([v for _, v in odds]))
### BUGGY CODE ###

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

time_A = list(map(int, input().split()))
time_B = list(map(int, input().split()))
max_books = 0
allot_to_A = 0
allot_to_B = K

while True:
    num_books = 0
    change_point_A = 10000000000
    change_point_B = 10000000000
    time_bankA = allot_to_A
    time_bankB = allot_to_B

    for i in range(len(time_A)):
        if time_A[i] <= time_bankA:
            time_bankA -= time_A[i]
            num_books += 1
        else:
            change_point_A = time_A[i] - time_bankA  # Aで読める本が１冊増える時間
            break

    for j in range(len(time_B)):
        if time_B[j] <= time_bankB:
            time_bankB -= time_B[j]
            num_books += 1
        else:
            change_point_B = time_bankB + 1  # Bで読める本が１冊へる時間
            break

    max_books = max(max_books, num_books)
    change_point = min(change_point_A, change_point_B)
    allot_to_A += change_point
    allot_to_B -= change_point
    if allot_to_A < 0 or allot_to_B < 0:
        break

print(max_books)


### FIXED CODE ###

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

A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)
### BUGGY CODE ###

k,s=map(int,input().split(" "))
c=0
for i in range(k+1):
  for j in range(k+1):
    for l in range(k+1):
      if i+j+l==s:
        c+=1
      if i+j+l>s:
        break
print(c)

### FIXED CODE ###

k,s=map(int,input().split(" "))
c=0
for i in range(k+1):
  for j in range(k+1):
    if s-i-j<=k and s-i-j>=0:
      c+=1

print(c)
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(max(dp[n]))

### FIXED CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(max(dp[n]))
### BUGGY CODE ###

from collections import defaultdict
from collections import deque

s=input()
n=len(s)
dd = defaultdict(int)
q = deque()
if n<4:
    print(0)
    exit()
ans=0
for i in range(4):
    q.append(s[i])
if(int(''.join(q))%2019)==0:
    ans+=1

for i in range(0, n-3):
    for j in range(5, n+1, 3):
        if i+j<n+1:
            dd[(i,i+j)]+=1
            if(int(s[i:i+j])%2019==0) and dd[(i,i+j)]==1:
                ans+=1
                i=i+j
                break
            if j>n-4:
                for k in range(3):
                    if i+j+k<n:
                        dd[(i,i+j+k)]+=1
                        if int(s[i:i+j+k])%2019==0 and dd[(i,i+j+k)]==1:
                            ans+=1

print(ans)


### FIXED CODE ###

from collections import defaultdict
dd = defaultdict(int)
S = list(input().rstrip())
tmp = 0
dd[0]+=1
r=1
for s in S[::-1]:
    tmp+=int(s)*r
    r*=10

    tmp%=2019
    r%=2019
    dd[tmp]+=1
su=0
for i in dd.values():
    su+=(i*(i-1))//2
print(su)
### BUGGY CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
bs = b
cs = c
 
x = 0
 
f = range(a[0])
g = range(a[1])
 
for i in range(a[0]):
    for ii in range(i,a[0]):
        for j in range(a[1]):
            for jj in range(j,a[1]):
                x = x + ((bs[ii] - bs[i]) * (cs[jj] - cs[j]))
                if x > (10**9 + 7):
                    x = x % (10**9 + 7)
 
ans = x
 
print(ans)

### FIXED CODE ###

a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))

x = 0
y = 0

for i in range(1,a[0]):
    x = x + b[i] - b[0]
    
xx = x
for i in range(1,a[0]-1):
    xx = xx - ((b[i] - b[i - 1]) * (a[0] - i))
    x = x + xx

for i in range(1,a[1]):
    y = y + c[i] - c[0]
    
yy = y
for i in range(1,a[1]-1):
    yy = yy - ((c[i] - c[i - 1]) * (a[1] - i))
    y = y + yy

ans = x * y
ans = ans % (10**9 + 7)

print(ans)
### BUGGY CODE ###

mod = 10**9+7
S = list(input())
Q=0
DP=[]
#DP[x][y] x+1文字目までを見たときの、
#y=0,1,2 : A,AB,ABCの登場回数
if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Q=1
else:
    DP.append([0,0,0])
for i,s in enumerate(S):
    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+3**Q)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(3**Q+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Q+=1
print(DP[len(S)-1][2]%mod)

### FIXED CODE ###

mod = 10**9+7
S = list(input())
Thankyou = 1
DP=[]
#DP[x][y] x+1文字目までを見たときの、
#y=0,1,2 : A,AB,ABCの登場回数
if S[0] == "A" or S[0]=="?":
    DP.append([1,0,0])
    if S[0]=="?":
        Thankyou = 3
else:
    DP.append([0,0,0])
for i,s in enumerate(S):

    if i==0:continue
    a,b,c = DP[i-1]
    if s=="A":
        DP.append([(a+Thankyou)%mod,b,c])
    elif s=="B":
        DP.append([a,(a+b)%mod,c])
    elif s=="C":
        DP.append([a,b,(b+c)%mod])
    else:
        DP.append([(Thankyou+3*a)%mod,(a+3*b)%mod,(b+3*c)%mod])
        Thankyou *= 3
        Thankyou %= mod
print(DP[len(S)-1][2]%mod)
### BUGGY CODE ###

N = int(input())
print(sum(range(N)))

### FIXED CODE ###

N = int(input())

print((0+N-1)*(N)//2)
### BUGGY CODE ###

n=int(input())
comb=[]
ans=[]


for k in range(1, n+1):
    flag=False
    for x in range(1, 80):
        if 6*x**2 > k:
            break
        else:
            for y in range(x, 80):
                for z in range(y, 80):
                    if (x+y+z)**2 - x*y-y*z-z*x==k:
                        comb.append((x,y,z))
                        flag=True
                        break
    
    if flag:
        pass
    else:
        comb.append((0, 0, 0))


for s in range(n):
    if comb[s][0]==comb[s][1]==comb[s][2]==0:
        ans.append(0)
    elif comb[s][0]==comb[s][1]==comb[s][2]!=0:
        ans.append(1)
    elif comb[s][0]!=comb[s][1] and comb[s][1]!=comb[s][2] and comb[s][2]!=comb[s][0]:
        ans.append(6)
    else:
        ans.append(3)

for i in range(n):
    print(ans[i])

### FIXED CODE ###

n=int(input())
cnt=[0]*(n+1)

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp=x*x + y*y + z*z + x*y + y*z + z*x
            if tmp <=n:
                cnt[tmp]+=1


for i in range(1, n+1):
    print(cnt[i])
### BUGGY CODE ###

# coding: utf-8

def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = tuple(map(int, args[1].split()))

    l, r = 1, max(A)
    while 1e-3 < r-l:
        m = (l+r)/2
        cnt = 0
        for a in A:
            cnt += -int(-a//m)-1

        if k < cnt:
            l = m
        else:
            r = m

    return str(-int(-l//1))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8

def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = tuple(map(int, args[1].split()))

    l, r = 1, max(A)
    while 0.1 < r-l:
        m = (l+r)/2
        cnt = 0
        for a in A:
            cnt += -int(-a//m)-1

        if k < cnt:
            l = m
        else:
            r = m

    return str(-int(-l//1))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    D = [[*map(int, input().split())] for _ in [None] * K]
    D = {(r - 1, c - 1) : v for r, c, v in D}

    dp = [[[-1] * 4 for _ in [None] * C] for _ in [None] * R]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = D.get((r, c), None)
            for i in range(4):
                if dp[r][c][i] > -1:
                    if r < R - 1:
                        dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i])
                    if c < C - 1:
                        dp[r][c + 1][i] = max(dp[r][c + 1][i], dp[r][c][i])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i] + v)
                        if c < C - 1:
                            dp[r][c + 1][i + 1] = max(dp[r][c + 1][i + 1], dp[r][c][i] + v)

    v = D.get((R - 1, C - 1), 0)
    ans = dp[R - 1][C - 1][3]
    for i in range(3):
        ans = max(ans, dp[R - 1][C - 1][i] + v)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = map(int, input().split())
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    DP[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(" ")))

    total = 0
    c_list = []
    a_count_list = []
    for i in range(n):
        count = a.count(i + 1)
        a_count_list.append(count)
        # print(count)
        if count > 1: # 2個以上
            # c = combinations_count(count, 2)
            c = count * (count - 1) // 2
        else:
            c = 0

        c_list.append(c)
        total = total + c

    # print(a, c_list, total, a_count_list)
    for k in range(n):
        if c_list[a[k] - 1] == 1:
            q = 1
        elif c_list[a[k] - 1] == 0:
            q = 0
        else:
            # q = c_list[a[k] - 1] - 1
            q = c_list[a[k] - 1] - c_list[a[k] - 1] * (a_count_list[a[k] - 1] - 2) // a_count_list[a[k] - 1]
        print(total - q)

### FIXED CODE ###

from collections import defaultdict

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split(" ")))

    variation = set(a)
    a_count_dict = defaultdict(int)
    for j in a:
        a_count_dict[j] += 1

    total = 0
    c_dict = {}
    for i in variation:
        count = a_count_dict[i]
        if count > 1: # 2個以上
            # c = combinations_count(count, 2)
            c = count * (count - 1) // 2
        else:
            c = 0
        c_dict[i] = c
        total = total + c

    # total = 0
    # c_list = []
    # a_count_list = []
    # for i in range(n):
    #     count = a.count(i + 1)
    #     a_count_list.append(count)
    #     # print(count)
    #     if count > 1: # 2個以上
    #         # c = combinations_count(count, 2)
    #         c = count * (count - 1) // 2
    #     else:
    #         c = 0
    #
    #     c_list.append(c)
    #     total = total + c

    # print(a, c_list, total, a_count_list)
    for k in range(n):
        ck = c_dict[a[k]]
        ca = a_count_dict[a[k]]
        if ck == 1 or ck == 0:
            q = ck
        else:
            # q = c_list[a[k] - 1] - 1
            q = ck - ck * (ca - 2) // ca


        # if c_list[a[k] - 1] == 1:
        #     q = 1
        # elif c_list[a[k] - 1] == 0:
        #     q = 0
        # else:
        #     # q = c_list[a[k] - 1] - 1
        #     q = c_list[a[k] - 1] - c_list[a[k] - 1] * (a_count_list[a[k] - 1] - 2) // a_count_list[a[k] - 1]
        print(total - q)
### BUGGY CODE ###


def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        l,r = map(int,input().split())
        for i in range (l,r+1):
            S.append(i)

    S.sort()

    ans = [0]*N
    ans[0] = 1

    for i in range (1,N):
        for j in S:
            if i-j < 0:
                break
            else:
                ans[i] += ans[i-j]
                ans[i] %= mod


    print(ans[N-1])


main()


### FIXED CODE ###

def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        S.append(list(map(int,input().split())))

    S.sort()
    #print(S)

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

        ans[i] %= mod
        acc[i] = (acc[i-1]+ans[i])%mod


    print(ans[N-1])


main()
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N 
for i,hi in enumerate(h):
  if i==0:continue;
  dp[i] += min(dp[j] + abs(hi-h[j]) for j in range(max(i-K,0),i)) 
print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]+[None]*(N-1) 
def func(N,K,h,dp):
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(i-K,0),i)) 

func(N,K,h,dp)
print(dp[-1])
### BUGGY CODE ###

import sys
import  math
import fractions
from collections import defaultdict
import copy
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

K=int(input())
mod_l=[0]*(K*10)
mod_l[0]=7%K
mod_k=7%K
ans=1
for i in range(10*K-1):
    if(mod_l[i]==0):
        print(ans)
        sys.exit(0)
    mod_k=(mod_k*10)%K  
    if(mod_k==0):
        print("-1")
        sys.exit(0)
    mod_l[i+1]=(mod_l[i]+mod_k)%K
    ans+=1

print("-1")


### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
import copy
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

K=int(input())
mod_l=[0]*(K*10)
mod_l[0]=7%K
mod_k=7%K
ans=1
for i in range(10*K-1):
    if(mod_l[i]==0):
        print(ans)
        sys.exit(0)
    mod_k=(mod_k*10)%K  
    if(mod_k==0):
        print("-1")
        sys.exit(0)
    mod_l[i+1]=(mod_l[i]+mod_k)%K
    ans+=1

print("-1")