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

import itertools
from bisect import bisect_left

def index(a, x):
    'Find leftmost index of item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return i
    return False

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = []
    for i,j,k in itertools.combinations(range(N), 3):
        if i < j < k:
            s = int(str(lst[i])+str(lst[j])+str(lst[k]))

            idx = bisect_left(a, s)

            if idx == len(a):
                a.append(s)
            
            elif a[idx] != s:
                a.insert(idx, s)

    print(len(a))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = ['{:03d}'.format(i) for i in range(1000)]
    count = 0
    for i in range(len(a)):
        m,n,o = 0,1,2
        s = list(a[i])
        while m < n < o < len(lst) :
            if s[0] != lst[m]:
                m += 1
                n += 1
                o += 1
            elif s[1] != lst[n]:
                n += 1
                o += 1
            elif s[2] != lst[o]:
                o += 1
            else:
                count += 1
                break

    print(count)

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

import math

k = int(input())
m = 0
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            m = math.gcd(i,j)
            ans += math.gcd(m,l)

print(ans)


### FIXED CODE ###

import math

k = int(input())
ans = 0
m = 0
for a in range(1,k+1):
    for b in range(a+1,k+1):
        for c in range(b+1, k+1):
            m = math.gcd(a,b)
            ans += 6*math.gcd(m,c)
for a in range(1,k+1):
    for c in range(a+1,k+1):
        ans += 3*math.gcd(a,c)
for c in range(1,k+1):
    for a in range(c+1,k+1):
        ans += 3*math.gcd(a,c)
for a in range(1,k+1):
    ans += a
print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

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

import itertools

n = int(input())
l = list(itertools.combinations_with_replacement([0, 1], n))[::-1]
ll = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        ll[i][x-1] = y

for i in range(len(l)):
    l2 = list(set(itertools.permutations(l[i])))
    for lst in l2:
        flag = False
        for j in range(n):
            for k in range(n):
                if ll[j][k] == -1: continue
                if lst[j] == 1:
                    if lst[k] != ll[j][k]:
                        flag = True
                        break
                elif lst[j] == 0:
                    if lst[k] == ll[j][k]:
                        flag = True
                        break
            if flag:
                break
        if not flag:
            print(lst.count(1))
            exit()
print(0)


### FIXED CODE ###

from itertools import product
N=int(input())
XYs = []
for i in range(N):
    A = int(input())
    XYs.append([tuple(map(int, input().split())) for _ in range(A)])

n=0
for ts in product(*[[1, 0] for _ in range(N)]):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in XYs[i]):
                break
    else:
        n=max(n,sum(ts))
print(n)
### BUGGY CODE ###

A, B, K = map(int, input().split())

while(K):
    if(A >=1):
        A -= 1
    elif(B >=1):
        B -= 1
    K -= 1
print(A, end=" ")
print(B)

### FIXED CODE ###

A, B, K = map(int, input().split())

if(K <= A+B):
    print(A-K if A > K else 0, end=" ")
    print(B-(K-A) if A < K else B)
else:
    print(0, end=" ")
    print(0)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(k):
    if a != 0:
        a -= 1
    elif b != 0:
        b -= 1
    else:
        break
print(str(a) + " " + str(b))

### FIXED CODE ###

a, b, k = map(int, input().split())
a = a - k
if a < 0:
    b = b + a
    a = 0
    b = max(0, b)
print(a, b)
### BUGGY CODE ###

from collections import Counter

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

for k in range(N):
    counter = 0
    l = Counter([A[i] for i in range(N) if i!=k])
    for v in l.values():
         counter += v*(v-1)//2
    print(counter)

### FIXED CODE ###

from collections import Counter

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

