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

n,q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
px = [list(map(int,input().split())) for i in range(q)]

child = [[] for _ in range(n)]
for a,b in ab:
    a -= 1
    b -= 1
    child[a].append(b)
    child[b].append(a)
# print(child)

p_val = [0] * n
for p,x in px:
    p_val[p-1] += x

ans = [p_val[0]]+[0]*(n-1)
stack = [0]
visited = [0] * n
while stack:
    s = stack.pop()
    visited[s] = 1
    for c in child[s]:
        if visited[c]:
            continue
        stack+=[c]
        ans[c] = ans[s]+p_val[c]
print(*ans)



### FIXED CODE ###

n,q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
px = [list(map(int,input().split())) for i in range(q)]

child = [[] for _ in range(n)]
for a,b in ab:
    a -= 1
    b -= 1
    child[a].append(b)
    child[b].append(a)
# print(child)

p_val = [0] * n
for p,x in px:
    p_val[p-1] += x

ans = [p_val[0]]+[0]*(n-1)
stack = [0]
visited = [0] * n
while stack:
    s = stack.pop()
    visited[s] = 1
    for c in child[s]:
        if visited[c]:
            continue
        stack+=[c]
        ans[c] = ans[s]+p_val[c]
print(*ans)
### BUGGY CODE ###

N = int(input())
XY = [[int(x) for x in input().split()] for i in range(N)]
mod = 998244353
XY.sort() #Xについてソート
X, Y = zip(*XY)
Y_rank = {x:i for i, x in enumerate(sorted(Y), 1)}
BIT = [0] * (N+1)

def append_BIT(x):
    while x <= N:
        BIT[x] += 1
        x += x & (-x)

def sum_BIT(x):
    ret = 0
    while x:
        ret += BIT[x]
        x &= (x-1)
    return ret

pow2 = [1]
for i in range(N):
    pow2.append(pow2[-1] * 2 % mod)

ret = 0 
for i in range(N):
    y = Y_rank[Y[i]]
    L = i
    R = N-i-1
    D = y-1
    U = N-D-1
    LD = sum_BIT(y)
    append_BIT(y)
    LU = L - LD
    RU = U - LU
    RD = D - LD
    
    ret += (pow2[N]-1 - pow2[L] - pow2[R] - pow2[U] - pow2[D] + pow2[LD] + pow2[LU] + pow2[RU] + pow2[RD])
    ret %= mod

print(ret)
    



### FIXED CODE ###

N = int(input())
XY = [[int(x) for x in input().split()] for i in range(N)]
mod = 998244353
XY.sort() #Xについてソート
X, Y = zip(*XY)
Y_rank = {x:i for i, x in enumerate(sorted(Y), 1)}
BIT = [0] * (N+1)

def append_BIT(x):
    while x <= N:
        BIT[x] += 1
        x += x & (-x)

def sum_BIT(x):
    ret = 0
    while x:
        ret += BIT[x]
        x &= (x-1)
    return ret

pow2 = [1]
for i in range(N):
    pow2.append(pow2[-1] * 2 % mod)

ret = 0 
for i in range(N):
    y = Y_rank[Y[i]]
    L = i
    R = N-i-1
    D = y-1
    U = N-D-1
    LD = sum_BIT(y)
    append_BIT(y)
    LU = L - LD
    RU = U - LU
    RD = D - LD
    
    ret += (pow2[N]-1 - pow2[L] - pow2[R] - pow2[U] - pow2[D] + pow2[LD] + pow2[LU] + pow2[RU] + pow2[RD])
    
ret %= mod
print(ret)
### BUGGY CODE ###

