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

def gcdf(a,n,gcdv):
#    print("a:",a)
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(n):
            a[i]=a[i]%a0
            if a[i]==0:
                a[i]=a0
            if ramin>a[i]:
                ramin=a[i]
            if ramin<=gcdv:
                return gcdv
        a0=min(a)
#        print("a:",a,ramin)
    return ramin


#n=2
#a=[1000000000, 1000000000]
#n=4
#a=[15, 18, 24, 36]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
    a.sort()
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy,n-1,gcdv)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)


### FIXED CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
mem=set()
c=0
for i in range(N):
    if i > 0:
        if P[i] <= min(mem):
            c+=1
    else:
        c+=1
    mem.add(P[i])
print(c)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
mini=(10**5)*2
c=0
for i in range(N):
    if P[i] <= mini:
        mini=P[i]
        c+=1
print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

H,W = map(int,input().split())
S = [input() for _ in range(H)]

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#':
      dfs(i,j)
      ans += numb * numw
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

H,W = map(int,input().split())
S = [input() for _ in range(H)]

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#' and not seen[i][j]:
      dfs(i,j)
      ans += numb * numw
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=object)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n, dtype=object)
    while k:
        if k % 2:
            answer = np.dot(answer, can)
        can = np.dot(can, can)
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = [[int(c) for c in input().split()] for _ in range(n)]
    can = np.matrix(can, 'O')
    
    # for i in range(n):
    #     for j, e in enumerate(int(c) for c in input().split()):
    #         can[i, j] = e

    b = np.eye(n, n, 0, 'O')
    while k:
        b = [b, b*can % MOD][k & 1]
        can = can*can % MOD
        k >>= 1

    print(b.sum() % MOD)

    # answer = np.eye(n, dtype=int)
    # while k:
    #     if k % 2:
    #         answer = np.dot(answer, can) % MOD
    #     can = np.dot(can, can) % MOD
    #     k //= 2

    # total = 0
    # for i in range(n):
    #     for j in range(n):
    #         total += answer[i,j]
    #         if total >= MOD:
    #             total -= MOD

    # print(total)


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

N, A, B = input().split()
N = int(N)
A = int(A)
B = int(B)

L = []
i = 0
k = 0
j = 0

for k in range(10**100):
    for i in range(A):
        L.append('b')
    for j in range(B):
        L.append('r')

    if len(L) >= N:
        L = L[0:N]
        print(L.count('b'))
        break

### FIXED CODE ###

N, A, B = map(int , input().split())
 
L = []
i = 0
k = 0
j = 0
P = N // (A + B)
Q = N % (A + B)

if A > Q:
    print((P * A) + Q)
else:
    print((P * A) + A)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [0 for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [[0, dic[0]]]
    visit[0] = 1
    while any(x == 0 for x in visit):
        for i in range(len(next_visit)):
            t = next_visit.pop(0)
            for s in t[1]:
                if visit[s] == 0:
                    point[s] += point[t[0]]
                    visit[s] = 1
                    next_visit.append([s, dic[s]])
    print(" ".join(map(str, point)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np

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

dp = np.zeros(W+1, np.int64)

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)
print(dp[-1])

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(W+1, np.int64)

for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w]+v, out=dp[w:])

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

N=int(input())
S=[]
count=[0]*N
A=[]

for i in range(N):
	S.append(input())
    
S=sorted(S)

for i in range(N):
	for j in range(N):
		if S[i]==S[j]:
			count[i]+=1              

for i in range(N):
	if max(count)==count[i]:
		A.append(S[i])
A=sorted(set(A))

for i in range(len(A)):
	print(A[i])


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
from collections import Counter
import numpy as np
n=int(input())
S=[]
for i in range(n):
    S.append(input())
s=Counter(S)
keys, values = zip(*s.most_common())

values=np.array(values)
index=np.where(values==np.max(values))
answer=[]
for i in index[0]:
    answer.append(keys[i])
answer.sort()
for i in answer:
    print(i)
### BUGGY CODE ###

N = int(input())
S = input()

EW = [] # 「EW」となっている部分のEの座標
if S[0] == "W":
    EW.append(-1)
for i in range(N-1):
    if S[i]=="E" and S[i+1]=="W":
        EW.append(i)
if S[N-1] == "E":
    EW.append(N-1)

ans = 1000000
for ew in EW:
    cnt = 0
    for j in range(0, ew):
        if S[j] == "W":
            cnt += 1
    for k in range(ew+2, N):
        if S[k] == "E":
            cnt += 1
    if ans > cnt:
        ans = cnt

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

w_rotation = 0
e_rotation = S.count("E")
ans = w_rotation + e_rotation
for i in range(N):
    if S[i] == "W":
        w_rotation += 1
    else: # S[i] == "E":
        e_rotation -= 1
    if ans > w_rotation + e_rotation:
        ans = w_rotation + e_rotation

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

N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] += i + 1
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans % P)

### FIXED CODE ###

N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] = (X[a] + i + 1) % P
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans)
### BUGGY CODE ###

s=input()
n=int(input())
cnt=0
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            s=c+s
        else:
            s+=c
    else:
        cnt+=1
if cnt%2==0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s=input()
n=int(input())
cnt=0
l=[]
r=[]
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            l.append(c)
        else:
            r.append(c)
    else:
        cnt+=1
if cnt%2==0:
    print(''.join(l[::-1])+s+''.join(r))
else:
    print(''.join(r[::-1])+s[::-1]+''.join(l))
### BUGGY CODE ###