l = Counter(A)
ans = sum([v*(v-1)//2 for v in l.values()])

for a in A:
    print(ans - l[a]*(l[a]-1)//2 + (l[a]-1)*(l[a]-2)//2)
### BUGGY CODE ###

N = int(input())
H_list = input().split(" ")
H_LIST = []

for i in range(0, N):
    H_LIST.append(int(H_list[i]))
 
max_count = 0

for i in range(0, N):
    S = H_LIST[i]
    count = 0
    for j in range(i + 1, N):
        if S >= H_LIST[j]:
            S = H_LIST[j]
            count += 1
        else:
            break
    if max_count < count:
        max_count = count

print(max_count)


### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
hs = [0] + list(map(int, input().split())) 


max_val = sum([max(hs[i + 1] - hs[i], 0) for i in range(n)])
dp = [[max_val for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):	
		dp[i][j] = min([dp[i - 1][l] + max(hs[j] - hs[l], 0) for l in range(j)])

print(min([dp[n - k][l] for l in range(n + 1)]))

### FIXED CODE ###

n, k = list(map(int, input().split()))
hs = [0] + list(map(int, input().split())) 


max_val = sum([max(hs[i + 1] - hs[i], 0) for i in range(n)])
dp = [[max_val for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):	
		dp[i][j] = min([dp[i - 1][l] + max(hs[j] - hs[l], 0) for l in range(j)])

print(min([dp[n - k][l] for l in range(n + 1)]))
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

n=int(input())
*a,=map(int,input().split())

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b

@lru_cache()
def f(i,j,k):
    v=0
    if not i+j+k:return 0.0
    v+=n
    if i:v+=f(i-1,j,k)*i
    if j:v+=f(i+1,j-1,k)*j
    if k:v+=f(i,j+1,k-1)*k
    v/=i+j+k
    return v

print(f(k1,k2,k3))

### FIXED CODE ###

n=int(input())

b=[0,0,0]
for i in map(int,input().split()):
    b[i-1]+=1
k1,k2,k3=b
dp=[[[None]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]
dp[0][0][0]=0

for k in range(k3+1):
    for j in range(k2+k3+1-k):
        for i in range(k1+k2+k3+1-j-k):
            if not i+j+k:continue
            dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)

print(dp[k1][k2][k3])
### BUGGY CODE ###

global memo
global ans

def judge_dup(list1,list2):#list1とlist2に共通した要素がある場合は１、ない場合は０
    tmp_list1=list(set(list1))
    tmp_list2=list(set(list2))
    judge=tmp_list1 + tmp_list2
    if(len(tmp_list1) + len(tmp_list2) == len(set(judge))):
        return 0
    else:
        return 1


def longest_common(data1,ind1,data2,ind2):
    #data1[ind1],data2[ind2]を先頭とする２つの部分文字列の最長common文字列の長さを返す
    if(len(data1) <=ind1 or len(data2) <=ind2):
        return 0
    if(memo[ind1][ind2]!=-1):
        return memo[ind1][ind2]

    tmp_data1=data1[ind1:]
    tmp_data2=data2[ind2:]
    tmp_max=0
    for i in range(len(tmp_data1)):
        x=tmp_data1[i]
        for j in range(len(tmp_data2)):
            if(x==tmp_data2[j]):
                if(judge_dup(tmp_data1[:i],tmp_data2[:j])==0):
                    #注目する文字以前に共通する文字があったら調査する意味なし
                    tmp = longest_common(data1,ind1+i+1,data2,ind2+j+1)
                    if(tmp_max < tmp +1):
                        tmp_max=tmp+1
                break
    
    memo[ind1][ind2]=tmp_max
    global ans
    if(ans < tmp_max):
        ans =tmp_max
    return tmp_max
            
    






                





n=int(input())


for loop in range(n):
    ans=0
    data1=input()
    data2=input()
    data1=list(data1)
    data2=list(data2)

    memo=[[-1]*len(data2) for i in range(len(data1))]
#memo[n][m]は、data1[n]、data2[m]それぞれを先頭とする
#部分文字列の最長common文字列の長さを格納する
    longest_common(data1,0,data2,0)
    print(ans)


### FIXED CODE ###





def lsc(str1,str2):
    table1=[0]*(len(str2)+1)
    for i in range(len(str1)):
       table2=table1[:]
       for j in range(len(str2)):
            if(str1[i] == str2[j]):
               table1[j+1] = table2[j] +1
            else:
                if(table1[j+1] < table1[j]):
                    table1[j+1]=table1[j]
    return table1[-1]




n=int(input())

for loop in range(n):
    str1=input()
    str2=input()
    print(lsc(str1,str2))
### BUGGY CODE ###

N=int(input())
ans=1
for i in range(1,N+1):
	ans*=i

print(ans%(10**9+7))

### FIXED CODE ###

import math
N=int(input())
ans=math.factorial(N)%(10**9+7)
print(ans)
### BUGGY CODE ###

def lcs(X, Y):
    m = len(X) + 1
    n = len(Y) + 1
    c = [[0] * n for _ in xrange(m)]
    X = ' ' + X
    Y = ' ' + Y
    maxl = 0
    for i in xrange(1,m):
        for j in xrange(1,n):
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
            #elif c[i-1][j] >= c[i][j-1]:
            #    c[i][j] = c[i-1][j]
            else:
                c[i][j] = max(c[i][j-1],c[i-1][j])
        maxl = max(maxl, c[i][j])
    print maxl
    return 0

def main():
    q = int(raw_input())
    for i in xrange(q):
        X = raw_input()
        Y = raw_input()
        lcs(X,Y)
    return 0

main()

### FIXED CODE ###

def lcs(x,y):
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in xrange(a):
        e = x[i]
        x2 = x1+[]
        for j in xrange(b):
            if e == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print max(x1)
    return 0

def main():
    q = int(raw_input())
    for i in xrange(q):
        X = raw_input()
        Y = raw_input()
        lcs(X,Y)
    return 0

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
flg = True
t = 0

while flg:
    p = -1
    for i in range(n):
        if a[i] % 2 == 0:
            if p == -1:
                p = i
            else:
                if a[p] < a[i]:
                    p = i

    for i in range(n):
        if i != p:
            a[i] *= 3
        else:
            a[i] = a[i] // 2
    
    if p == -1:
        flg = False
    else:
        t += 1

print(t)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
t = 0

for i in range(n):
    while a[i] % 2 == 0:
        a[i] = a[i] // 2
        t += 1
        
print(t)
### BUGGY CODE ###

import numpy as np
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = np.array(input().split(), dtype=np.int64)
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)
for i in range(K):
    # cnt = [0]*N
    cnt = np.zeros_like(A)
    for j, x in enumerate(A):
        # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
        l = max(j-x,0)
        r = min(j+x+1,N)
        cnt[l] += 1
        if r<N:
            cnt[r] -= 1
        # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
        #     cnt[k] += 1
    # print(nd)
    # A = np.count_nonzero(nd, axis=0)
    # print(cnt)
    A = np.cumsum(cnt)
    if A[0] == A[N-1] == N:
        break
    # print(*A)

print(*A)

### FIXED CODE ###

import numpy as np
from numba import njit
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = np.array(input().split(), dtype=np.int64)
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)

# @njit('(i8[::1],)', cache=True)
@njit(cache=True)
def loop(A):
    for i in range(K):
        # cnt = [0]*N
        cnt = np.zeros_like(A)
        for j, x in enumerate(A):
            # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
            l = max(j-x,0)
            r = min(j+x+1,N)
            cnt[l] += 1
            if r<N:
                cnt[r] -= 1
            # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
            #     cnt[k] += 1
        # print(nd)
        # A = np.count_nonzero(nd, axis=0)
        # print(cnt)
        A = np.cumsum(cnt)
        if A[0] == A[N-1] == N:
            break
        # print(*A)
    return A

A = loop(A)
print(*A)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(S, start):
    H = len(S)
    W = len(S[0])
    stack = [start]
    closed = set()
    r = 0
    while stack:
        next_stack = []
        for s in stack:
            closed.add(s)
            for d in (-1, 1):
                for p in ((s[0] + d, s[1]), (s[0], s[1] + d)):
                    if p in closed:
                        continue
                    if p[0] < 0 or H <= p[0] or p[1] < 0 or W <= p[1]:
                        continue
                    if S[p[0]][p[1]] == "#":
                        continue
                    next_stack.append(p)
        stack = next_stack
        r += 1
    return r - 1


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]

    res = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            res = max(res, f(S, (h, w)))
    print(res)

        
if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(S, start):
    H = len(S)
    W = len(S[0])
    stack = [start]
    closed = set()
    r = 0
    while stack:
        next_stack = []
        for s in stack:
            if s in closed:
                continue
            closed.add(s)
            for d in (-1, 1):
                for p in ((s[0] + d, s[1]), (s[0], s[1] + d)):
                    if p in closed:
                        continue
                    if p[0] < 0 or H <= p[0] or p[1] < 0 or W <= p[1]:
                        continue
                    if S[p[0]][p[1]] == "#":
                        continue
                    next_stack.append(p)
        stack = next_stack
        r += 1
    return r - 1


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]

    res = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            res = max(res, f(S, (h, w)))
    print(res)

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

from collections import defaultdict
        

obj = defaultdict(lambda: 1)

N=int(input())
ANA=[]
L=[]
for i in range(N):
    k=sorted([x for x in input()])
    if k in L:
        obj["".join(k)]+=1
    else:
        L.append(k)

result=0
for i in obj.values():
    if i and i-1:
        result+=i*(i-1)/2
    
print(int(result))


### FIXED CODE ###

from collections import defaultdict
        

obj = defaultdict(lambda: 1)

N=int(input())
ANA=[]
L=set([])
for i in range(N):
    k="".join(sorted([x for x in input()]))
    if k in L:
        obj[k]+=1
    else:
        L.add(k)

result=0
for i in obj.values():
    if i and i-1:
        result+=i*(i-1)/2
    
print(int(result))
### BUGGY CODE ###

S = input()
s = len(S)
mod = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(s)]
table = [[0] * 10 for _ in range(13)]
for i in range(13):
    for j in range(10):
        table[i][j] = (i * 10 + j) % 13

