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

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    b = LI()
    cnt = defaultdict(lambda : 0)
    for i in a:
        cnt[i] += 1
    for i in b:
        if not cnt[i]:
            continue
        cnt[i] += 1
    for i in cnt.values():
        if i > n:
            print("No")
            return
    r = n-2
    while 1:
        if r < 0:
          r += n
        update = False
        for l in range(n):
            if a[l] == b[l]:
                update = True
                b[l],b[r] = b[r],b[l]
                r -= 1
        if not update:
            break
    print("Yes")
    print(*b)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    b = LI()
    cnt = defaultdict(lambda : 0)
    for i in a:
        cnt[i] += 1
    for i in b:
        if not cnt[i]:
            continue
        cnt[i] += 1
    for i in cnt.values():
        if i > n:
            print("No")
            return
    r = n-1
    while 1:
        update = False
        for l in range(n):
            while r >= 0 and a[r] != b[r]:
                r -= 1
            if a[l] == b[l]:
                update = True
                b[l],b[r] = b[r],b[l]
                r -= 1
        if not update:
            break
    print("Yes")
    print(*b)
    return

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

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=1
for i in A:
  t=(t*i)//fractions.gcd(t,i)
ans=0
for i in A:
  ans+=t//i
  ans%=(10**9+7)
print(ans)

### FIXED CODE ###

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
print(ans%(10**9+7))
### BUGGY CODE ###

N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        if vmax > b:
            vmax = b
            for j in range(1, ha[b]):
                va[j] = b
        count += ha[b] - 1
    else:
        if hmax > b:
            hmax = b
            for j in range(1, va[b]):
                ha[j] = b
        count += va[b] - 1

print(black - count)


### FIXED CODE ###

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

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

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

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

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

    print(black)

main()
### BUGGY CODE ###

from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for index, i in enumerate(graph[v],1):
            if dist[i] != -1:
                continue
            if index==len(graph[v]):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                newdp = update(dp, A[i])
                dist[i] = len(newdp)-1
                d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

from numpy import zeros

R, C, K, *RCV = map(int, open(0).read().split())

V = zeros((R + 1, C + 1), int)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

dp = zeros((R + 1, C + 1, 4), int)
for i in range(1, R + 1):
    for j in range(1, C + 1):

        vij = V[i][j]

        for k in range(4):
            dp[i][j][k] = max(
                dp[i][j - 1][k],
                dp[i - 1][j][3]
            )
        for k in reversed(range(1, 4)):
            dp[i][j][k] = max(
                dp[i][j][k],
                vij + dp[i][j][k - 1]
            )

print(dp[R][C][3])

### FIXED CODE ###

from numpy import zeros, int64
from numba import njit

R, C, K, *RCV = map(int64, open(0).read().split())
V = zeros((R + 1, C + 1), int64)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

@njit
def main():
    dp = zeros((R + 1, C + 1, 4), int64)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

            for k in range(4):
                dp[i][j][k] = max(
                    dp[i][j - 1][k],
                    dp[i - 1][j][3]
                )
            for k in range(3, 0, -1):
                dp[i][j][k] = max(
                    dp[i][j][k],
                    vij + dp[i][j][k - 1]
                )

    print(dp[R][C][3])

main()
### BUGGY CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

edge2 = np.array(edge[0])
for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    continue
  edge2 = np.vstack([edge2,edge[i]])

x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))

### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0
#print(edge)
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))
### BUGGY CODE ###

from collections import Counter
N = input()
count=0
S=[0]
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S.append(int(X)*(10**(int(i+1)-1))+S[i])
  mod_val=(S[i+1] % 2019)
  mod_count.append(mod_val)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
for a in range(N):
    for b in range(a+1, N):
        Ll = L[b+1:N]
        la = L[a]
        lb = L[b]
        ab = la + lb
        sa = abs(la-lb)
        first = bisect.bisect_left(Ll, ab) -1 
        second = bisect.bisect_right(Ll, sa)
        count += first - second +1
print(count)




### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
total = []
for a in range(N-2):
    for b in range(a+1, N-1):
        la = L[a]
        lb = L[b]
        ab = la + lb
        sa = abs(la-lb)
        first = bisect.bisect_left(L, ab) -1 
        second = bisect.bisect_right(L, sa)
        if first > second and first >= b+1:
            count += first - max(second, b+1) +1
print(count)
### BUGGY CODE ###

# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    acc = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(M):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = acc[i][j] + 1
            acc[i + 1][j + 1] = (acc[i + 1][j] + acc[i][j + 1] - acc[i][j] + dp[i + 1][j + 1]) % MOD
    print(acc[N][M] + 1)  # ''の分


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]  # (i,j)で丁度終わる文字列数
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

    acc = [[0] * (M + 1) for _ in range(N + 1)]
    acc[0][0] = 0
    acc[0][1] = 0
    acc[1][0] = 0

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  # ("","")のケース

    print(ans)


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

S = list(input())

ans = 0
tot = [str(0)]

for i in range(len(S)-1):
  for j in range(i+3,len(S)):
    if int(''.join(tot)) % 2019 == 0 and int(''.join(tot)) >= 2019:
      ans += 1
    tot = [str(0)]
    for k in range(i,j+1):
      tot.append(S[k])
print(ans)

### FIXED CODE ###

S = input()
mod = [0] * 2019
mod[0] = 1 
d = 1
n = 0
for i in reversed(S):
  n += int(i) * d
  n %= 2019
  d *= 10
  d %= 2019
  mod[n % 2019] += 1
ans = 0
for j in range(2019):
  ans += mod[j] * (mod[j] - 1) // 2
print(ans)
### BUGGY CODE ###

S = input()

S = S.split()

L = int(S[0])
R = int(S[1])
min = 2 * (10**10)

for i in range(L, R, 1):
    for j in range(i+1, R+1, 1):
        mod = (i*j) % 2019
        if mod < min:
            min = mod
            if min == 0:
                break

print(min)


### FIXED CODE ###


S = input()

S = S.split()

L = int(S[0])
R = int(S[1])
min = 2 * (10**10)

flg = 0

for i in range(L, R, 1):
    if flg ==0:
        for j in range(i+1, R+1, 1):
            mod = (i*j) % 2019
            if mod < min:
                min = mod
                if min == 0:
                    flg = 1
                    break
    else:
        break

print(min)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
neighbor = [[] for i in range(N)]
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)
X = [0] * N
for _ in range(Q):
    p, x = inpl()
    X[p-1] += x
result = [0] * N
def dfs(node, x, parent):
    x += X[node]
    result[node] = x
    for c in neighbor[node]:
        if c == parent:
            continue
        else:
            dfs(c,x,node)

dfs(0, 0, None)
print(' '.join(map(str,result)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
neighbor = [[] for i in range(N)]
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)
X = [0] * N
for _ in range(Q):
    p, x = inpl()
    X[p-1] += x

result = [0] * N
result[0] = X[0]
visited = [False] * N
dfs_stack = [0]
x = 0
while dfs_stack:
    node = dfs_stack.pop()
    visited[node] = True
    for c in neighbor[node]:
        if visited[c]:
            continue
        else:
            dfs_stack.append(c)
            result[c] = result[node] + X[c]

print(' '.join(map(str,result)))
### BUGGY CODE ###

def apc001_c():
    import sys
    n = int(input())

    lower = 0
    print(lower)
    sys.stdout.flush()
    seat_low = str(input())
    if seat_low == 'Vacant': return

    upper = n-1
    print(upper)
    sys.stdout.flush()
    seat_up = str(input())
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        print(x)
        sys.stdout.flush()
        s = str(input())
        if s == seat_low: lower = x
        elif s == seat_up: upper = x
        else: return

if __name__ == '__main__':
    apc001_c()
    exit(0)

### FIXED CODE ###

def apc001_c():
    import sys
    n = int(input())

    def ask(x:int):
        print(x)
        sys.stdout.flush()
        res = str(input())
        return res

    lower = 0
    seat_low = ask(lower)
    if seat_low == 'Vacant': return

    upper = n-1
    seat_up = ask(upper)
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        s = ask(x)
        if s == 'Vacant': return
        if x % 2 == 0:
            if s == seat_low: lower = x
            else: upper = x
        else:
            if s == seat_up: lower = x
            else: upper = x

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

def checkRGB(a,b,c):
    if a == b or b == c or c == a:
        return False
    else:
        return True

N = int(input())
S = input()

if N<4:
    print(0)
    exit()
sum = S.count("R")*S.count("G")*S.count("B")
for i in range(1,N):
    center = S[i]
    for j in range(i):
        left = S[j]
        if 2*i-j<N:
            right = S[2*i-j]
            if checkRGB(left,center,right):
                sum -= 1

print(sum)


### FIXED CODE ###

def checkRGB(a,b,c):
    if a == b or b == c or c == a:
        return 0
    else:
        return 1

N = int(input())
S = input()

if N<4:
    print(0)
    exit()
sum1 = S.count("R")*S.count("G")*S.count("B")
sum2 = 0
for i in range(0,N-2):
    left = S[i]
    for j in range(i+1,(N+i)//2+(N+i)%2):
        center = S[j]
        right = S[2*j-i]
        if checkRGB(left,center,right):
            sum2 += 1
print(sum1-sum2)
### BUGGY CODE ###

def soinsuu(x):#整数xの素因数分解
    n=x
    bunkai=[]
    for i in range(2,int(n**0.5)+1):
        cnt=0
        while x%i==0:
            x//=i
            cnt+=1
        if cnt==0:
            continue
        bunkai.append([i,cnt])
    if x!=1:
        bunkai.append([n,1])
    ans=1
    for l in bunkai:
        ans*=(l[1]+1)
    return ans

N=int(input())
ans=1
for i in range(2,N+1):
    ans+=i*soinsuu(i)
print(ans)

### FIXED CODE ###

def tousa(b,l):
    cnt=l//b
    s=(b+l)*cnt//2
    return s

n=int(input())
ans=0
for k in range(1,n+1):
    N=n//k
    ans+=tousa(k,k*N)
print(ans)
### BUGGY CODE ###


N,M=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
l=[]
l1=[]

for i in range(M):
    b,c=[int(x) for x in input().rstrip().split()]
    l1=[c]*b
    l=l+l1
l.sort(reverse=True)
A=A+l[:N]
A.sort(reverse=True)
print(sum(A[:N]))


    




### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])
 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)
### BUGGY CODE ###

n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

### FIXED CODE ###

n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))
### BUGGY CODE ###

