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

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]
while True:
  new_move_lis  = []
  for i,j in move_lis:
    if maze[i][0][j] == "#":
      continue
    for k,l in walk_move:
      if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in already_lis:
        dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
        new_move_lis.append([i+k, j+l])
        already_lis.append([i+k, j+l])
  if not len(new_move_lis):
    new_already_lis = []
    for o,p in already_lis:
      for m,n in magic_move:
        if not m and not n:
          continue
        if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == ".":
          dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
          new_move_lis.append([o+m, p+n])
          new_already_lis.append([o+m, p+n])
    already_lis = new_already_lis
  if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
    break
  else:
    move_lis = new_move_lis

if dp[Dh-1][Dw-1] == inf:
  print("-1")
else:
  print(dp[Dh-1][Dw-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが良い場合は値を更新

print(max(dp))

### FIXED CODE ###

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが良い場合は値を更新

print(max(dp))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
num = int(input())
line = list(map(int,input().split()))
for i in range(1,num+1):
    print(line.count(i))

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections
num = int(input())
line = list(map(int,input().split()))
clist = collections.Counter(line)
for i in range (1,num+1):
    print(clist[i])
### BUGGY CODE ###

import itertools

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


combi = []
perm = []

# 1からn桁の[1, 2]の数字の組み合わせのうち合計値がnになるものをcombiに代入
for i in range(int(n / 2), n + 1):
    tmp_combi = list(itertools.combinations_with_replacement([1, 2], i))
    for c in (tmp_combi):
        if sum(c) == n:
            combi.append(c)

# combiの順列を作成しpermに入れる
# setを使いユニークにしている
# 1, 1, 2 -> 1 1 2, 1 2 1, 2 1 1
for c in combi:
    for p in list(set(list(itertools.permutations(c)))):
        perm.append(p)

# 順列1つずつに対しコストを計算して最小値をmin_costに代入
min_cost = 10 ** 10
for p in perm:
    cost = 0
    p = list(p)
    pos = p.pop(0)
    if pos != 1:
        continue
    for j in p:
        cost += abs(h[pos - 1] - h[pos + j - 1])
        pos += j
    if cost < min_cost:
        min_cost = cost

print(min_cost)

### FIXED CODE ###

N = int(input())
blank = 2
h = list(map(int,input().split())) + [0] * blank
INF = 10 ** 9 + 1
dp = [INF] * (N + blank)
dp[0] = 0
for i in range(N):
  dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i + 1])
  dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 2])
  
print(dp[N - 1])
### BUGGY CODE ###

n,k=map(int,input('').split(' '))
a=input('')
a=a.split(' ')
for p in range(n):
    a[p]=int(a[p])

p=1
h=[]
h.append(1)
j=k
while j>0:
    p=a[p-1]
    if p in h:
        j=j-1
        c=len(h)-h.index(p)
        j=j%c
        h=[]

    else:
        h.append(p)
        j=j-1

print(p)

### FIXED CODE ###

n,k=map(int,input('').split(' '))
a=input('')
a=a.split(' ')
o=[]
l=[]
for p in range(n):
    a[p]=int(a[p])
    o.append(0)
    l.append('n')

p=1
h=[]
h.append(1)
j=k
aj=0
while j>0:
    p=a[p-1]
    o[p-1]+=1
    if o[p-1]>=2:
        j=j-1
        c=len(h)-l[p-1]#h.index(p)
        j=j%c

    else:
        h.append(p)
        j=j-1
    
        aj+=1
    
    l[p-1]=aj

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

# -*- coding: utf-8 -*-
import sys
X, Y = map(int, input().split())

mod = 10 ** 9 + 7

a = (2 * Y - X) / 3
b = (2 * X - Y) / 3
if a < 0 or b < 0 or (X + Y) % 3 != 0:
    print(0)
    sys.exit()

