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

#!/usr/bin/env python3
import io
import os


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

    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        for j in reversed(range(w[i + 1], m + 1)):
            dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
m = []

for i in range(1, n+1):
    m.append(min(p[:i]))

for i in range(1, n+1):
    if p[i-1] <= m[i-1]:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
m = [0] * n

memo = n
for i in range(n):
    if memo > p[i]:
        m[i] = p[i]
        memo = p[i]
    else:
        m[i] = memo

for i in range(1, n+1):
    if p[i-1] <= m[i-1]:
        count += 1

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

import sys
N=int(input())
print(0)
s=input()
if s=='Vacant':
  sys.exit()
a=s
print(N-1)
s=input()
if s=='Vacant':
  exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=x:
      right=n
    else:
      left=n

### FIXED CODE ###

import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=a:
      right=n
    else:
      left=n
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
flag = True
while flag:
    flag = False
    for i in range(N):
        if A[i] >= N:
            count = A[i] // N
            ans += count
            for j in range(N):
                A[j] += count
            A[i] -= count
            A[i] %= N
            flag = True
            break

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
flag = True
while flag:
    flag = False
    for i in range(N):
        if A[i] >= N:
            count = A[i] // N
            ans += count
            for j in range(N):
                A[j] += count
            A[i] -= count
            A[i] %= N
            flag = True

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

def create_anagram_dic(val):
  dic = {}
  for s in val:
    if s not in dic:
      dic[s] = 0
    dic[s] += 1
  
  return dic

def is_anagram(val, dic):
  for k, v in dic.items():
    if val.count(k) != v:
      return False
  return True

N = int(input())

s = list()
for i in range(0, N):
  val = str(input())
  s.append(val)
  
  
result_dic = {}

while len(s) > 0:
  current_val = s[0]
  result_dic[current_val] = 1
  dic = create_anagram_dic(current_val)
  for i in range(len(s) - 1, 0, -1):
    if is_anagram(s[i], dic):
      result_dic[current_val] += 1
      s.pop(i)
  s.pop(0)

result_count = 0
for val in result_dic.values():
  result_count += val * (val - 1) // 2

print(result_count)

### FIXED CODE ###

# 入力部
N = int(input())

s = list()
for i in range(0, N):
  val = str(input())
  s.append(val)
  
# 計算部
result_dic = {}

for i in range(0, len(s)):
  sorted_val = ''.join(sorted(s[i]))
  if sorted_val in result_dic:
    result_dic[sorted_val] += 1
  else:
    result_dic[sorted_val] = 1

result_count = 0
for val in result_dic.values():
  result_count += val * (val - 1) // 2

print(result_count)
### BUGGY CODE ###

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

if __name__ == "__main__":
    N = int(input())
    Xs = list(map(int, input().split()))
    Xs_ = Xs[::]
    Xs_.sort()

    for i in range(N):
        Xs__ = Xs_[::]
        Xs__.remove(Xs[i])
        print(Xs__[int(N/2)-1])


### FIXED CODE ###

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

def solver():
    # mr.zehnpaard
    from statistics import median_low, median_high

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

    m1, m2 = median_low(xs), median_high(xs)

    medians = (str(m2 if x < m2 else m1) for x in xs)
    print('\n'.join(medians))

def main():
    from statistics import median_low, median_high

    N = int(input())
    Xs = list(map(int, input().split()))
    m_low, m_high = median_low(Xs), median_high(Xs)

    for x in Xs:
        ans = m_high if x <= m_low else m_low
        print(ans)


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

import heapq
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))

