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

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2)
    for l, r in lrl:
        add(l+i+1, r+i+2, now)

print(query(n, n+1) % 998244353)


### FIXED CODE ###

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)
### BUGGY CODE ###

import itertools

def one_hot(n):
    temp_0=[0]
    temp_1=[1]
    ret=[]
    S=[temp_0,temp_1]
    v=S.pop()
    while len(ret)!=2**n:
        if len(v)==n:
            ret.append(v)
            if len(S)!=0:
                v = S.pop()
        else:
            S.append(v+[0])
            S.append(v+[1])
            v=S.pop()
    return ret

if __name__ == '__main__':
    n=int(input())
    string=input()
    string=list(string)
    div=10**9+7
    count=0
    iteration=one_hot(n)
    for i in iteration:
        temp=[]
        for s,j in zip(string,i):
            if j==1:
                temp.append(s)
        if len(temp)!=0 and len(temp)==len(set(temp)):
            count+=1
    print(count%div)


### FIXED CODE ###

if __name__ == '__main__':
    n=int(input())
    string=input()
    string_set=set(string)
    div=10**9+7
    count=1
    for s in string_set:
        count*=string.count(s)+1
    count-=1
    print(count%div)
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a_cnt = Counter(a)

a = sorted(list(set(a)))
n = len(a)
def divisor(n):
    res = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            res.append(i)

            if i != n // i and i != 1:
                res.append(n // i)
    return res

divs = [set(divisor(a[i])) for i in range(n)]

ans = 0
memo = set()
for i in range(n):
    if a_cnt[a[i]] == 1:
        if memo & divs[i] == set():
            ans += 1

    memo.add(a[i])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for x in set(a):
    if flg[x]:
        ans += 1

    tmp = 1
    while tmp * x <= 10 ** 6:
        flg[tmp * x] = False
        tmp += 1

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

A,B,N = map(int,input().split())
x = 0
a = 0
while x<=N:
  if a < A*x//B - A*(x//B):
    a = A*x//B - A*(x//B)
    x += 1
  else:
    x += 1
print(a)

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(N, B-1)
a = A*x//B - A*(x//B)
print(a)
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

N,X,Y=map(int,input().split())

G=[[] for i in range(N)]
num=[0]*(N-1)

for i in range(N-1):
    G[i].append(i+1)
    G[i+1].append(i)

G[X-1].append(Y-1)
G[Y-1].append(X-1)

from collections import deque
from copy import deepcopy
def BFS(a,b):
    d=deque([])
    d.append([a,[0]*N])
    while d:
        x,c=d.popleft()
        chk=deepcopy(c)
        chk[x]=1
        for i in G[x]:
            if chk[i]==1:continue
            if i==b:
                ans=chk.count(1)
                return ans
            else:
                d.append([i,chk])

for i in range(N-1):
    for j in range(i+1,N):
        n=BFS(i,j)
        num[n-1]+=1

for a in num:
    print(a)








### FIXED CODE ###

N,X,Y=map(int,input().split())

G=[[i+1] for i in range(N)]
G[N-1].pop()
for i in range(1,N):
    G[i].append(i-1)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

from collections import deque

q=deque([])
cnt=[0]*N

for n in range(N-1):
    seen=[0]*N
    q.append([n,0])
    seen[n]=1
    while q:
        x,c=q.popleft()
        if c>=N-1:continue
        for g in G[x]:
            if seen[g]==0:
                q.append([g,c+1])
                seen[g]=1
                if n<g:
                    cnt[c+1]+=1
for i in range(1,N):
    print(cnt[i])
### BUGGY CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
li=[]
idx_li=[1]
flag=False
for i in range(k):
    idx=a[idx-1]
    if idx in idx_li:
        flag=True
        break
    idx_li.append(idx)
if flag:
    #non_loop=idx_li[:idx_li.index(idx)]
    loop = idx_li[idx_li.index(idx):]
    
    size=len(loop)
    print(loop[(k-(len(idx_li)-len(loop)))%size])
else:
    print(idx)

### FIXED CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
idx_li=[]
ord_=[-1]*n
flag=False
for i in range(k):
    idx_li.append(idx)
    ord_[idx-1]=1
    idx=a[idx-1]
    if ord_[idx-1]==1:
        flag=True
        break
if flag:
    #non_loop=idx_li[:idx_li.index(idx)]
    loop = idx_li[idx_li.index(idx):]
    
    size=len(loop)
    print(loop[(k-(len(idx_li)-len(loop)))%size])
else:
    print(idx)
### BUGGY CODE ###

R, G,B,N = map(int, input().split())
l=[R, G, B]

l.reverse()
r_max=N//l[0]
g_max=N//l[1]
RR=l[0]
GG=l[1]
BB=l[2]
ans=0
for r in range(r_max+1):
    res=N-r*RR
    for g in range(g_max+1):
        x=res-GG*g
        if x>=0 and x%BB==0:
            ans+=1
            
print(ans)

### FIXED CODE ###

R, G,B,N = map(int, input().split())
l=[R, G, B]

l.reverse()
r_max=N//l[0]
g_max=N//l[1]
RR=l[0]
GG=l[1]
BB=l[2]
ans=0
for r in range(r_max+1):
    res=N-r*RR
    for g in range(g_max+1):
        x=res-GG*g
        if x<0:
            break
        if x%BB==0:
            ans+=1
            
print(ans)
### BUGGY CODE ###

N = int(input())

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

res = A[0]



for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1

if 0 in A:
    res = 0

print(res)

### FIXED CODE ###

N = int(input())

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

res = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1
        break



print(res)
### BUGGY CODE ###

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    g = a[0]
    MOD = 10**9+7
    for t in a:
        #g = g*a[i]//fractions.gcd(g,a[i])
        g = divmod(g*t,fractions.gcd(g,t))[0]
    res = 0
    for t in a:
        res += divmod(g,t)[0]%MOD
    print(res%MOD)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

n = int(input())
A = [int(x) for x in input().split()]
B = [0] * n

for i in reversed(range(n)):
    if i + 1 > n // 2:
        B[i] = A[i]
        # iの倍数が書かれた箱に入っているボールの個数はOK
    else:
        # iの倍数が書かれた箱に入っているボールの個数
        c = n // (i+1)
        s = 0
        for j in range(c):
            s += B[(i+1)*(j+1)-1]
        if s % 2 == A[i]:
            continue
        else:
            B[i] = 1

print(sum(B))
for i in range(len(B)):
    if B[i] == 1:
        if sum(B[i:]) > 1:
            print(i + 1, end=' ')
        else:
            print(i + 1)



### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]
B = [0] * n

for i in reversed(range(n)):
    if i + 1 > n // 2:
        B[i] = A[i]
        # iの倍数が書かれた箱に入っているボールの個数はOK
    else:
        # iの倍数が書かれた箱に入っているボールの個数
        c = n // (i+1)
        s = 0
        for j in range(c):
            s += B[(i+1)*(j+1)-1]
        if s % 2 == A[i]:
            continue
        else:
            B[i] = 1

ans = sum(B)
print(ans)
count = 0
for i in range(len(B)):
    if B[i] == 1:
        count += 1
        if count == sum:
            print(i + 1)
        else:
            print(i + 1, end=' ')
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
ans=0

for i in range(N//R+1):
    for j in range(N//G+1):
        
        if N>=i*R+j*G and (N-(i*R+j*G))%B==0:
            ans+=1

print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
ans=0

for i in range(N//R+1):
    for j in range(N//G+1):
        
        if N>=i*R+j*G and (N-(i*R+j*G))%B==0:
            ans+=1

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

import sys
from collections import Counter
import random
import numpy as np

n=int(input())
x=np.array(list(map(int,input().split())))
for i in range(n):
    y=np.delete(x,i)
    print(int(np.median(y)))

### FIXED CODE ###

import sys
from collections import Counter
import random
import numpy as np

n=int(input())
x=np.array(list(map(int,input().split())))
z=sorted(x)
cand=[z[n//2-1],z[n//2]]
#print(int(np.median(x)))
dic={}
for i in range(n):
    a=x[i]
    if(a<=cand[0]):print(cand[1])
    else:print(cand[0])
### BUGGY CODE ###

# coding: utf-8
K, S = map(int, input().split())
counter = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                counter += 1   

print(counter)

### FIXED CODE ###

# coding: utf-8
K, S = map(int, input().split())
ans = 0;

for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >= 0 and z <= K:
            ans += 1

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

import bisect
N,M,Q=map(int,input().split())
Rli=[[] for _ in range(N)]
for i in range(M):
  l,r=map(int,input().split())
  Rli[l-1].append(r)
for i in range(N):
  Rli[i].sort()
  
for i in range(Q):
  ans=0
  p,q=map(int,input().split())
  for j in range(p-1,N):
    ans+=bisect.bisect_right(Rli[j],q)
  print(ans)

### FIXED CODE ###

import bisect
N,M,Q=map(int,input().split())
LR=[[0]*(N+1) for _ in range(N)]
for i in range(M):
  l,r=map(int,input().split())
  LR[l-1][r]+=1
for i in range(N):
  for j in range(1,N+1):
    LR[i][j]+=LR[i][j-1]
  
for _ in range(Q):
  ans=0
  p,q=map(int,input().split())
  for i in range(p-1,q):
    ans+=LR[i][q]-LR[i][p-1]
  print(ans)
### BUGGY CODE ###

n, q = list(map(int,input().split()))
s = input()
l = []
for i in range(q) :
    l.append(list(map(int,input().split())))
def f(l,r) :
    global s
    count = 0
    for i in range(l,r) :
        if s[i - 1] == "A" and s[i] == "C" :
            count += 1
    print(count)
for l,r in l :
    f(l,r)

### FIXED CODE ###

n,q= map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]
sa = [0]*n
for i in range(0,len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        sa[i+1] = sa[i] + 1
    else:
        sa[i+1] = sa[i]

""" A C D D D A C A C """
"""0 1 1 1 1 1 2 2 3  """
for si, syu in l:
    print(sa[syu-1] - sa[si-1])
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


def gcd_3(x, y, z):
    return gcd(gcd(x, y), z)

K = inp()

dic = {} # key: (i, j, k), el: gcd(i, j, k)
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            std = tuple(sorted([i, j, k]))
            if std in dic:
                ans += dic[std]
            else:
                a = gcd_3(i, j, k)
                dic[std] = a
                ans += a
print(ans)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


def gcd_3(x, y, z):
    return gcd(gcd(x, y), z)

K = inp()

dic = {} # key: (i, j, k), el: gcd(i, j, k)
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        tmp = gcd(i, j)
        for k in range(j, K + 1):
            a = gcd(tmp, k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)
### BUGGY CODE ###

def resolve():
    n, k = list(map(int, input().split()))
    xxx = list(map(int, input().split()))
    ans = float("inf")
    for i in range(n-k+1):
        lll = xxx[i:i+k]
        if not lll[0] <= 0 <= lll[-1]:
            ans = min(ans, max(abs(lll[0]), abs(lll[-1])))
        else:
            ans = min(ans, min(abs(lll[0]), abs(lll[-1]))+abs(lll[-1]-lll[0]))
    print(ans)
resolve()

### FIXED CODE ###


def resolve():
    n, k = list(map(int, input().split()))
    xxx = list(map(int, input().split()))
    ans = float("inf")
    for i in range(n-k+1):
        max_l = xxx[i+k-1]
        min_l = xxx[i]
        if not min_l <= 0 <= max_l:
            ans = min(ans, max(abs(min_l), abs(max_l)))
        else:
            ans = min(ans, min(abs(min_l), abs(max_l))+abs(max_l-min_l))
    print(ans)
resolve()
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += int(i*(i-1)/2)
for k in range(N):
    print(S - A.count(A[k]) + 1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w = map(int,input().split())
c = []
for i in range(h):
  a = input()
  c.append(a)
  
from collections import deque

def bfs(sh,sw):
    d = [[False] * w for i in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sh,sw,0))
    d[sh][sw] = True
    chk = False
    while que:
        p = que.popleft()
        if c[p[0]][p[1]] == '#':
            a = p[2]
            break
        for i in range(4):
            nw = p[1] + dx[i]
            nh = p[0] + dy[i]
            
            if 0 <= nw < w and 0 <= nh < h and c[nh][nw] == '#':
                chk = True
                a = p[2] + 1
            elif 0 <= nw < w and 0 <= nh < h and d[nh][nw] == False:
                que.append((nh,nw,p[2]+1))
                d[nh][nw] = True
        if chk:
          break
    return a
  
ans = 0
for i in range(h):
  for j in range(w):
    res = bfs(i,j)
    ans = max(ans,res)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w = map(int,input().split())
c = []
for i in range(h):
  a = input()
  c.append(a)
  
from collections import deque

d = [[-1] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque([])
for i in range(h):
  for j in range(w):
    if c[i][j] == '#':
      que.append((i,j,0))
      d[i][j] = 0

ans = 0
while que:
  p = que.popleft()
  for i in range(4):
      nw = p[1] + dx[i]
      nh = p[0] + dy[i]
      if 0 <= nw < w and 0 <= nh < h and d[nh][nw]==-1:
          que.append((nh,nw,p[2]+1))
          d[nh][nw] = p[2]+1
          ans = max(ans,p[2]+1)

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

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
#answer = [-1] * N
#p = [0] * N
for i in range(N):
  count[i]  = A.count(i + 1)
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  #if answer[A[i] - 1] != -1:
    #p[i] = answer[A[i] - 1]
    #print(answer[A[i] - 1])
  #else:
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
    #p[i] = s
  print(s)
  #answer[A[i] - 1] = s
#for i in p:
  #print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)
### BUGGY CODE ###

N,C,K = map(int,input().split())
T = []
for i in range(N):
  T.append(int(input()))

T.sort()
counter = 0
while len(T) > 0:
  if len(T) == 1:
    T.pop()
    counter += 1
  else:
    c = 1
    while c <= len(T)-1:
      if T[c] - T[0] <= K:
        c += 1
      else:
        break
  
    del T[:min(c,C)]
    counter += 1

print(counter)

### FIXED CODE ###

N,C,K = map(int,input().split())
T = []
for i in range(N):
  T.append(int(input()))

T.sort()
counter = 0
while len(T) > 0:
  if len(T) == 1:
    T.pop()
    counter += 1
  else:
    c = 1
    while c <= len(T)-1 and c < C:
      if T[c] - T[0] <= K:
        c += 1
      else:
        break
  
    del T[:c]
    counter += 1

print(counter)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
from sys import stdin

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

lcm_A = reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))

### FIXED CODE ###

import fractions
import functools
import sys

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))

count_list = []
for a in A_list:
    count = 0
    for i in range(N):
        if a == A_list[i]:
            count += 1
    count_list.append(count)

if max(count_list) == 1:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_set = set(A_list)

if len(A_list) == len(A_set):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N=int(input())
A = [list(map(int, input().split())) for _ in range(N)]

inf=float('inf')
dp=[[-inf]*3 for j in range(N+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    for i in range(3):
        if (m == i):
            continue
        dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)

### FIXED CODE ###

#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N=int(input())
A = [list(map(int, input().split())) for _ in range(N)]

inf=float('inf')
dp=[[0]*3 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    if dp[n][m]>0:
        return dp[n][m]

    for i in range(3):
            if (i == m):
                continue
            dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)
### BUGGY CODE ###

N = int(input())
S = []
C = []
for i in range(N):
  s = input()
  if s in S:
    C[S.index(s)] += 1
  else:
    S.append(s)
    C.append(1)
M = max(C)
l = len(C)
A = [S[j] for j in range(l) if C[j] == M]
A.sort()
[print(k) for k in A]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

n, m = map(int, input().split())
if abs(n-m) > 1:
	print(0)
	exit()
i = n
np = 1
while True:
	np = np * i
	i -= 1
	if i == 1:
		break
i = m
mp = 1
while True:
	mp = mp * i
	i -= 1
	if i == 1:
		break
s = 2 if n == m else 1
r = (mp*np*s) % (10**9 + 7)
print(r)

### FIXED CODE ###

import math

n, m = map(int, input().split())
if abs(n-m) > 1:
	print(0)
	exit()
s = 2 if n == m else 1
np = math.factorial(n)
mp = math.factorial(m)
r = (mp*np*s) % (10**9 + 7)
print(r)
### BUGGY CODE ###

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

D = [1]
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % 998244353)
print(D[-1])

### FIXED CODE ###

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

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])