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

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def bfs(init_v):
    def to_idx(p):
        i, j = divmod(p, n)
        return i, j

    def to_v(i, j):
        return i*n+j
    next_v = deque([to_idx(init_v)])
    exist[init_v] = 0
    while next_v:
        i, j = next_v.popleft()
        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                continue
            c = cost[to_v(i, j)]+exist[to_v(i, j)]
            if cost[to_v(x, y)] <= c:
                continue
            cost[to_v(x, y)] = c
            next_v.append((x, y))


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
cnt = 0
for i in range(N):
    Pi = P[i]
    for j in range(i+1):
        Pj = P[j]
        if Pi > Pj:
            cnt +=1
            break
cnt = len(P)-cnt
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
Min = P[0]
cnt = 0
for Pi in P:
    if Pi <= Min:
        Min = Pi
        cnt +=1
print(cnt)
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    ls = len(S)
    l = [1] * ls
    nl = [0] * ls
    if ls%2==1:
        val=ls+1
    else:
        val=ls
    for _ in range(val):
        for i in range(ls):
            if S[i] == 'R':
                nl[i + 1] += l[i]
            else:
                nl[i - 1] += l[i]
        for j in range(ls):
            l[j] = nl[j]
            nl[j] = 0
    print(*l)


resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = list(input())
    N = len(S)
    A = [1] * N
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] == 'R':
            A[i + 2] += A[i]
            A[i] = 0
    for i in range(N - 1, 0, -1):
        if S[i] == 'L' and S[i - 1] == 'L':
            A[i - 2] += A[i]
            A[i] = 0
    print(*A)


resolve()
### BUGGY CODE ###

M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=d[:]
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a];i-=1
print(z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M

### FIXED CODE ###

M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[i+1]*3)%M
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-06-26 21:21:26 +0900
# LastModified: 2020-06-26 21:27:41 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    e_p = [sum(p[i:i+k])+k for i in range(n-(k-1))]
    print(max(e_p)/2)




if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-07-29 16:20:16 +0900
# LastModified: 2020-07-29 16:30:22 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = [(x+1)/2 for x in p]
#    print(s)
    s = list(accumulate(s))
    s.insert(0, 0)
    ans = 0
#    print(s)
    for i in range(n-k+1):
        ans = max(ans, s[i+k]-s[i])
    print(ans)



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

import sys
import itertools
import numpy as np

lines = sys.stdin.readlines()

N = int(lines[0].rstrip())
perms = list(itertools.permutations(range(N)))

arr_2d = np.zeros((N,2))
arr_dist = np.zeros(len(perms))

for i, line in enumerate(lines[1:]):
    x, y = map(int,line.split(' '))
    arr_2d[i, 0] = x
    arr_2d[i, 1] = y


index = 0
for l in perms:
    for i in range(N-1):
        arr_dist[index] += np.linalg.norm(arr_2d[l[i]] - arr_2d[l[i+1]])
    index += 1
    
print(np.mean(arr_dist))

### FIXED CODE ###

import sys
import itertools
import numpy as np

lines = sys.stdin.readlines()

N = int(lines[0].rstrip())
perms = list(itertools.permutations(range(N)))
combs = list(itertools.combinations(range(N), 2))

arr_2d = np.zeros((N,2))
if N <= 2:
	arr_dist_memo = np.zeros((len(combs)+1,len(combs)+1))
else:
	arr_dist_memo = np.zeros((len(combs),len(combs)))

arr_dist_ave = np.zeros(len(perms))

for i, line in enumerate(lines[1:]):
    x, y = map(int,line.split(' '))
    arr_2d[i, 0] = x
    arr_2d[i, 1] = y

for i,j in combs:
    arr_dist_memo[i, j] = np.linalg.norm(arr_2d[i] - arr_2d[j])

for index, l in enumerate(perms):
    for i, j  in zip(range(N-1), range(1, N)):
        arr_dist_ave[index] += arr_dist_memo[l[i],l[j]]

print(np.mean(arr_dist_ave)*2)
### BUGGY CODE ###

N, M = map(int, input().split())
islands = {i + 1: {i + 1} for i in range(N)}
ab_list = [map(int, input().split()) for i in range(M)]

ans = list()
k2k = dict()
start = N*(N - 1) / 2