a = int(a)
b = int(b)
N = a + b
f = [1]
invf = [1]
for i in range(1,a+b+1):
    f.append((f[-1] * i) % mod)
    invf.append(pow(f[i], mod-2, mod))
ans = f[a+b] * (invf[a] * invf[b] % mod) % mod
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
X, Y = map(int, input().split())

mod = 10 ** 9 + 7

a = (2 * Y - X) / 3
b = (2 * X - Y) / 3
if a < 0 or b < 0 or (X + Y) % 3 != 0:
    print(0)
    sys.exit()

a = int(a)
b = int(b)
N = a + b
f = [1]
for i in range(1,a+b+1):
    f.append((f[-1] * i) % mod)
ans = f[a+b] * (pow(f[a], mod-2, mod) * pow(f[b], mod-2, mod) % mod) % mod
print(ans)
### BUGGY CODE ###

s=input()
l=len(s)
a=[]
z=[]
ans=0
for i in range(l):
    if s[i]=="A":
        a.append(i)
    elif s[i]=="Z":
        z.append(i)

for i in range(len(a)):
    for j in range(len(z)):
        if abs(z[j]-a[i]+1)>=ans:
            ans=abs(z[j]-a[i]+1)

print(ans)

### FIXED CODE ###

s=input()
l=len(s)
a=[]
z=[]
ans=0
for i in range(l):
    if s[i]=="A":
        a.append(i)
    elif s[i]=="Z":
        z.append(i)

ans=(max(z)-min(a)+1)

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


n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    
    return result

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)


### FIXED CODE ###

n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
checked = [0]
next_num = a[0]-1
i = 0
while True:
    if i == 0:
        i += 1
    elif next_num in checked:
        loop = checked[checked.index(next_num):]
        break
    checked.append(next_num)
    next_num = a[next_num]-1
dif = len(checked) - len(loop)
if k <= dif:
    print(checked[k]+1)
else:
    k = k-dif
    print(loop[k%len(loop)]+1)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
checked = [0]
next_num = a[0]-1
check = [0]*n
i = 0
while True:
    if i == 0:
        i += 1
    elif check[next_num] == 1:
        loop = checked[checked.index(next_num):]
        break
    checked.append(next_num)
    check[next_num] = 1
    next_num = a[next_num]-1
dif = len(checked) - len(loop)
if k <= dif:
    print(checked[k]+1)
else:
    k = k-dif
    print(loop[k%len(loop)]+1)
### BUGGY CODE ###

s = [_ for _ in input()]


def f(s):
  result = 0
  for i in range(len(s)-1):
    if s[i] == 'B' and s[i+1] == 'W':
      result += 1
      s[i] = 'W'
      s[i+1] = 'B'
  return result

result = 0
while True:
  temp = f(s)
  if temp == 0:
    break
  else:
    result += temp
print(result)

### FIXED CODE ###

s = input()
b_count = s.count('B')
shoki = 0
for i in range(len(s)):
  if s[i] == 'B':
    shoki += i
saigo = sum(range(len(s) - b_count,len(s)))
print(saigo-shoki)
### BUGGY CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def main():
    """ main """
    N = int(input())
    AS = list(map(int, input().split()))
    dp = [0]*N
    dp[0] = AS[1]
    for i in range(1,N):
        for j in range(0,i):
            dp[j] = gcd(dp[j],AS[i])
        i_gcd = AS[0]
        for j in range(1,i):
            i_gcd = gcd(AS[j],i_gcd)
        dp[i] = i_gcd
    print(max(dp))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def main():
    """ main """
    N = int(input())
    AS = list(map(int, input().split()))
    L = [0]*(N+2)
    R = [0]*(N+2)
    for i in range(0,N):
        L[i+1] = gcd(L[i],AS[i])
    for i in range(N-1,-1,-1):
        R[i] = gcd(R[i+1],AS[i])
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i],R[i+1]))
    print(ans)


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