MOD = 998244353
def main():
  N, M, K = map(int, input().split())
  ans = [0] * (K+1)
  temp = 1
  for i in range(N):
    if i == 0:
      temp*=M
      temp %= MOD
    else:
      temp *= (M-1)
      temp %= MOD
    if i+1 >= N-K:
      ans[i+1-N+K] = temp
  t_ans = 0
  key = 1
  for i in range(len(ans)):
    t_ans += (ans[-1-i]*key) % MOD
    t_ans %= MOD
    key *= (N-i-1)
    key //= (i+1)
  print(t_ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

MOD = 998244353
#階乗のリストを作成する
N, M, K = map(int, input().split())
frac = [1]
for i in range(N):
    frac.append(frac[i]*(i+1)%MOD)

#上の公式を用いてcombの計算を行う
def comb(n, k, mod):
    a=frac[n]
    b=frac[k]
    c=frac[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
  
def main():
  ans = [0] * (K+1)
  temp = 1
  for i in range(N):
    if i == 0:
      temp*=M
      temp %= MOD
    else:
      temp *= (M-1)
      temp %= MOD
    if i+1 >= N-K:
      ans[i+1-N+K] = temp
  t_ans = 0
  for i in range(len(ans)):
    key = comb(N-1, i, MOD)
    t_ans += (ans[-1-i]*key)
    t_ans %= MOD
  print(t_ans)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

# coding: utf-8
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    if l == 1:
        l += 2
    for v in range(l, r+1, 2):
        t1 = check(v)
        t2 = check((v+1)//2)
        if t1 and t2:
            ans += 1
    print(ans)

### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left, bisect_right
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag

def primes(n):  
    is_prime = [True] * (n + 1)  
    is_prime[0] = False  
    is_prime[1] = False  
    for i in range(2, int(n**0.5) + 1):  
        if not is_prime[i]:  
            continue  
        for j in range(i * 2, n + 1, i):  
            is_prime[j] = False  
    return [i for i in range(n + 1) if is_prime[i]]
def primes_plus(l):
    # l: 素数の配列
    L = []
    for p in l:
        if check((p+1)//2):
            L.append(p)
    return L
l_primes = primes(10**6)
l_primes = primes_plus(l_primes)[1:]
# print(len(l_primes))
Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    r += 1
    l_idx = bisect_left(l_primes, l)
    r_idx = bisect_left(l_primes, r)
    # print(l_idx, r_idx)
    if l == r and l_idx == r_idx and l == l_primes[l_idx]:
        print(1)
    else:
        print(r_idx - l_idx)
# print(l_primes)
### BUGGY CODE ###

import numpy as np
h,w = map(int,input().split())
field = []
accum=[[0 for i in range(w)] for j in range(h)]
accumrev=[[0 for i in range(w)] for j in range(h)]
stack = [[0 for i in range(w)] for j in range(h)]
stackrev = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    field.append(list(input()))
field = np.array(field)

for i in range(h):
    s = field[i]
    temp = 0
    for j in range(w):
        if s[j] == "#":
            accum[i][j] = 0
            temp = 0
        else:
            temp += 1
            accum[i][j] = temp
    accum[i][-1] = temp
for i in range(h):
    s = field[i]
    temp = 0
    for j in range(1,w+1):
        if s[-j] == "#":
            accumrev[i][-j] = 0
            temp = 0
        else:
            temp += 1
            accumrev[i][-j] = temp
    accumrev[i][0] = temp
# print(field)
# print(np.array(accum))
# print(np.array(accumrev))

nf = np.transpose(field)

for i in range(w):
    s = nf[i]
    temp = 0
    for j in range(h):
        if s[j] == "#":
            stack[j][i] = 0
            temp = 0
        else:
            temp += 1
            stack[j][i] = temp
    stack[-1][i] = temp

for i in range(w):
    s = nf[i]
    temp = 0
    for j in range(1,h+1):
        if s[-j] == "#":
            stackrev[-j][i] = 0
            temp = 0
        else:
            temp += 1
            stackrev[-j][i] = temp
    stackrev[0][i] = temp

# print(field)
# print(np.array(stack))
# print(np.array(stackrev))

accum = np.array(accum)
accumrev = np.array(accumrev)
stack = np.array(stack)
stackrev = np.array(stackrev)

tot = accum+accumrev+stack+stackrev-3
# print(tot)
print(np.max(tot))



### FIXED CODE ###

import numpy as np

H,W = map(int, input().split())
s = [list(input()) for j in range(H)]
s = (np.array(s) == ".") * 1

L = np.zeros((H, W), dtype = int)
R = np.zeros((H, W), dtype = int)
U = np.zeros((H, W), dtype = int)
D = np.zeros((H, W), dtype = int)


for j in range(W):
    if j == 0:
        L[:,j] = s[:,j]
    else:
        L[:,j] = (L[:,j-1] + 1) * s[:,j]
        

for j in reversed(range(W)):
    if j == W-1:
        R[:,j] = s[:,j]
    else:
        R[:,j] = (R[:,j+1] + 1) * s[:,j]


for i in range(H):
    if i == 0:
        U[i,:] = s[i,:]
    else:
        U[i,:] = (U[i-1,:] + 1) * s[i,:]

for i in reversed(range(H)):
    if i == H-1:
        D[i,:] = s[i,:]
    else:
        D[i,:] = (D[i+1,:] + 1) * s[i,:]

print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

A, B, C=map(int,input().split())
K=int(input())
x=0
while x<K:
  if A>B:
    B*=2
    x+=1
  elif B>C:
    C*=2
    x+=1
if C>B>A:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A, B, C=map(int,input().split())
K=int(input())
ab=int(A/B)
if ab==0:
  x=0
else:
  x=int(len(bin(ab))-2)
B1=B*(2**x)
bc=int(B1/C)
if bc==0:
  y=0
else:
  y=int(len(bin(bc))-2)
if x+y<=K:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from itertools import product

n = int(input())
s = input()
r, g, b = [], [], []

for i, char in enumerate(s):
    if char == 'R': r.append(i)
    elif char == 'G': g.append(i)
    else: b.append(i)

count = 0
for config in product(r,g,b):
    a, b, c = config
    a, b, c = sorted((a, b, c))

    if (b-a)!=(c-b): count += 1

print(count)


### FIXED CODE ###

n = int(input())
s = input()

rinds, ginds, binds = [], [], []

for i in range(n):
    if s[i] == 'R': rinds.append(i)
    elif s[i] == 'G': ginds.append(i)
    else: binds.append(i)


rlen, glen, blen = len(rinds), len(ginds), len(binds)

def binsearch_same(binds, blen, dist, i):
    lo, hi = 0, blen-1
    while lo<=hi:
        mid = lo + (hi-lo)//2
        d = binds[mid] - i
        if dist == d:
            return True
        elif d < dist:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

ans = 0

for i in rinds:
    for j in ginds:
        dist = abs(i-j)
        i_ = min(i, j)
        j_ = max(i, j)
        ans += blen
        # i' < j' < k

        if binsearch_same(binds, blen, dist, j_):
            ans -= 1
        # i'< k < j' 
        if dist%2==0 and binsearch_same(binds, blen, dist//2, i_):
            ans -= 1
        # # k < i' < j'
        if binsearch_same(binds, blen, -dist, i_):
            ans -= 1

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

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
counter = set([])
for i in range(n - 1):
    a_np = np.roll(np.array(a), i + 1)
    index = np.where(a % a_np == 0)
    for num in index[0]:
        counter.add(num)
print(n - len(counter))

### FIXED CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
ans = 0
for x in set(a):
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
import os
import math
import itertools
def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0

mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                if mini > abs(x0+y0):
                    mini = abs(x0+y0)
                    x = x0
                    y = y0

print(x-1+y-1)


### FIXED CODE ###

import sys
import os

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

N = int(input())
listN = make_divisors(N)
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(len(listN)):
        x = listN[i]
        y = N//x
        mini = min(x+y,mini)
print(x-1+y-1)
### BUGGY CODE ###

from functools import lru_cache
n= int(input())
arr = [int(x) for x in input().strip().split()]

@lru_cache(None)
def helper(i, mon, stk):
    if i==len(arr):
        return mon
    
    ans = helper(i+1, mon, stk)
    buy = 1
    while True:
        if arr[i]*buy<=mon:
            ans = max(ans, helper(i+1, mon - arr[i]*buy, stk+buy))
        else:
            break
        
        buy += 1
    
    for s in range(1, stk+1):
        ans = max(ans, helper(i+1, mon+arr[i]*s, stk-s))
    
    return ans

    
print(helper(0, 1000, 0))

### FIXED CODE ###

n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

        
# mem = {}
# def helper(i, mon, stk):
#     key = (i, mon, stk)
#     if key in mem:
#         return mem[key]
    
#     if i==len(arr):
#         return mon
    
#     ans = helper(i+1, mon, stk)
#     buy = 1
#     while True:
#         if arr[i]*buy<=mon:
#             ans = max(ans, helper(i+1, mon - arr[i]*buy, stk+buy))
#         else:
#             break
        
#         buy += 1
    
#     for s in range(1, stk+1):
#         ans = max(ans, helper(i+1, mon+arr[i]*s, stk-s))
    
#     mem[key] = ans
#     return ans

    
# print(helper(0, 1000, 0))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = [0 for _ in range(N)]
        x = 0
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
                x = 1
        days += 1
        if not x:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

from fractions import gcd
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for y in range(1, k+1):
            ans += gcd(gcd(i,j), y)
print(ans)


### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for y in range(1, k+1):
            ans += gcd(gcd(i,j), y)
print(ans)
### BUGGY CODE ###

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

ans = 1
for i in range(m//n,0,-1):
    if m % i == 0:
        break
print(i)


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)

solve()
### BUGGY CODE ###

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(input())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
f = [1] * (N + 1)
for i, c in enumerate(C):
    for j in range(i - 1):
        if C[j] == c:
            ans += f[j]
    f[i + 1] = ans

print(ans)

### FIXED CODE ###

import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

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

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

ans=[]

for r in range(int(N/R)+1):
    for g in range(int((N-r*R)/G)+1):
        if ((N-r*R-g*G)/B).is_integer():
            ans.append([r,g,(N-r*R-g*G)/B])

print(len(ans))

### FIXED CODE ###

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

ans=[]

count=0
for r in range(int(N/R)+1):
    for g in range(int((N-r*R)/G)+1):
        
        if (N-r*R-g*G)%B==0:
            count+=1
            #ans.append([r,g,(N-r*R-g*G)/B])

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

import sys

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [sys.maxsize] * N
dp[0] = 0

for i in range(1, N):    
  for k in range(1, K+1):
    if len(H) >= abs(i-k):
      # もらうDP min(to, from)
      dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))
print(dp[-1])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

def cmin(a, b, i):
  if a > b:
    dp[i] = b
    return True
  return False

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [sys.maxsize]*N
dp[0] = 0

for i in range(0, N):
  for j in range(1,K+1):
    cmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]), i)
    if i > 1:
      cmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]), i)
