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())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from heapq import heappop,heappush
todo=[[0,Ch,Cw]]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo:
  cnt,nh,nw=heappop(todo)
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        heappush(todo,[cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        heappush(todo,[cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])


### FIXED CODE ###

h,w=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
todo=[[0,Ch,Cw]]
ntodo=[]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo or ntodo:
  if not todo:
    todo=ntodo
    ntodo=[]
  cnt,nh,nw=todo.pop()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.append([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        ntodo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

point = 0
lin = []

for i in range(n,0,-1):
    score = 0
    for j in range(i+1,n+1):
        if j % i == 0:
            score += li[j-1]
    if li[i-1] != score%2:
        point += 1
        lin.append(i)

print(point)
for i in lin:
    print(i)

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = [0] + list(map(int,stdin.readline().rstrip().split()))
lin = [0]*(n+1)
point = 0
lis = []

for i in range(n,0,-1):
    su = sum(lin[i::i])%2
    if li[i] != su:
        lin[i] = 1
        point += 1
        lis.append(i)
    
print(point)
lis.sort()

for i in lis:
    print(i)
### BUGGY CODE ###

from pprint import pprint
from collections import deque


def solve(n, q, edges, p):
    counter = [0] * n


    parents = deque()
    parents.append(0)
    while parents:
        parent = parents.popleft()
        counter[parent] += p[parent]
        # print("child")
        # print(child, counter[child])
        if parent in edges:
            for child in edges[parent]:
                counter[child] = counter[parent]
                # print("c")
                # print(c, counter[c])
                parents.append(child)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = set()
    edges = {}
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        if a_i not in a:
            a.add(a_i)
            edges[a_i-1] = []
        edges[a_i-1].append(b_i-1)

    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

N, M = map(int, input().split())

C = []
dp = [10 ** 9 for i in range (1 << N)]
dp [0] = 0
for i in range(M):
  a, b = map(int, input().split())
  c = list(map(lambda x: int(x) - 1, input().split()))
  b = 0
  for i in c:
    b |= 1 << i
  C.append((b,a))
for s in range(1 << N):
  for c in range(M):
    t = s | C[c][0]
    cost = dp[s] + C[c][1]
    dp[t] = min(dp[t], cost)
print (dp[-1] if dp[-1] != 10 ** 9 else -1)

### FIXED CODE ###

N, M = map(int, input().split())

C = []
dp = [10 ** 9 for i in range (1 << N)]
dp [0] = 0
for i in range(M):
  a, b = map(int, input().split())
  c = list(map(lambda x: int(x) - 1, input().split()))
  b = 0
  for i in c:
    b |= 1 << i
  C.append((b,a))
for s in range(1 << N):
  for c in range(M):
    t = s | C[c][0]
    dp[t] = min(dp[t], dp[s] + C[c][1])
print (dp[-1] if dp[-1] != 10 ** 9 else -1)
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
grid = []
for i in range(q):
    array = list(map(int, input().strip().split()))
    grid.append(array)

line = []
for i in range(n-1):
    if (s[i:i+2]=="AC"): 
        line.append(1)
    else:
        line.append(0)
    
for i in range(0,q):
    target = line[grid[i][0]-1:grid[i][1]-1]
    print(sum(target))

### FIXED CODE ###

import numpy as np

n,q=map(int,input().split())
s=str(input())

line = np.zeros([n,])
count = 0
for i in range(1,n):
    if (s[i-1:i+1]=="AC"): 
        count += 1
    line[i]=count 
        
for i in range(q):
    l,r = map(int,input().split())
    target = line[r-1] - line[l-1]
    print(int(target))
### BUGGY CODE ###

a = int(input())
c = list(map(int, input().split()))
ans = c[0]
for i in range(1, a):
  ans = ans*c[i]

if ans > 10**18:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

import sys
a = int(input())
c = list(map(int, input().split()))

if 0 in c:
  print('0')
  sys.exit()

ans = c[0]
for i in range(1, a):
  ans = ans*c[i]
  if ans > 10**18:
    print('-1')
    sys.exit()
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
ans = -1
for i in range(n):
  a.append(int(input()))
btn = 1
cnt = 0
while True:
  btn = a[btn-1]
  cnt += 1
  if btn == 2:
    ans = cnt
    break
  if btn == 1:
    break
print(ans)    

### FIXED CODE ###

n = int(input())
a = []
ans = -1
for i in range(n):
  a.append(int(input()))
btn = 1
cnt = 0
for i in range(n):
  btn = a[btn-1]
  cnt += 1
  if btn == 2:
    ans = cnt
    break
  if btn == 1:
    break
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n=int(input())
a=list(map(int,input().split()))
limit=10**18

ans = 1
ans = reduce(mul, a) #=> 1320

# for i in range(n):
#   ans *= a[i]
#   if a[i] == 0:
#     break
#   elif (ans*a[i]) > limit:
#     ans = -1
#     break

if ans > limit:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

# from operator import mul
# from functools import reduce

n=int(input())
a=list(map(int, input().split()))
# limit=10**18

# if 0 in a:
#     print(0)
#     exit()

ans = 1
# ans = reduce(mul, a) #=> 1320

for i in range(n):
  ans *= a[i]
  if ans > 10 ** 18:
  # if a[i] == 0:
  #   break
  # elif (ans*a[i]) > limit:
    ans = -1
    break

for i in range(n):
  if a[i] == 0:
      ans = 0

# if ans > limit:
#   print(-1)
# else:
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
m = []
for i in range(Q):
 l, r = map(int, input().split())
 Sc = S[l-1:r]
 m = []
 for j in range(len(Sc)-1):
        if Sc[j] == 'A' and Sc[j+1] == 'C':
            m.append(1)
        else:
            m.append(0)
 print(sum(m))

### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())

count = [0] * n
for i in range(n - 1):
    if s[i:i+2] == "AC":
        count[i+1] = count[i] + 1
    else:
      count[i+1] = count[i]

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(count[r] - count[l])
### BUGGY CODE ###

# PDFで解法が4つも書いてある。これはその最初の解法

x,y,z,k =  list(map(int, input().split() ))

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

aa.sort(reverse = True)
bb.sort(reverse = True)
cc.sort(reverse = True)
# 降順＝大きい方から順

ab = []
for i in aa:
	for j in bb:
		ab.append(i + j)

# ab = [i + j for i in aa for j in bb]
# appendを使うと遅いので、二重の内包記法を使う 
# 外側でaaの要素、内側でbbの要素が動いていく。今回はどっちでも良いけど。
ab.sort(reverse = True)

max_len = min(k, len(ab))
abc = []
for i in ab[:max_len]:
	for j in cc:
		abc.append(i + j)

# abc = [i + j for i in ab[:max_len] for j in cc]
abc.sort(reverse = True)

for i in range(k):
	print(abc[i])


### FIXED CODE ###

# PDFで解法が4つも書いてある

x,y,z,k =  list(map(int, input().split() ))

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

aa.sort(reverse = True)
bb.sort(reverse = True)
cc.sort(reverse = True)
# 降順＝大きい方から順

ab = [i + j for i in aa for j in bb]
# appendを使うと遅いので、二重の内包記法を使う 
# 外側でaaの要素、内側でbbの要素が動いていく。今回はどっちでも良いけど。
ab.sort(reverse = True)

max_len = min(k, len(ab))
abc = [i + j for i in ab[:max_len] for j in cc]
abc.sort(reverse = True)

for i in range(k):
	print(abc[i])
### BUGGY CODE ###

x,s=map(int,input().split())
n=x+1
a=0
for i in range(n):
    for j in range(n):
        for k in  range(n):
            if i+j+k==s:
                a+=1
print(a)

### FIXED CODE ###

x,s=map(int,input().split())
n=x+1
a=0
for i in range(n):
    for j in range(n):
        if 0<=(s-(i+j))<=x:
            a+=1
print(a)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[v].append(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = list(y)
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = list(x)
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,0)])
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==s:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())

ans = 0

while True:
    if N >= 1 and M >= 2:
        N -= 1
        M -= 2
        ans += 1
    elif M >= 4:
        M -= 4
        ans += 1
    else:
        break
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())