import numpy as np

p = int(input())
aaa = list(map(int, input().split()))

q = p - 2
m = np.arange(p + 1, dtype=np.int32)
r = np.ones(p + 1, dtype=np.int32)
while q:
    if q & 1:
        r = r * m % p
    m = m * m % p
    q >>= 1

coefs = [0] * p
coefs[0] = sum(aaa)
for i, a in enumerate(aaa):
    if a == 0:
        continue
    b = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b) % p
        b = -b * i * j * r[p - j] % p

print(*coefs)


### FIXED CODE ###

p = int(input())
aaa = list(map(int, input().split()))

coefs = [0] * p
coefs[0] = sum(aaa)
invs = [pow(x, p - 2, p) for x in range(p + 1)]
for i, a in enumerate(aaa):
    if a == 0:
        continue

    b = 1
    c = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b * c) % p
        b = -b * i % p
        c = c * j * invs[p - j] % p

print(*coefs)
### BUGGY CODE ###

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

cnt = 0

for X in range(min(A),max(A)+1):
    transient = A.count(X-1) + A.count(X) + A.count(X+1)
    if transient > cnt:
        cnt = transient

print(cnt)


### FIXED CODE ###

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

C = [0]*(10**5 + 2)

for i in A:
    C[i-1] += 1
    C[i] += 1
    C[i+1] += 1

print(max(C))
### BUGGY CODE ###

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

rates_list = [[],[]]
for i in range(3):
	if aa[i] > bb[i]:
		rates_list[1].append([bb[i], aa[i]])
	else:
		rates_list[0].append([aa[i], bb[i]])