dp = [[-1 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*hi
dp[0][1] = -ai*(n-1-hi)
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(hi-i+1)
    dp[0][i] = dp[0][i-1] - ai*abs(n-i-hi)
    for j in range(1,i):
        dp[i-j][j] = max(dp[i-j-1][j]-ai*abs(hi-i+j+1),dp[i-j][j-1]-ai*abs(n-j-hi))

max = 0
for i in range(n+1):
    if max < dp[i][n-i]:
        max = dp[i][n-i]
print(max)


### FIXED CODE ###

import heapq
import time
st = time.time()
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))
dp = [[0 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*(n-1-hi)
dp[1][1] = -ai*hi
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(n-i-hi)
    dp[i][i] = dp[i-1][i-1] - ai*abs(hi-i+1)
    for j in range(1,i):
        dp[i][j] = max(dp[i-1][j-1]-ai*abs(hi-j+1),dp[i-1][j]-ai*abs(n-i+j-hi))

print(max(dp[n]))
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(float, input().split()))
MV = 0
add = 0
m = 0 #何番目のサイコロを最後に含むか
ev = 0
lst = []
for i in range(K, N+1):
    for j in range(i-K, i):
        add += p[j]
        m = j
    if MV < add:
        MV = add
        for k in range(m-K+1, m+1):
            ev += ((p[k]*(p[k]+1))/2)/p[k]

    lst.append(ev)
    add = 0
    ev = 0

print(float(max(lst)))

### FIXED CODE ###

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

E = []

for i in range(N):
    E.append((P[i]+1)/2)

tnt = sum(E[:K])
ans = tnt

for i in range(N-K):
    tnt = tnt + E[K+i] - E[i]
    ans = max(ans, tnt)

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

#!/usr/bin/env python3
n,k = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]
kita = [0.5*(i+1) for i in range(max(p)+1)]
kitai = [kita[i] for i in p]
maxn = 0
for i in range(n-k+1):
    kt = 0
    for j in range(k):
        kt += kitai[i+j]
    if kt > maxn:
        maxn = kt
print(maxn)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
maxn = 0
sum = 0
for i in range(n-k+1):
	if i == 0:
		for j in range(k):
			sum += p[j]
		maxn = sum
	else:
		sum -= p[i-1]
		sum += p[i+k-1]
		if maxn < sum:
			maxn = sum
print(0.5*(maxn+k))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  ans=0
  d=[0]*(n+1)
  for i in range(1,n+1):
    for j in range(i,n+1,i):
      d[j]+=1
  for i in range(1,n+1):
    ans+=i*d[i]
  print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  ans=0
  d=[0]*(n+1)
  for i in range(1,n+1):
    for j in range(i,n+1,i):
      d[j]+=1
  for i in range(1,n+1):
    ans+=i*d[i]
  print(ans)
### BUGGY CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
 
s=[list(map(int,list(input().split()))) for i in range(q)] 
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[s[i][1]-1]) - int(retsu[s[i][0]-1]) == s[i][2]:
            tmp = tmp + s[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

### FIXED CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
  A, B, C, D = map(int, input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[b[i]-1]) - int(retsu[a[i]-1]) == c[i]:
            tmp = tmp + d[i]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)
### BUGGY CODE ###

import sys

x = int(input())


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


for i in range(len(make_divisors(x))):
    for j in range(180):
        if j ** 5 - (j - make_divisors(x)[i]) ** 5 == x:
            print(j, j - make_divisors(x)[i])
            sys.exit()

### FIXED CODE ###

import sys
 
x = int(input())
 
 
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
 
 
for i in range(len(make_divisors(x))):
    for j in range(130):
        if j ** 5 - (j - make_divisors(x)[i]) ** 5 == x:
            print(j, j - make_divisors(x)[i])
            sys.exit()
### BUGGY CODE ###

n, m = list(map(int, input().split()))
broken = []
for i in range(m):
    broken.append(int(input()))
MOD = 10 ** 9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in broken:
    dp[1] = 1
for i in range(2, n+1):
    if i not in broken:
        dp[i] = (dp[i-1] + dp[i-2])%MOD

print(dp[-1])

### FIXED CODE ###

# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline
 
def main():
    N, M = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline

inf = float('inf')

n = int(input())
a = tuple(int(input()) for _ in range(n))

seen = [False] * n
cnt = 0

flg = True
while flg:
    flg = False
    num = -1
    for i, aa in enumerate(a):
        if seen[i]:
            continue
        flg = True
        if num == -1:
            num = aa
            seen[i] = True
            cnt += 1
        else:
            if aa > num:
                num = aa
                seen[i] = True