ans = 0

ans += min(N, M//2)

N -= ans
M -= ans * 2

ans += M // 4

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

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

expect_value_dice = []
ans = []
for i in p:
    expect_value_dice.append((1+i)/2)


for i in range(n - k +1):
    ans.append(sum(expect_value_dice[i:i+k]))

print(max(ans))

### FIXED CODE ###

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

sum_p =[0]
tmp = 0
for i in p:
    tmp += i
    sum_p.append(tmp)

max_expect = 0
for i in range(k, n+1):
    tmp = sum_p[i] - sum_p[i - k]
    max_expect = max(tmp, max_expect)

ans = (k + max_expect)/2
print(ans)
### BUGGY CODE ###

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

if X[0] > X[1]:
    v = X[0]
else:
    v = X[1]

while True:
    if (v % X[0] == 0) and (v % X[1] == 0):
        j = v
        break
    v += 1

print(j)

### FIXED CODE ###

import fractions

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

v = fractions.gcd(X[0], X[1])
j = X[0] / v
p = int(X[1] * j)

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

a=int(input())
i=100
f=0
while i<a:
  if a>100000:
    a=a/100000
    i=i//100000
  i=int(i*1.01)
  f=f+1
print(f)


### FIXED CODE ###

a=int(input())
i=100
f=0
while i<a:
  i=i+i//100
  f=f+1
print(f)
### BUGGY CODE ###

K = int(input())
ans = 0

def gcd(p, q):
  if p % q == 0: return q
  return gcd(q, p%q)

for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      ans += gcd(gcd(i, j), k)
      
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 k in range(1, K+1):
      ans += gcd(gcd(i, j), k)
      
print(ans)
### BUGGY CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
n,m=map(int,input().split())
s=input()
t=input()
if s[0]!=t[0]:
    print(-1)
    exit()
k=lcm(n,m)
ans=[""for i in range(k)]
ans[0]=s[0]
for i in range(1,n):
    ans[i*(k//n)]=s[i]
for i in range(1,m):
    if not ans[i*(k//m)]:
        ans[i*(k//m)]=t[i]
    else:
        if ans[i*(k//m)]!=t[i]:
            print(-1)
            exit()
print(k)

### FIXED CODE ###

from math import gcd
N,M = map(int, input().split())
S = input()
T = input()
G = gcd(N,M)
for i in range (G):
  if S[N//G * i] != T[M//G * i]:
    print(-1)
    exit()
print(N//G * M//G * G)
### BUGGY CODE ###

l,r = map(int,input().split())
ans = 100000000000000000
for i in range(l,r):
  for j in range(l+1,r+1):
    ans = min(ans,(i*j) % 2019)
    if((i*j) % 2019 == 0):
      break
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
if r-l >= 2019:
    print(0)
else:
    r1 = r % 2019
    l1 = l % 2019
    if l1 > r1:
        print(0)
    else:
        ans = 2019
        for i in range(l1, r1):
            for j in range(i + 1, r1 + 1):
                ans = min(ans, (i*j) % 2019)
        print(ans)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        L,R=bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY 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 += [c] * b

a.sort()
bc.sort(reverse=True)
sum_a = sum(a)

ans = sum_a
for i, j in zip(a, bc):
    if i >= j:
        break
    ans += j - i

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)


def f():
    s = sum(a)
    i = 0
    for v in bc:
        b, c = map(int, v)
        while b > 0:
            if i >= n:
                return s
            if c <= a[i]:
                return s
            s += c - a[i]
            b -= 1
            i += 1
    return s


print(f())
### BUGGY CODE ###

S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += 3**cnt
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + 3**cnt) % mod
        cnt += 1
        
        
print(ABC)

### FIXED CODE ###

S = input()

mod = 10**9+7
A = 0
AB = 0
ABC = 0
cnt = 0
for i in range(len(S)):
    if S[i] == "A":
        A += pow(3, cnt, mod)
        A %= mod
    elif S[i] == "B":
        AB += A
        AB %= mod
    elif S[i] == "C":
        ABC += AB
        ABC %= mod
    else:
        ABC = (3*ABC + AB) % mod
        AB = (3*AB + A) % mod
        A = (3*A + pow(3, cnt, mod)) % mod
        cnt += 1
        
        
print(ABC)
### BUGGY CODE ###

from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cost = 0
    for x, y in zip(costX[stateX], costY[stateY]):
        cost += min(x, y)

    if ans[M] > cost:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

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

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

dicts = {}
for i in A:
    for num in make_divisors(i):
        if num in dicts:
            dicts[num]+=1
        else:
            dicts[num]=1


max_value=0
for k,v in dicts.items():
    if v>=N-1 and max_value<k:
        max_value=k

print(max_value)

### FIXED CODE ###

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

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

A = sorted(A)
from collections import Counter
check = Counter(A)
for c,k in check.items():
    if k>=N-1:
        A=[c]



def del_dicts(dicts,i):
    del_list=[]
    for k,v in dicts.items():
        if v<i:
            del_list.append(k)
    for d in del_list:
        del dicts[d]
    return dicts

dicts = {}

for i in range(len(A)):
    if i<=2:
        for num in make_divisors(A[i]):
            if num in dicts:
                dicts[num]+=1
            else:
                dicts[num]=1
    
    else:
        del_list=[]
        
        for k in dicts.keys():
            if A[i]%k == 0:
                dicts[k]+=1
    dicts = del_dicts(dicts,i)
print(max(dicts.keys()))
### BUGGY CODE ###

n = int(input())

s = []
for i in range(n):
    tmp = []
    tmp = list(input())
    tmp.sort()
    s.append("".join(tmp))

cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if i == j:
            pass
        else:
            if s[i] == s[j]:
                cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())

s = []
for i in range(n):
    tmp = []
    tmp = list(input())
    tmp.sort()
    s.append("".join(tmp))

s.sort()

cnt = 0
t_cnt = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        t_cnt += 1
    elif s[i] != s[i+1]:
        if t_cnt > 1:
            t_cnt += 1

            t = 0
            for j in range(t_cnt):
                t += j

            cnt += t
            t_cnt = 0
        else:
            cnt += t_cnt
            t_cnt = 0

    if i == n-2:

        if t_cnt > 1:
            t_cnt += 1

            t = 0
            for j in range(t_cnt):
                t += j

            cnt += t
            t_cnt = 0
        else:
            cnt += t_cnt
            t_cnt = 0

print(cnt)