def recursive_dict(x):
  if not x in k2k: return x
  prev = k2k[x]
  while True:
    if prev in k2k:
      prev = k2k[prev]
    else:
      k2k[x] = prev
      return prev


for a, b in ab_list[::-1]:
  a, b = recursive_dict(a), recursive_dict(b)
  if a == b:
    ans.append(0)
    continue
  ans.append(len(islands[a]) * len(islands[b]))
  islands[a] |= islands[b]
  k2k[b] = a

cumsum = 0
for i in ans[::-1]:
  cumsum += i
  print(cumsum)


### FIXED CODE ###

N, M = map(int, input().split())
islands = {i + 1: 1 for i in range(N)}
ab_list = [map(int, input().split()) for i in range(M)]

ans = list()
k2k = dict()
start = N*(N - 1) / 2


def recursive_dict(x):
  if not x in k2k: return x
  prev = k2k[x]
  while True:
    if prev in k2k:
      prev = k2k[prev]
    else:
      k2k[x] = prev
      return prev

for a, b in ab_list[::-1]:
  a, b = recursive_dict(a), recursive_dict(b)
  if a == b:
    ans.append(0)
    continue
  ans.append(islands[a] * islands[b])
  islands[a] += islands[b]
  k2k[b] = a

cumsum = 0
for i in ans[::-1]:
  cumsum += i
  print(cumsum)
### BUGGY CODE ###

from collections import deque, Counter

INF = float("inf")

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

E = [[] for _ in range(N + 1)]
for i in range(1, N):
    E[i].append(i + 1)
    E[i + 1].append(i)
E[X].append(Y)
E[Y].append(X)