print(cnt)


### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
a = tuple(int(input()) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  # aa以上の最小値のindex
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)
### BUGGY CODE ###

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

a.reverse()
now=[]
now.append(2)

for group in a:
    nxt_now = []
    for num in now:
        if num % group !=0:
            continue

        for i in range(group):
            nxt_now.append(num+i)
    if len(nxt_now) ==0:
        print(-1)
        exit()

    now = nxt_now
print(min(now),max(now))

### FIXED CODE ###

k = int(input())
a = list(map(int, input().split()))
a.reverse()

mn,mx = 2,2
for g in a:
    mn = g * (((mn - 1) // g) + 1)
    mx = g * (mx//g) + g - 1

    if mn > mx:
        print(-1)
        exit()

print(mn,mx)
### BUGGY CODE ###

n, k = map(int, input().split())
cnt=0
for b in range(k+1,n+1):
    a_=int(n/b)
    cnt+=(b-k)*(a_)
#    print(b,n%b, (b-k)*(a_))
    for a in range(1,n%b+1):
        if a%b>=k:
#            print(a,b)
            cnt+=1
#    print(b,cnt)
print(cnt)


### FIXED CODE ###

n, k = map(int, input().split())
cnt=0
if k==0:
    print(n*n)
else:
    for b in range(k+1,n+1):
        a_=int(n/b)
        cnt+=(b-k)*(a_)
        cnt+=max(n%b-k+1, 0)
    print(cnt)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
print(ans % (10**9 + 7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1, n+1):
    ans *= i
    ans %= (10**9 + 7)
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = []
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.append((t_h, t_w))

max_h_set = set([i for i, v in enumerate(num_in_h) if v == max(num_in_h)])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max(num_in_w)])
ans = max(num_in_h) + max(num_in_w)

point = 0
comb = len(max_h_set) * len(max_w_set)
targets = set(targets)
for t in targets:
    if t[0] in max_h_set and t[1] in max_w_set:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)


### FIXED CODE ###

import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h = max(num_in_h)
max_w = max(num_in_w)
max_h_set = set([i for i, v in enumerate(num_in_h) if v == max_h])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max_w])
ans = max_h + max_w - 1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
z = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            for k in range(j+1, n):
                if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and k - j != j - i:
                    z += 1

print(z)

### FIXED CODE ###

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

nR = [0]*n
nG = [0]*n
nB = [0]*n
if s[-1] == 'R':
    nR[-1] = 1
elif s[-1] == 'G':
    nG[-1] = 1
elif s[-1] == 'B':
    nB[-1] = 1
for i in range(n-2, -1, -1):
    if s[i] == 'R':
        nR[i] = nR[i+1] + 1
        nG[i] = nG[i+1]
        nB[i] = nB[i+1]
    elif s[i] == 'G':
        nR[i] = nR[i+1]
        nG[i] = nG[i+1] + 1
        nB[i] = nB[i+1]
    elif s[i] == 'B':
        nR[i] = nR[i+1]
        nG[i] = nG[i+1]
        nB[i] = nB[i+1] + 1

cnt = 0
for i in range(n):
    for j in range(i, n-1):
        if s[i] != s[j]:
            f = 0
            if 2*j - i < n:
                if s[i] != s[2*j-i] and s[j] != s[2*j-i]:
                    f = 1

            if s[i] != 'R' and s[j] != 'R':
                cnt += nR[j] - f
            elif s[i] != 'G' and s[j] != 'G':
                cnt += nG[j] - f
            elif s[i] != 'B' and s[j] != 'B':
                cnt += nB[j] - f

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

n,k=map(int,input().split())
H=list(map(int,input().split()))
H.sort()
H.reverse()
for i in range(k):
    if len(H)>0:
        H.pop(0)
print(sum(H))

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
H.sort()
if n>k:
    for i in range(k):
        H.pop(n-i-1)
    ans=sum(H)