print(dp[N-1])
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.98 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

x,y = map(int,input().split())
mod = 10**9+7
if (2*x-y)%3!=0 and (2*y-x)!=0:
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)*pow(ka(n),mod-2,mod))%mod
print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
if (x+y)%3!=0:
  print(0)
  exit()
if 2*min(x,y)<max(x,y):
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

# input
N = int(input())
S = input()
max_val = 0


for j in range(len(S)):
    s = S[j:]
    z = [0]*len(s)
    n = len(s)
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while (R < n):
                if (s[R - L] == s[R]):
                    z[i] = R - L + 1
                    if z[i] > L:
                        z[i] = 0
                else:
                    break
                R += 1
        else:
            k = i - L
            if z[k] < R - i + 1:
                z[i] = z[k]
            else:
                L = i
                while (R < n):
                    if s[R - L] == s[R]:
                        z[i] = R - L + 1
                        if z[i] > L:
                            z[i] = 0
                    else:
                        break
                    R += 1
    max_z = max(z)
    # print(z)
    # print(n)
    if (max_z > max_val) & (max_z / 2 < n//2):
        max_val = max(z)

print(max_val)


### FIXED CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

import heapq

X, Y, Z, K = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
B = [int(v) for v in input().split()]
C = [int(v) for v in input().split()]

h = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            heapq.heappush(h, (-(A[i]+B[j]+C[k]), A[i], B[j], C[k]))

for i in range(K):
    print(sum(heapq.heappop(h)[1:]))

### FIXED CODE ###

import heapq

X, Y, Z, K = [int(v) for v in input().split()]
A = sorted([int(v) for v in input().split()], reverse=True)
B = sorted([int(v) for v in input().split()], reverse=True)
C = sorted([int(v) for v in input().split()], reverse=True)

added = set()
h = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
added.add((0, 0, 0))
for i in range(K):
    cost, ai, bi, ci = heapq.heappop(h)
    print(-cost)

    if ai + 1 < X:
        na = (ai + 1, bi, ci)
        if not na in added:
            heapq.heappush(h, (-(A[ai + 1] + B[bi] + C[ci]),) + na)
            added.add(na)
    if bi + 1 < Y:
        nb = (ai, bi + 1, ci)
        if not nb in added:
            heapq.heappush(h, (-(A[ai] + B[bi + 1] + C[ci]),) + nb)
            added.add(nb)
    if ci + 1 < Z:
        nc = (ai, bi, ci + 1)
        if not nc in added:
            heapq.heappush(h, (-(A[ai] + B[bi] + C[ci + 1]),) + nc)
            added.add(nc)
### BUGGY CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,m = IL()
    war = [list(IL()) for _ in range(m)]
    war.sort(key=lambda x: x[1])
    bridge = [1]*n
    for rep in war:
        left = rep[0]-1
        right = rep[1]-1
        if not 0 in bridge[left:right]:
            bridge[right-1] = 0
    print(bridge.count(0))
    return

if __name__=='__main__':
    Main()

### FIXED CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,m = IL()
    war = [list(IL()) for _ in range(m)]
    war.sort(key=lambda x: x[1])
    pre = war[0][1]-2
    ans = 1
    for rep in war:
        if pre<rep[0]-1:
            pre = rep[1]-2
            ans += 1
    print(ans)
    return

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

n, k = map(int, input().split())
p = list(map(int, input().split()))

def kitai(n):
  return (1 + n) / 2

ans = 0
for i in range(n - k + 1):
  temp = 0
  for j in range(k):
    temp += kitai(p[i + j])
  ans = max(ans, temp)
  
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

s = [0]

def kitai(n):
  return (1 + n) / 2

for i in range(n):
  s.append(kitai(p[i]) + s[-1])

ans = 0
for i in range(n - k + 1):
  ans = max(ans, s[i + k] - s[i])
print(ans)