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

from sys import exit
# import copy
# import numpy as np
from collections import deque

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

cnt = 0

a_sum = deque([0])
b_sum = deque([0])
atmp = 0
btmp = 0

for i in a:
    atmp += i
    a_sum.append(atmp)

for i in b:
    btmp += i
    b_sum.append(btmp)


for i in range(n+1):
    for j in range(m+1):
        if a_sum[i] + b_sum[j] <= k:
            cnt = max(cnt, i + j)
        else:
            break

print(cnt)


### FIXED CODE ###

from sys import exit
import copy
# import numpy as np
from collections import deque

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

cnt = 0


a.insert(0, 0)
b.insert(0, 0)


for i in range(1, n+1):
    a[i] += a[i-1]

for i in range(1, m+1):
    b[i] += b[i-1]

tmp = m
for i in range(n+1):
    for j in range(tmp, -1, -1):
        if a[i] + b[j] <= k:
            cnt = max(cnt, i + j)
            tmp = j
            break


print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy

def main():
	num = int(input())
	
	clocks = []
	for _ in range(num):
		clock = int(input())
		clocks.append(clock)
		
	times = copy.deepcopy(clocks)
	while True:
		flg = True
		max_num = max(times)
		for i, time in enumerate(times):
			if max_num == time : continue
			
			tmp = max_num // time
			times[i] = times[i] * tmp
			if max_num != times[i]:
				flg = False
			
		if flg:
			print(times[0])
			sys.exit()
		else:
			p = times.index(max_num)
			times[p] = times[p] + clocks[p]
			max_num = times[p]
			
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy

def main():
	num = int(input())
	
	clocks = []
	for _ in range(num):
		clock = int(input())
		clocks.append(clock)
		
	ans = 1
	for clock in clocks:
		ans = lcm(ans, clock)
	print(ans)
			
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
def lcm(a, b):
	g = gcd(a, b)
	return a // g * b
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
rc.reverse()
rq.reverse()

for i in range(len(s)):
    if s[i]=='A' or s[i]=='?':
        if s[i]=='?':
            qq = q-1
        else:
            qq = q
        for j in range(i+1,len(s)):
            if s[j]=='B' or s[j]=='?':
                if s[j] == '?':
                    qqq = qq-1
                else:
                    qqq = qq
                ans += rc[j]*(3**qqq)
                if qq>0:
                    ans += rq[j]*(3**(qqq-1))
                ans %= 10**9+7

print(int(ans))


### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

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