else:
    ans=0
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x), input().split()))
ans = 0
for i in range(M):
  b, c = map(int, input().split())
  b = min(b, N)
  A += [c for j in range(b)]
  heapq.heapify(A)
  for i in range(b):
    heapq.heappop(A)
  
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
exc = []

for i in range(M):
  exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(M):
  e += [exc[i][1]] * exc[i][0]
  count += exc[i][0]
  if count >= N:
    break
cards = sorted(A+e, reverse=True)
print(sum(cards[:N]))
### BUGGY CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        dict[_s].pop(bisect.bisect_left(dict[_s], first))
        s[first] = last
        bisect.insort_left(dict[last], first)

### FIXED CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        if _s == last:
            continue
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)
### BUGGY CODE ###

A,B,C,D = map(int, input().split())
while A != 0 or B != 0 or C != 0 or D != 0:
    if A == 0 or B == 0:
        print("Yes")
    elif C == 0 or D == 0:
        print("No")
    else:
        continue
    A -= 1
    B -= 1
    C -= 1
    D -= 1

### FIXED CODE ###

A,B,C,D = map(int, input().split())
S = 0
while S != 1:
    C = C - B
    A = A - D
    if C <= 0:
        S = 1
        print("Yes")
    elif A <= 0:
        S = 1
        print("No")
    else:
        continue
### BUGGY CODE ###

H,W=map(int,input().split())

queue=[]
mat=[[True]*(W+2)]
for i in range(1,H+1):
  array=[True]+[x=="#" for x in input()]+[True]
  mat.append(array)
  for j in range(1,W+1):
    if array[j]:
      queue.append((i,j))
mat.append([True]*(W+2))
#print(mat)
#print(queue)

d=0
while queue:
  new_queue=set()
  for q in queue:
    i,j=q
    #print(q)
    if not mat[i-1][j]:
      new_queue.add((i-1,j))
      mat[i-1][j]=True
    if not mat[i+1][j]:
      new_queue.add((i+1,j))
      mat[i+1][j]=True
    if not mat[i][j-1]:
      new_queue.add((i,j-1))
      mat[i][j-1]=True
    if not mat[i][j+1]:
      new_queue.add((i,j+1))
      mat[i][j+1]=True
      
  queue=list(new_queue)
  d+=1
  
print(d-1)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

N=int(input())

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

for i in range(N):
    if(N%2==0):
        if(i%2==0):
            B.append(A[i])
        else:
            B.insert(0,A[i])
    else:
        if(i%2==0):
            B.insert(0,A[i])
        else:
            B.append(A[i])

for i in range(N):
    print(B[i] if i==0 else " "+str(B[i]),end="")
print()


### FIXED CODE ###

N=int(input())

A=list(map(int,input().split()))
B=[]
C=[]

for i in range(N):
    if(N%2==0):
        if(i%2==0):
            B.append(A[i])
        else:
            C.append(A[i])
    else:
        if(i%2==0):
            C.append(A[i])
        else:
            B.append(A[i])

C.reverse()
for i in range(len(B)):
    C.append(B[i])

for i in range(N):
    print(C[i] if i==0 else " "+str(C[i]),end="")
print()
### BUGGY CODE ###

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

dp = [float("inf") for i in range(n+k+10)]
dp[0] = 0

for i in range(n-1):
    for j in range(1,k+1):
        if i+j >= n:
            continue
        dp[i+j] = min(dp[i+j], dp[i] +abs(h[i]-h[i+j]))

print(dp[n-1])

### FIXED CODE ###

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

dp = [float("inf") for i in range(n+k+10)]
dp[0] = 0

for i in range(n-1):
    for j in range(1,k+1):
        if i+j >= n:
            continue
        dp[i+j] = min(dp[i+j], dp[i] +abs(h[i]-h[i+j]))

print(dp[n-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    line = input().split()
    l, r = int(line[0]), int(line[1])
    print((r - l + 1 - len(S[l-1:r].replace('AC','')))//2)


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
t = [0] * (N+1)
cnt = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cnt += 1
    t[i] = cnt
t[-1] = t[-2]
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])