import numpy as np
from functools import reduce

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

cumA = reduce(lambda x, y: x + [y + x[-1]], As, [0])
cumB = reduce(lambda x, y: x + [y + x[-1]], Bs, [0])

max_count = 0
a_count = len(As)
b_count = 0
while a_count >= 0 and b_count < len(Bs):
    while b_count <= len(Bs) and cumA[a_count] + cumB[b_count] <= K:
        b_count += 1
    b_count = max(0, b_count - 1)
    if cumA[a_count] + cumB[b_count] <= K:
        max_count = max(max_count, a_count + b_count)
    a_count -= 1

print(max_count)


### FIXED CODE ###

import numpy as np
from functools import reduce

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


def get_cum(arr):
    cum_arr = [0]
    for e in arr:
        tot = cum_arr[-1] + e
        if tot > K:
            return cum_arr
        cum_arr.append(tot)
    return cum_arr


cumA = get_cum(As)
cumB = get_cum(Bs)

max_count = 0
a_thresh = len(cumA) - 1
a_count = a_thresh
b_count = 0
b_thresh = len(cumB) - 1
while a_count >= 0 and b_count <= b_thresh:
    while b_count <= b_thresh and cumA[a_count] + cumB[b_count] <= K:
        b_count += 1
    b_count = max(0, b_count - 1)
    if cumA[a_count] + cumB[b_count] <= K:
        max_count = max(max_count, a_count + b_count)
    a_count -= 1

print(max_count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
b=list(set(a))
c=0
for i in b:
    nc=0
    for j in range(len(a)):
        if a[j]==i:
          nc+=1
        else:
          nc+=0    
    er = nc - i
    if er<0:
        c+= er+i
    else:
        c+=er
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

def z_algo(S):  # SとS[i:]の最長共通接頭辞 Z Algorithm
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def resolve():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        a = z_algo(s[i:])
        for index, j in enumerate(a):
            if j <= index:
                ans = max(ans, j)
    print(ans)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def resolve():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        a = z_algo(s[i:])
        for index, j in enumerate(a):
            if j <= index:
                ans = max(ans, j)
    print(ans)


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

#bitでタコ殴りにする
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

m=998244353    
N,K=map(int,input().split())
bit = Bit(N)
bit.add(1,1)#初期値　はじめは１
period = []
for _ in range(K):#動ける区間の記憶
    l,r=map(int,input().split())
    period.append((l,r))
for i in range(2,N+1):#2からNまで見ていく。もらうDP
    for l,r in period:
        rx = max(0,i-l)
        lx = max(0,i-r-1)
        if rx==0:
            tmp_r = 0
        else:
            tmp_r = bit.sum(rx)
        if lx == 0:
            tmp_l = 0
        else:
            tmp_l = bit.sum(lx)
        bit.add(i,tmp_r)
        bit.add(i,-tmp_l)
ans = (bit.sum(N)-bit.sum(N-1))%m
print(ans)





### FIXED CODE ###

N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=(DPsum[i-1]+DP[i])%m
print(DP[N]%m)