"""
二部グラフの問題。
同じ色に塗られた任意の2頂点について、その距離が偶数である。
-> this means that neighbor nodes' color must be another color.
"""
import sys
sys.setrecursionlimit(200000)
N = int(input())
edges = [{} for _ in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    edges[u][v]=w%2
    edges[v][u]=w%2

color = [0 for _ in range(N+1)]
path = {}
def f(n,c):
    color[n]=c
    path[n]=""
    for v,d in edges[n].items():
        if v not in path:
            nextC = c
            if d == 1:
                nextC = (nextC+1)%2
            f(v,nextC)
f(1,0)

for i in range(1,N+1):
    print(color[i])

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush(que,(nxC,nx))

    for i in range(1,N+1):
        print(colors[i])

main()
### BUGGY CODE ###

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
def kakeru(ary):
    result = 1
    for i in ary:
        result *= i
    return result

tmp =  kakeru(A[0:k])
point = tmp
for i in range(n-k):
    point = point * A[k+i] / A[i]
    if point > tmp:
        tmp = point
        print('Yes')
    else:
        tmp = point
        print('No')

### FIXED CODE ###

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(n-k):
    if A[k+i] > A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N-1):
        for j in range(i+1,N):
            for k in range(N):
                if i == k or j == k or A[i][k] == 0 or A[j][k] == 0:
                    continue
                
                if A[i][j] == A[i][k]+A[j][k]:
                    A[i][j] = 0
                    A[j][i] = 0
                elif A[i][j] > A[i][k]+A[j][k]:
                    print(-1)
                    return
    
    answer = 0
    for i in range(N):
        answer += sum(A[i])
    print(answer//2)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            ## impossible
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

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

n =int(input())
a = list(map(int, input().split()))
b = 1
for i in range(0,n):
  b *= a[i]
if b > 10**18:
  print(-1)
else:
  print(b)

### FIXED CODE ###

n =int(input())
a = list(map(int, input().split()))
b = 1
if 0 in a:
  print(0)
else:
  for i in range(0,n):
    b *= a[i]
    if b > 10**18:
      print(-1)
      break
  if b <= 10**18:
    print(b)
### BUGGY CODE ###

l = {".":1,"*":-10000}
def x(a):
	m=0
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			d=e-c+1
			for r in N:
				p[r]+=l[a[r][e]]
			m=max(P(p,d),m)
	return int(m**0.5)
	
def P(a,d):
	m=0
	for i in range(n-d+1):
		k=sum(a[i:i+d])
		m=max(m,k)
	return m
    
while True:
	n=input()
	if n==0:break
	N=range(n)
	print x([raw_input() for i in N])

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(1,N):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
if A.count(0) > 0:
    print(0)
else:
    ans = A[0]
    flag = 0
    for i in range(1,N):
        ans *= A[i]
        if ans > 10**18:
            flag += 1
            print(-1)
            break
    if flag == 0:
        print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
dict_left = {}
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for x in range(2**N):
    red_left = ''
    blue_left = ''
    B = bin(x)[2:]
    B = B.zfill(N)
    for i in range(N):
        if int(B[i]) == 1:
            red_left += S_left[i]
        else:
            blue_left += S_left[i]
    tango = red_left + '|' + blue_left
    if tango in dict_left:
        dict_left[tango] += 1
    else:
        dict_left[tango] = 1
ans = 0
for x in range(2**N):
    red_right = ''
    blue_right = ''
    B = bin(x)[2:]
    B = B.zfill(N)
    for i in range(N):
        if int(B[i]) == 1:
            red_right += S_right[i]
        else:
            blue_right += S_right[i]
    tango = blue_right + '|' + red_right
    if tango in dict_left:
        ans += dict_left[tango]

print(ans)

### FIXED CODE ###

from collections import Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for B in product(range(2),repeat = N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    for i in range(N):
        if B[i]:
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)
### BUGGY CODE ###

N = int(input())
vote = [1,1]
for i in range(N):
    ratio = list(map(int, input().split()))
    for j in range(2):
        while(vote[j] % ratio[j] != 0):
            vote[j] += 1
    if vote[0] * ratio[1] < vote[1] * ratio[0]:
        while (vote[0] * ratio[1] != vote[1] * ratio[0]):
            vote[0] += 1;
    if vote[0] * ratio[1] > vote[1] * ratio[0]:
        while (vote[0] * ratio[1] != vote[1] * ratio[0]):
            vote[1] += 1;
print(vote[0] + vote[1])

### FIXED CODE ###

N = int(input())
vote = [1,1]
for i in range(N):
    ratio = list(map(int, input().split()))
    for j in range(2):
        while(vote[j] % ratio[j] != 0):
            vote[j] += 1
    if vote[0] * ratio[1] < vote[1] * ratio[0]:
        vote[0] = vote[1] // ratio[1] * ratio[0];
    if vote[0] * ratio[1] > vote[1] * ratio[0]:
        vote[1] = vote[0] // ratio[0] * ratio[1];
print(vote[0] + vote[1])
### BUGGY CODE ###

n = int(input())

s = []
cnt = [0] * n
_max = 0
for i in range(n):
  tmp = input()
  if tmp not in s:
    s.append(tmp)
  else:
    cnt[s.index(tmp)] += 1
    if _max < cnt[s.index(tmp)]:
      _max = cnt[s.index(tmp)]
    
results = []
for i in range(len(s)):
  if cnt[i] == _max:
    results.append(s[i])

results.sort()
for result in results:
  print(result)

### FIXED CODE ###

n = int(input())

dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

_max = 0
for v in dic.values():
  if _max < v:
    _max = v
dic2 = sorted(dic.items())

for (k,v) in dic2:
  if v == _max:
    print(k)
### 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]
P = [p for _, _, p 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 = [[] for _ in range(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

    ans[M].append((costX[stateX], costY[stateY]))

for xy in ans:
    res = INF
    for a in xy:
        res = min(res, sum(map(min, zip(*a))))
    print(res)


### 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()