if S[0] == '?':
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(S[0]) % 13] += 1

for i in range(1, s):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][table[j][k]] = (dp[i][table[j][k]] + dp[i - 1][j]) % mod
    else:
        t = int(S[i])
        for j in range(13):
            dp[i][table[j][t]] = dp[i - 1][j]

print(dp[-1][5] % mod)

### FIXED CODE ###

def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(s)]

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

    print(dp[-1][5] % mod)


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

k, s = map(int, input().split())
ans = []
for i in range(k+1):
    for j in range(min(k+1,s-i+1)):
        h = s- i- j
        if 0<= h <= k:
            ans.append([i, j, h])
print(len(ans))

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(min(k+1,s-i+1)):
        h = s- i- j
        if 0<= h <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
 
## BFS
 
#入力受け取り
N, Q = mi()
x = li2(N-1)
 
cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1
 
#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)
 
global ans
ans = [0]*N
 
def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)
 
dfs(0, 0)
 
for i in range(N):
    print(ans[i], '', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


for i in range(1, N+1):
    print(ans[i], ' ', end='')
'''

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')
### BUGGY CODE ###

INF = float("inf")

N, *XYP = map(int, open(0).read().split())
XYP = list(zip(*[iter(XYP)] * 3))

def solve(XP):
    M = len(XP)
    XP.sort()

    dp = [[INF] * (M + 1) for _ in range(M + 1)]
    dp[0][0] = 0

    for i, (x, p) in enumerate(XP):
        dp[i + 1][0] = dp[i][0] + abs(x) * p

    for l, dpl in enumerate(dp[:M]):
        for r in range(l + 1, M + 1):
            val = INF
            for lx, _ in XP[l:r]:
                cur = 0
                for x, p in XP[l:r]:
                    cur += p * min(abs(x - lx), abs(x))
                val = min(val, cur)

            for i in range(1, M + 1):
                dp[r][i] = min(
                    dp[r][i],
                    val + dpl[i - 1]
                )

    res = [INF] * (N + 1)
    res[:M + 1] = dp[M]
    return res


A = [INF] * (N + 1)
for state in range(1 << N):
    XP, YP = [], []
    for i, (x, y, p) in enumerate(XYP):
        if (state >> i) & 1:
            XP.append((x, p))
        else:
            YP.append((y, p))

    X, Y = solve(XP), solve(YP)
    for i in range(N + 1):
        for j in range(N + 1 - i):
            A[i + j] = min(A[i + j], X[i] + Y[j])

for a in A:
    print(a)

### FIXED CODE ###

INF = float("inf")

N, *XYP = map(int, open(0).read().split())
XYP = list(zip(*[iter(XYP)] * 3))

def solve(XP):
    M = len(XP)
    XP.sort()

    dp = [[INF] * (M + 1) for _ in range(M + 1)]
    dp[0][0] = 0

    for i, (x, p) in enumerate(XP):
        dp[i + 1][0] = dp[i][0] + abs(x) * p

    for l, dpl in enumerate(dp[:M]):
        for r in range(l + 1, M + 1):
            val = INF
            for lx, _ in XP[l:r]:
                cur = 0
                for x, p in XP[l:r]:
                    cur += p * min(abs(x - lx), abs(x))
                val = min(val, cur)

            for i in range(1, M + 1):
                dp[r][i] = min(
                    dp[r][i],
                    val + dpl[i - 1]
                )

    res = [INF] * (N + 1)
    res[:M + 1] = dp[M]
    return res


A = [INF] * (N + 1)
for state in range(1 << N):
    XP, YP = [], []
    for i, (x, y, p) in enumerate(XYP):
        if (state >> i) & 1:
            XP.append((x, p))
        else:
            YP.append((y, p))

    X, Y = solve(XP), solve(YP)
    for i in range(N + 1):
        for j in range(N + 1 - i):
            A[i + j] = min(A[i + j], X[i] + Y[j])

for a in A:
    print(a)