if n % 2 == 0:
    for i in range(n//2):
        if a.count(2*i + 1) != 2:
            print(0)
            exit()
else:
    if a.count(0) != 1:
        print(0)
        exit()
    for i in range(1,n//2+1):
        if a.count(2*i) != 2:
            print(0)
            exit()
    
print(2**(n//2) % (10**9+7))

### FIXED CODE ###

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

if n % 2 == 0:
    for i in range(n//2):
        d += (2*i + 1) * 2
    if d != sum(a):
        print(0)
        exit()
else:    
    for i in range(1, n//2+1):
        d += 4 * i
    if d != sum(a):
        print(0)
        exit()

print(2**(n//2) % (10**9+7))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            a[j]=sum(num[:j+1])
        if sum(a)==n*n:
            break
    print(*a)


### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)
### BUGGY CODE ###

N=int(input())
src=list(map(int,input().split()))
L=[i+a for i,a in enumerate(src,1)]
R=[i-a for i,a in enumerate(src,1)]
ans=0
for l in L:
  for n in range(N):
    if R[n] == l:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N=int(input())
src=list(map(int,input().split()))
ans=0
d=defaultdict(int)
e=[]
for i,s in enumerate(src,1):
  l=i+s
  r=i-s
  d[l]+=1
  ans+=d[r]

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

S = list(input())

Q = int(input())


for i in range(Q):
    s = list(input().split())
    if len(s) == 1:
        S = S[::-1]
    else:
        if s[1] == '1':
            S.insert(0,s[2])
        else:
            S.append(s[2])

print('%s' % ''.join(S))



### FIXED CODE ###

Sr = list(input())
Sl = []
Q = int(input())


for i in range(Q):
    s = list(input().split())
    if len(s) == 1:
        Sr,Sl = Sl,Sr
    elif s[1] == '1':
        Sl.append(s[2])
    else:
        Sr.append(s[2])
Sl.reverse()
print('%s' % (''.join(Sl) + ''.join(Sr)))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-



import sys
############
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    X = int(input())
    divs = make_divisors(X)
    for d in divs:
        tm = X-pow(d,5)
        if tm%10!=0:
            continue
        divss = make_divisors(abs(tm)//(5*d))
        divss += [0]
        for b in divss:
            Y=pow(b+d,5)-pow(b,5)
            Y_=pow(-b+d,5)-pow(-b,5)
            if Y==X:
                print(b+d,b)
                sys.exit()
            elif Y_==X:
                print(-b+d,-b)
                sys.exit()

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

def main():
    X = int(input())
    for a in range(-200, 200):
        a5 = pow(a,5)
        for b in range(-200, 200):
            b5 = pow(b,5)
            if a5-b5 == X:
                print(a,b)
                sys.exit()

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

from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0

    def __init__(self, size):
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self._offset + 1)


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

st = SegmentTree(N)
for i in range(N):
    st.update(i, A[i])

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, gcd(st.query(0, i), st.query(0, N - 1)))
print(result)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
c1 = [0] * (n + 1)
c2 = [0] * (n + 1)
# c1[1] = a[0]
# c2[n - 1] = a[n - 1]
for i in range(1, n + 1):
  c1[i] = gcd(c1[i - 1], a[i - 1])
  c2[n - i] = gcd(c2[n - i + 1], a[n - i])
print(max(gcd(c1[i], c2[i + 1]) for i in range(n)))
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10**12
cost = [[INF] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m:
            cost[hh][ww] = m
            que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if 0 <= hh < h and 0 <= ww < w and s[hh][ww] == '.' and cost[hh][ww] > m + 1:
            cost[hh][ww] = m + 1
            que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
f = [int(x) for x in input().split()]
a.sort()
f.sort(reverse=True)
lx = 0
rx = 10 ** 12
for i in range(1000):
    if lx == rx:
        break
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        ta = a[j]
        y = (ta*f[j] - cx + f[j] -1) // f[j]
        kk += max(0, y)
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)

### FIXED CODE ###

n, k = map(int, input().split())
# a = [int(x) for x in input().split()]
# f = [int(x) for x in input().split()]
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
lx = -1
rx = a[-1] * f[0]
while rx-lx>1 :
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        kk += max(0, a[j] - cx//f[j])
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
x=[0]*n
for i in range(n):
  for j in range(n):
    if(j+1==a[i]):
      x[j]=i+1
  
print(" ".join(map(str,x)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=[0]*n
for i in range(n):
  x[a[i]-1]=i+1
  
print(" ".join(map(str,x)))
### BUGGY CODE ###

k,s=map(int,input().split())
a=0
for x in range(k+1):
  for y in range (k+1):
    for z in range (k+1):
      if x + y + z == s:
        a+=1
        break

print(a)


### FIXED CODE ###

k,s = map(int,input().split())
a=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=s-x-y<=k:
            a+=1
print(a)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      pos.append([i, j])
      A[i][j] = 1
      cnt += 1
ccnt = 0
pnt = 0
while pnt < cnt:
  n = cnt
  ccnt += 1
  for i in range(pnt, cnt):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
        cnt += 1
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
        cnt += 1
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
        cnt += 1
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
        cnt += 1
  pnt = n
print(ccnt-1)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      pos.append([i, j])
      A[i][j] = 1
cnt = 0
while pos != []:
  n = len(pos)
  cnt += 1
  for i in range(n):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
  pos = pos[n:]
print(cnt-1)
### BUGGY CODE ###

n =int(input())
A = list(map(int, input().split()))
 
s = A[0]
for i in range(1, n):
  s *=A[i]
 
if s <= 1000000000000000000:
  print(s)
elif s > 1000000000000000000:
  print(-1)

### FIXED CODE ###

def main():
  n =int(input())
  A = list(map(int, input().split()))

  if 0 in A:
    print(0)
    return

  p = 1
  for a in A:
    p *= a
    if p > 10 ** 18:
      print(-1)
      return

  print(p)
main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a = sorted(a)

import numpy as np
def getNearestValue(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]
  
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
  
ans = 0
for i in range(1,n):
    tmp0 = a[i] / 2
    tmp1 = getNearestValue(a[0:i], tmp0)
    tmp2 = cmb(a[i], tmp1)
    if tmp2 > ans:
        ans = tmp2
        ans1 = a[i]
        ans2 = tmp1
print(ans1, ans2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# kakomon toku
import math
import sys
import itertools
import numpy as np
 
n = int(input())
a = [int(i) for i in input().split()]
 
#print(a)
a = np.sort(a)
ai = a[n-1]
aj = a[0]
center = ai / 2
diff = ai
i=0
for m in a:
    if diff > abs(m - center) :
        aj = m
        diff = abs(aj - center)
    else:
        break
 
print(ai,aj)
### BUGGY CODE ###

n = int(input())
L =sorted([int(i) for i in input().split()],reverse=True)

# print(L)

count=0
for i in range(0, n,1):
  x=0
  for j in range(i+1,n,1):
    for k in range(j+1,n,1):
      if (L[j] + L[k] > L[i]):
        count +=1
      else:
        if j == k+1:
          x=1
        break
    if x==1:
      break
print(count)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

from collections import deque
import sys

N = int(input())

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

q = deque([])

q.append([b,[]])

dic = {}

while len(q) > 0:

    now = q.pop()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        if (i+1) == nb[i]:

            nex = nb.copy()
            nec = nc.copy()
            
            nec.append(nex[i])
            del nex[i]

            s = " ".join(map(str,nex))
            if s in dic:
                continue
            dic[s] = 1

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])

print (-1)

### FIXED CODE ###

from collections import deque
import sys

N = int(input())

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

q = deque([])

q.append([b,[]])

dic = {}

while len(q) > 0:

    now = q.pop()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        i = len(nb) - i - 1

        if (i+1) == nb[i]:

            nex = []
            nec = []
            for j in range(len(nb)):
                if j != i:
                    nex.append(nb[j])
            for j in range(len(nc)):
                nec.append(nc[j])
            
            nec.append(nb[i])
            

            s = " ".join(map(str,nex))
            if s in dic:
                continue
            dic[s] = 1

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])
            break

print (-1)
### BUGGY CODE ###

Q=int(input())

PN=[True]*(10**5+1)
PN[0]=False
PN[1]=False

for i in range(2,int(int(10**5)**0.5+1)):
    if PN[i]==True:
        cnt=2
        while i*cnt<10**5+1:
            PN[i*cnt]=False
            cnt+=1

chk=[-1]*(10**5+1)

def YN(n):
    if chk[n]==1:return True
    elif chk[n]==0:return False
    else:
        if PN[n]==True and PN[(n+1)//2]==True:
            chk[n]=1
            return True
        else:
            chk[n]=0
            return False

for i in range(Q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r+1,2):
        if YN(j):ans+=1
    print(ans)




### FIXED CODE ###

import bisect

def PN(N):
    for i in range(2,int(N**0.5)+1):
        if N%i==0:
            return False
    return True

N=[3]
for i in range(5,100001,2):
    if PN(i) and PN((i+1)//2):
        N.append(i)

Q=int(input())

for i in range(Q):
    l,r=map(int,input().split())
    ln1=bisect.bisect_left(N,l)
    ln2=bisect.bisect_right(N,l)
    rn1=bisect.bisect_left(N,r)
    rn2=bisect.bisect_right(N,r)
    if ln1==ln2 and rn1==rn2:
        print(rn1-ln1)
    elif ln1==ln2 or rn1==rn2:
        print(rn1-ln2+1)
    else:
        print(rn1-ln2+2)
### BUGGY CODE ###

n, m = map(int, input().split())
gate_cond = [[int(x) for x in input().split()] for _ in range(m)]
each_valid_keys = [[x for x in range(l[0],l[1]+1)] for l in gate_cond]
all_valid_key = each_valid_keys[0]
for keys in each_valid_keys[1:]:
    all_valid_key = list(set(all_valid_key) & set(keys))
print(len(all_valid_key))

### FIXED CODE ###

n, m = map(int, input().split())

gate_cond = [[int(x) for x in input().split()] for _ in range(m)]
max_under_th = max([l[0] for l in gate_cond])
min_upper_th = min([l[1] for l in gate_cond])
if min_upper_th - max_under_th >= 0:
    print(min_upper_th - max_under_th + 1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = list(map(lambda x: x - 1, a))

for i in range(n):
    print(a.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = list(map(lambda x: x - 1, a))

cnts = [0 for _ in range(n)]
for ai in a:
    cnts[ai] += 1

for cnt in cnts:
    print(cnt)
### BUGGY CODE ###

target = input()

while len(target)>=5:
    if target[-7:] == "dreamer":
        target = target[:-7]
    elif target[-6:] == "eraser":
        target = target[:-6]
    elif target[-5:]=="dream" or target[-5:]=="erase":
        target = target[:-5]
if len(target)==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

target = input()

while len(target)>=5:
    if target[-7:] == "dreamer":
        target = target[:-7]
    elif target[-6:] == "eraser":
        target = target[:-6]
    elif target[-5:]=="dream" or target[-5:]=="erase":
        target = target[:-5]
    else:
      break
if len(target)==0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
l, r = [], []
for i in range(N):
  L,R=map(int,input().split())
  l+= [L]
  r+= [R]
  
prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(i+1,10**5+1):
    if j%i==0: prime[j]=0
  
ans = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: ans+=[1]
    else: ans+=[0]
  else: ans+=[0]
ans2= [0]
for i in range(10**5):
  ans2+=[ans2[-1]+ans[i+1]]
for i in range(N): 
  print(ans2[r[i]]-ans2[l[i]-1])

### FIXED CODE ###

N = int(input())
l, r = [], []
for i in range(N):
  L,R=map(int,input().split())
  l+= [L]
  r+= [R]
  
prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(i+1,10**5+1):
    if j%i==0: prime[j]=0
  
ans = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: ans+=[1]
    else: ans+=[0]
  else: ans+=[0]
ans2= [0]
for i in range(10**5):
  ans2+=[ans2[-1]+ans[i+1]]
for i in range(N): 
  print(ans2[r[i]]-ans2[l[i]-1])
### BUGGY CODE ###

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

s = []

for i in range(1,n+1):
  s.append(t.index(i)+1)

print(*s)


### FIXED CODE ###

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

d = list(range(1,n+1)) 
s = []
count = 1

c = zip(t, d)

c = sorted(c)

t, d = zip(*c)




print(*d)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        if steps.size == 0:
            break
        if steps[-1] >= N:
            steps = steps[:-1]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps.sort()
steps = np.array(steps, np.int64)

print(main(N, steps))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))