C = Counter()
for s in range(1, N + 1):
    dist = [INF] * (N + 1)
    dist[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if dist[c] > dist[p] + 1:
                dist[c] = dist[p] + 1
                Q.append(c)
    C.update(dist)

for k in range(1, N):
    print(C[k] // 2)

### FIXED CODE ###

from collections import deque, Counter

INF = float("inf")

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

E = [[] for _ in range(N + 1)]
for i in range(1, N):
    E[i].append(i + 1)
    E[i + 1].append(i)
E[X].append(Y)
E[Y].append(X)

C = Counter()
for s in range(1, N + 1):
    dist = [INF] * (N + 1)
    dist[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if dist[c] > dist[p] + 1:
                dist[c] = dist[p] + 1
                Q.append(c)
    C.update(dist)

for k in range(1, N):
    print(C[k] // 2)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
#print(dp)
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)
        
     

### FIXED CODE ###

import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)
### BUGGY CODE ###

import math

Q = int(input())
li = []
M = 0
for index in range(Q):
	l, r = map(int, input().split())
	li.append((l, r))
	M = max([M, l, r])

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1

for l, r in li:
	print(sum(similar_2017[l:r+1]))

### FIXED CODE ###

import math

Q = int(input())
li = []
M = 0
for index in range(Q):
	l, r = map(int, input().split())
	li.append((l, r))
	M = max([M, l, r])

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1
similar_sum = [0 for _ in range(M+1)]
for i in range(1,M+1):
	if similar_2017[i] == 1:
		similar_sum[i] = similar_sum[i-1] + 1
	else:
		similar_sum[i] = similar_sum[i-1]

for l, r in li:
	print(similar_sum[r] - similar_sum[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans *= ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans *= ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)

### FIXED CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans = ans * ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans = ans * ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC91 D

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

lst = []
s = input()
k = I()
n = len(s)
for i in range(n):
    for j in range(i+1,n+1):
        lst.append(s[i:j])
lst = list(set(lst))
lst.sort()
print(lst[k-1])


### FIXED CODE ###

#!usr/bin/env python3
s = input()
K = int(input())

l = {s}
for n in range(1, K+1):
    for i in range(0, len(s)-n+1):
        l.add(s[i:i+n])
l = list(l)

l.sort()

print(l[K-1])
### BUGGY CODE ###

#TIME : 
import sys
from math import sqrt
input = sys.stdin.readline

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

n = inp()
a = inlt()
res = 1
for num in a:
    res*=num
if res > 10**18:
    print('-1')
else:
    print(res)

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
      print(0)
      return

  prod = 1
  for a in A:
      prod *= a
      if prod > 1000000000000000000:
          print(-1)
          return
  print(prod)

main ()
### BUGGY CODE ###

import heapq

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

heapq.heapify(a) # in-place

for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        temp = heapq.heappop(a) 
        if c > temp:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, temp)
            break


print(sum(a))

### FIXED CODE ###

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

bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

bc = sorted(bc, key=lambda x: x[1], reverse=True)

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

N=int(input())
S = []
for i in range(N):
  data=input()
  if data not in S:
    S.append(data)
print(len(S))

### FIXED CODE ###

N = int(input())
S = list()
for i in range(N):
  x = input()
  S.append(x)
  
A = set(S)
print(len(A))
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod = 10**9+7
dp = [[0 for j in range(m)]for i in range(n)]
for i in range(m):
    if s[0] ==t[i]:
        dp[0][i] = 1
for i in range(n):
    if s[i] ==t[0]:
        dp[i][0] = 1

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            sumdp = 0
            for k in range(i):
                for l in range(j):
                    sumdp += dp[k][l]
            dp[i][j] = (sumdp + 1) % mod
res = 1
for i in range(n):
    for j in range(m):
        res += dp[i][j]
        res %= mod
print(res)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod = 10**9+7
dp = [[0 for j in range(m)]for i in range(n)]
for i in range(m):
    if s[0] ==t[i]:
        dp[0][i] = 1
for i in range(n):
    if s[i] ==t[0]:
        dp[i][0] = 1

sumdp = [[0 for j in range(m)]for i in range(n)]
if s[0] ==t[0]:
    sumdp[0][0] =1
for i in range(m-1):
    sumdp[0][i+1] =sumdp[0][i]
    if s[0] == t[i+1]:
        sumdp[0][i+1] += 1
for i in range(n-1):
    sumdp[i+1][0]=sumdp[i][0]
    if s[i+1] ==t[0]:
        sumdp[i+1][0] += 1

for i in range(n-1):
    for j in range(m-1):
        if s[i+1] == t[j+1]:
            dp[i+1][j+1] = (sumdp[i][j] + 1) % mod
        sumdp[i+1][j+1] = (sumdp[i][j+1]+sumdp[i+1][j] - sumdp[i][j]+dp[i+1][j+1])%mod
print((sumdp[n-1][m-1]+1)%mod)
### BUGGY CODE ###

N = int(input())
char = []
for _ in range(N):
    a = list(input())
    a.sort()
    char.append(a)

char_count = []
cheack = [0]*N
for i in range(N-1):
    if cheack[i] == 0:
        count = 1
        for k in range(i+1,N):
            if char[i] == char[k]:
                count += 1
                cheack[k] = 1
        if count != 1:
            char_count.append(count)

ans = 0
for hoge in char_count:
    while 0 < hoge:
        hoge -= 1
        ans += hoge 
print(ans)
        

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
S = [input() for _ in range(n)]

d = defaultdict(lambda: -1)
for i in range(n):
    s = ''.join(sorted(list(S[i])))
    d[s] += 1
 
ans = 0
for v in d.values():
    ans += v*(v+1)//2
print(ans)
### BUGGY CODE ###

n=int(input())
r=0
while n!=0:
    r+=n%10
    n=n//10
if r%9==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=input()
r=0
for i in range(0,len(n)):
    r+=int(n[i])
if r%9==0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
nn = str(N)
n = len(nn)
ans = []

for i in range(n):
    waru = N % 10
    N = N // 10  
    ans.append(waru)

Sans = sum(ans)       
if Sans % 9 == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = input()
ans = []

for i in range(len(N)):
    ans.append(N[i])


ys = map((lambda x: int(x)), ans)
Sans = sum(ys)

if Sans % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import fractions
import collections
A,B = map(int,input().split())
p = fractions.gcd(A,B)
#print(p)
num = []
for i in range(2,p+1):
    while p%i==0:
        num.append(i)
        p //= i
#print(num)
pp = collections.Counter(num)
print(len(pp)+1)

### FIXED CODE ###

import fractions
import collections
A,B = map(int,input().split())
p = fractions.gcd(A,B)
#print(p)
num = []
for i in range(2,int(p**0.5)+1):
    while p%i==0:
        num.append(i)
        p //= i
if p != 1:
    num.append(p)
#print(num)
pp = collections.Counter(num)
print(len(pp)+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
N, K = map(int, input().split())
 
h = list(map(int, input().split()))
 
dp = [0]
 
for n in range(1, N):
    temp = float("inf")
    for k in range(1,K+1):
        if n-k < 0:
            continue
        temp = min(temp, dp[-k] + abs(h[n]-h[n-k]))
    dp.append(temp)
#print(dp)
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.zeros(N)
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))
### BUGGY CODE ###

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

def modComb(n,r,mod):
    tmp = 1
    for i in range(1,r+1):
        tmp *= (n-i+1) % mod
        tmp *= pow(i,mod-2,mod)
    
    return tmp % mod


mod = 10**9+7
ans = pow(2,n,mod) - 1
ans %= mod

print(ans-modComb(n,a,mod)-modComb(n,b,mod) % mod)



### FIXED CODE ###

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

def modComb(n,r,mod):
    tmp = 1
    r = min(r,n-r)
    for i in range(1,r+1):
        tmp = tmp * (n-i+1) % mod
        tmp = tmp * pow(i,mod-2,mod)
    
    return tmp % mod


mod = 10**9+7
ans = pow(2,n,mod) - 1

print((ans-modComb(n,a,mod)-modComb(n,b,mod)) % mod)
### BUGGY CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

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


def is_necessary(ai):
    # A[ai] が必要かどうか
    # A[ai] を使わずに K-A[ai] 以上 K 未満を作れるか

    # dp[j]: j を作れる
    dp = np.zeros(K, dtype=bool)
    dp[0] = 1
    for i, a in enumerate(A):
        if i == ai:
            continue
        dp[a:] = dp[a:] | dp[:-a]
    return any(dp[K - A[ai]:])


ans = N
for i, a in enumerate(A):
    ans -= is_necessary(i)
print(ans)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

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


def bisect_left_callable(fn, x, lo, hi):
    """
    (memo) いっぱい呼ぶなら np.searchsorted のほうがベクトル化されててはやそう
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def is_necessary(ai):
    # A[ai] が必要かどうか
    # A[ai] を使わずに K-A[ai] 以上 K 未満を作れるか

    # dp[j]: j を作れる
    dp = np.zeros(K, dtype=bool)
    dp[0] = 1
    for i, a in enumerate(A):
        if i == ai:
            continue
        dp[a:] = dp[a:] | dp[:-a]
    return any(dp[K - A[ai]:])


A.sort()
unnecessary = bisect_left_callable(is_necessary, 1, lo=0, hi=N)
print(unnecessary)
### BUGGY CODE ###

n,k = (int(x) for x in input().split())
s = []
for _ in range(k):
    a,b = (int(x) for x in input().split())
    s+=list(range(a,b+1))
mod = 998244353
    
l = [0]*(n)
s = sorted(s)
min_num = s[0]
for i in range(min_num,n):
    for j in s:
        if j < i:
	        l[i] += (l[i-j])
    if i in s:
        l[i] += 1
    l[i] %= mod
print(l[n-1])

### FIXED CODE ###

n,k = (int(x) for x in input().split())
lr = []
for _ in range(k):
    l,r = (int(x) for x in input().split())
    lr.append((l,r))
lr.sort()

mod = 998244353

dp= [0]*(n+1)
dp[1] = 1

for i in range(2,n+1):
    cnt = 0
    for l,r in lr:
        if l >= i:
            break
        else:
            cnt += dp[i-l] - dp[max(0,i-r-1)]
    dp[i] = (dp[i-1] + cnt) % mod

print(cnt%mod)
### BUGGY CODE ###

def main():
    n,q=map(int,input().split())
    a=[[None for i in range(n)]for i in range(n)]
    for i in range(n-1):
        x,y=map(int,input().split())
        a[x-1][y-1]=True
        a[y-1][x-1]=True
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    from collections import deque 
    d=deque()
    d.append(0)
    completed=[False]*n
    
    while d:
        now=d.popleft()
        completed[now]=True
        for x,aa in enumerate(a[now]):
            if aa==True and completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    n,q=map(int,input().split())
    from collections import deque,defaultdict
    dic=defaultdict(list)
    for i in range(n-1):
        x,y=map(int,input().split())
        dic[x-1].append(y-1)
        dic[y-1].append(x-1)
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    d=deque()
    d.append(0)
    completed=[False]*n
    while d:
        now=d.popleft()
        completed[now]=True
        for x in dic[now]:
            if completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()