max_d = n
for j in range(2):
	rates = rates_list[j]
	if len(rates) > 0:
		dp = [[0 for _ in range(max_d + 1)] for _ in range(len(rates))]
		dp[0] = [(d // rates[0][0]) * rates[0][1] + d % rates[0][0] for d in range(max_d + 1)]
		for i in range(1, len(rates)):
			for d in range(1, max_d + 1):
				if d - rates[i][0] >= 0:
					dp[i][d] = max(dp[i - 1][d], dp[i][d - rates[i][0]] + rates[i][1])
				else:
					dp[i][d] = dp[i - 1][d]
		#print(dp)
		max_d = dp[len(rates) - 1][max_d]
print (max_d)


### FIXED CODE ###

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

rates_list = [[],[]]
for i in range(3):
	if aa[i] > bb[i]:
		rates_list[1].append([bb[i], aa[i]])
	else:
		rates_list[0].append([aa[i], bb[i]])

max_d = n
for j in range(2):
	rates = rates_list[j]
	if len(rates) == 1:
		max_d = (max_d // rates[0][0]) * rates[0][1] + max_d % rates[0][0]
	elif len(rates) == 2:
		val = [rates[0][1] * i for i in range(max_d // rates[0][0] + 1)]
		rest = [max_d - rates[0][0] * i for i in range(max_d // rates[0][0] + 1)]
		val = [val[i] + rates[1][1] * (rest[i] // rates[1][0]) + (rest[i] % rates[1][0]) if rest[i] > 0 else val[i] for i in range(len(val))]
		max_d = max(val)
	elif len(rates) == 3:
		dp = [(d // rates[0][0]) * rates[0][1] + d % rates[0][0] for d in range(max_d + 1)]
		for d in range(1, max_d + 1):
			dp[d] = max([dp[d]] + [dp[d - rates[i][0]] + rates[i][1] if d - rates[i][0] >= 0 else d for i in range(1, len(rates))])
		max_d = dp[-1]
print (max_d)
### BUGGY CODE ###

import heapq
x, y, z, k = [ int(v) for v in input().split() ]
x_list = sorted([ int(v) for v in input().split() ], reverse = True)
y_list = sorted([ int(v) for v in input().split() ], reverse = True)
z_list = sorted([ int(v) for v in input().split() ], reverse = True)
check_list = [ [ [ False for i in range(x) ] for j in range(y) ]  for l in range(z)]
cake_list = []
def maling_cake(a,b,c):
    d = x_list[a]+y_list[b]+z_list[c]
    return (-d,a,b,c)


for i in range(k):
    if i == 0:
        print(-maling_cake(0,0,0)[0])
        check_list[0][0][0] = True
        if x > 1: 
            heapq.heappush(cake_list, maling_cake(1,0,0))
            check_list[1][0][0] = True
        if y > 1: 
            heapq.heappush(cake_list, maling_cake(0,1,0))
            check_list[0][1][0] = True
        if z > 1: 
            heapq.heappush(cake_list, maling_cake(0,0,1))
            check_list[0][0][1] = True
        
    else:
        di, ai, bi, ci = heapq.heappop(cake_list)
        if ai < x - 1:
            if check_list[ai+1][bi][ci] == False:
                heapq.heappush(cake_list, maling_cake(ai+1,bi,ci))
                check_list[ai+1][bi][ci] = True
        if bi < y - 1:
            if check_list[ai][bi+1][ci] == False:
                heapq.heappush(cake_list, maling_cake(ai,bi+1,ci))
                check_list[ai][bi+1][ci] = True
        if ci < z - 1:
            if check_list[ai][bi][ci+1] == False:
                heapq.heappush(cake_list, maling_cake(ai,bi,ci+1))
                check_list[ai][bi][ci+1] = True

        print(-di)

### FIXED CODE ###


import heapq
x, y, z, k = [ int(v) for v in input().split() ]
x_list = sorted([ int(v) for v in input().split() ], reverse = True)
y_list = sorted([ int(v) for v in input().split() ], reverse = True)
z_list = sorted([ int(v) for v in input().split() ], reverse = True)

cake_list = []
num_set = set([0])

def hash2(a,b,c):
    return 10**8*a+10**4*b+c


def maling_cake(a,b,c):
    d = x_list[a]+y_list[b]+z_list[c]
    return (-d,a,b,c)

for i in range(k):
    if i == 0:
        print(-maling_cake(0,0,0)[0])
        if x > 1: 
            heapq.heappush(cake_list, maling_cake(1,0,0))
            num_set.add(hash2(1,0,0))
        if y > 1: 
            heapq.heappush(cake_list, maling_cake(0,1,0))
            num_set.add(hash2(0,1,0))
        if z > 1: 
            heapq.heappush(cake_list, maling_cake(0,0,1))
            num_set.add(hash2(0,0,1))
        
    else:
        di, ai, bi, ci = heapq.heappop(cake_list)
        if ai < x - 1:
            if hash2(ai+1,bi,ci) not in num_set:
                heapq.heappush(cake_list, maling_cake(ai+1,bi,ci))
                num_set.add(hash2(ai+1,bi,ci))
        if bi < y - 1:
            if hash2(ai,bi+1,ci) not in num_set:
                heapq.heappush(cake_list, maling_cake(ai,bi+1,ci))
                num_set.add(hash2(ai,bi+1,ci))
        if ci < z - 1:
            if hash2(ai,bi,ci+1) not in num_set:
                heapq.heappush(cake_list, maling_cake(ai,bi,ci+1))
                num_set.add(hash2(ai,bi,ci+1))
        print(-di)
### BUGGY CODE ###

import numpy as np

d, g = map(int, input().split())
points_list = []
for i in range(d):
    p, c = map(int, input().split())
    points = []
    for j in range(p):
        point = [j, (i + 1) * 100 * j]
        points.append(point)
    points.append([j + 1, (i + 1) * 100 * (j + 1) + c])
    points_list.append(points)

total = np.array(points_list.pop())
for points in points_list:
    subtotal = np.array([[0,0]])
    for point in points:
        subtotal = np.append(subtotal, total + point, axis = 0)
    total = np.array(subtotal)

print(min(total[total[:,1] >= g][:,0]))

### FIXED CODE ###

d, g = map(int, input().split())
comp_points = []
P = []
for i in range(d):
    p, c = map(int, input().split())
    comp_points.append([p, (i + 1) * 100 * p + c])
    P.append(p)

ans = 10**10
#bitallsearch
for i in range(2 ** d):
    bit = format(i, "b").zfill(d)
    count = 0
    point = 0
    for j, dot in enumerate(bit):
        if dot == "1":
            count += comp_points[j][0]
            point += comp_points[j][1]
    #add shortage form high point not comp_points
    for b in range(d-1, -1, -1):
        flag = False
        if point >= g:
            ans = min(ans, count)
            break
        if bit[b] == "0":
            flag = True
            for p in range(P[b] - 1):
                count += 1
                point += (b+1) * 100
                if point >= g:
                    ans = min(ans, count)
                    break
        if (point < g) & flag:
            break

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

N,K = map(int,input().split())
x = list(map(int,input().split()))
x.append(0)
x.sort()

c = []
for i in range(N - K + 2):
    if (0 not in x[i:i+K+1]) or (len(x[i:i+K+1]) != K+1):
        continue
    p = x[i:i+K+1]
    if min(p) < 0 and max(p) > 0:
        if p[-1] + p[-1] - p[0] < abs(p[0]) + p[-1] -p[0]:
            c.append(p[-1] + (p[-1] - p[0]))
        else:
            c.append(abs(p[0]) + p[-1] - p[0])
    elif min(p) >= 0:
        c.append(p[-1])
    elif max(p) <= 0:
        c.append(abs(p[0]))

print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
### BUGGY CODE ###

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

neigh = {}

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys(), reverse=True)

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]
            break

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]
    ans[px[i][0] - 1] += px[i][1]

print(*ans)


### FIXED CODE ###

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

neigh = {}

ans = [0] * n
#print(neigh)
#print(neigh)

for i in range(q) :
    ans[px[i][0] - 1] += px[i][1]

for i in range(n - 1) :
    neigh.setdefault(ab[i][0], []).append(ab[i][1])

sortKey = sorted(neigh.keys())

for k in sortKey :
    for e in neigh[k] :
        ans[e - 1] += ans[k - 1]

print(*ans)

'''
    ans[sortKey]

for i in range(len(sortKey)) :
    for j in range(i + i, len(sortKey)) :
        if sortKey[i] in neigh[sortKey[j]] :
            neigh[sortKey[j]] += neigh[sortKey[i]]
            break

    if px[i][0] in neigh :
        for e in neigh[px[i][0]] :
            ans[e - 1] += px[i][1]


print(*ans)
'''
### BUGGY CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
l = [0] * N
c = 0
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
        l[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    print(max(l[a - 1: b]) - max(l[:a]))

### FIXED CODE ###

# coding: utf-8
N, Q = map(int, input().split())
S = input()
c = 0
lst = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    lst[i + 1] = c
for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(K):
    counter = [0] * (N+2)
    for i, a in enumerate(A, 1):
        counter[max(0, i - a)] += 1
        counter[min(N + 1, i + a + 1)] += -1
    end = True
    for i in range(1, len(counter) - 1):
        counter[i] += counter[i-1]
        if counter[i] != N: end = False
    A = counter[1:N+1]
    if end: break
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]

rcvs = rcvs

def main():
    for i in range(len(rcvs)):
        rcvs[i][0] -= 1
        rcvs[i][1] -= 1
    
    rewards = [[0 for _ in range(C)] for _ in range(R)]
    
    
    for rcv in rcvs:
        rewards[rcv[0]][rcv[1]] = rcv[2]
    
    dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
    answer = 0
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                candidate = dp[i+1][j][k]
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    print(max(dp[-1][-1]))

main()

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))