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

def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]%mod * pow(fact[n-k]*fact[k],mod-2,mod) % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(y,i)-x*nCk(y,i-1))%mod


### FIXED CODE ###

from math import factorial
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]*inv[n-k]*inv[k] % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
inv=[0]*(n+5)
inv[n+1]=pow(factorial(n+1), mod - 2, mod)
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]%mod
for i in xrange(n, -1, -1):
    inv[i] = inv[i+1]*(i+1)%mod
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(x+y,i))%mod
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    dp_tmp = [0]*n
    for kk in range(ss+1,n):
        dp_tmp[kk] =dp[kk]
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp_tmp[l]
    dp_tmp[ss] = tmp/(len(tree[ss])-1) + 1
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp_tmp[b]
        dp_tmp[a] = tmp/len(tree[a]) + 1
    
    return dp_tmp[0]

for i in reversed(range(n-1)):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)






### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    tmp = tmp/(len(tree[ss])-1) + 1
    if tmp > dp[ss]:
        return dp[0]
    else:
        dp[ss] = tmp
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)
### BUGGY CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	for k in range(1,N-K+1):
		if T<=sum(P[k:k+K]):
			T=sum(P[k:k+K])
	print((T+K)/2)

### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def gcd_arr(arr, N):
    if N == 2:
        return gcd(arr[0], arr[1])
    elif N == 1:
        return arr[0]
    else:
        mid = N // 2
        return gcd(gcd_arr(arr[:mid], mid), gcd_arr(arr[mid:], N-mid))

def gcd_arr_with_rm(arr, N, remove = 0):
    return gcd_arr(arr[0:remove] + arr[(remove+1):], N - 1)

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    max_gcd = 1
    for j in range(N):
        tmp = gcd_arr_with_rm(arr, N, remove = j)
        if tmp > max_gcd:
            max_gcd = tmp
    print str(max_gcd)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    left = [0] * (N + 1)
    right = [0] * (N + 1)
    left[0] = 0
    right[N] = 0
    for i in range(1, N+1):
        left[i] = gcd(left[i - 1], arr[i - 1])
    for i in range(N - 1, 0, -1):
        right[i] = gcd(right[i + 1], arr[i])
    max_gcd = 0
    for i in range(N):
        max_gcd = max(max_gcd, gcd(left[i], right[i+1]))
    print str(max_gcd)

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

import math
import bisect
inf=10**12
a,b,q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(a)]+[inf];s.sort()
t=[-inf]+[int(input()) for _ in range(b)]+[inf];t.sort()

for i in range(q):
    x=int(input())
    p=bisect.bisect_left(s,x)
    q=bisect.bisect_left(t,x)

    sl,sr,tl,tr=s[p-1],s[p],t[q-1],t[q]

    sltl=x-min(sl,tl)
    srtr=max(sr,tr)-x
    sltr=min(x-sl*2+tr,-x-sl+tr*2)
    srtl=min(x-tl*2+sr,-x-tl+sr*2)
    print(min(sltl,srtr,sltr,srtl))

### FIXED CODE ###

import math
import bisect
inf=10**12
a,b,q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(a)]+[inf];s.sort()
t=[-inf]+[int(input()) for _ in range(b)]+[inf];t.sort()

for i in range(q):
    x=int(input())
    p=bisect.bisect_left(s,x)
    q=bisect.bisect_left(t,x)

    sl,sr,tl,tr=s[p-1],s[p],t[q-1],t[q]

    sltl=x-min(sl,tl)
    srtr=max(sr,tr)-x
    sltr=min(x-sl*2+tr,-x-sl+tr*2)
    srtl=min(x-tl*2+sr,-x-tl+sr*2)
    print(min(sltl,srtr,sltr,srtl))
### BUGGY CODE ###

a, b, k = list(map(int, input().split()))
arr = [i for i in range(a, b+1)]
if (b-a)*2 < k:
  for i in arr:
    print(i)
  exit()
result = sorted(set(arr[:k] + arr[len(arr)-k:]))
for i in result:
  print(i)


### FIXED CODE ###

a, b, k = list(map(int, input().split()))
list_a = [i for i in range(a, min(a+k, b))]
list_b = [i for i in range(max(a, b+1-k), b+1)]
for i in sorted(set(list_a+list_b)):
  print(i)
### BUGGY CODE ###

def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
    mid = (ok+ng)//2
    dp = [False]*(k+1)
    dp[0] = True
    f = 0
    for j in range(n):
      if j == mid:
        continue
      w = a[j]
      for i in range(k,w-1,-1):
        if dp[i-w]:
          dp[i] = True
          if k-a[mid] <= i < k:
            ng = mid
            f = 1
            break
      if f:
        break
    else:
      ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()
  

### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

import re

pat = "AC"

m_iter = re.finditer(pat, s)

import numpy as np
m_start = np.array([])
for m in m_iter:
    m_start = np.append(m_start, m.start())
    
for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    contain = (l <= m_start) * (m_start <= r-1)
    print(sum(contain))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

t = [0] * (n+1)

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

for i in range(q):
    l, r = lr[i][0]-1, lr[i][1]-1
    print(t[r] - t[l])
### BUGGY CODE ###


d=[0]*13
d[0]=1
mul=1
for c in reversed(input()):
    e=[0]*13
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    d=e[:]
    mul*=10
print(d[5])




### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)
### BUGGY CODE ###

n,m = map(int,input().split())
work = [list(map(int, input().split())) for i in range(n)]
from operator import itemgetter
work = sorted(work,key=itemgetter(1),reverse=True)
count = 0
for i in range(1,m+1):
  for j in range(len(work)):
    if work[j][0] <= i:
      count += work[j][1]
      del work[j]
      break
print(count)



### FIXED CODE ###

import heapq

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

a = [0] * n
b = [0] * n
info = [[] for _ in range(m+1)]

for i in range(n):
    a[i], b[i] = map(int,input().split())
    if a[i] <= m:
        info[a[i]].append(b[i])

l = []
count = 0

for j in range(1,m+1):
    for x in info[j]:
        heapq.heappush(l,-x)
    if l != []:
        count += -heapq.heappop(l)

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

import sys

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

canUse = set(range(N))

ans = 0
while any([len(i) > 0 for i in A]):
    # print("\nDay", ans)
    ans += 1
    canUseNew = set()
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            A[first].pop()
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

print(ans)


### FIXED CODE ###

import sys

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    # print("LC", len(canUse))
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

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

L,R = map( int,input().split() )
ans = ( L * (L+1) ) % 2019  
for i in range(L,R):
    for j in range(i+1, R+1):
        ans = min( ( i * j ) %2019,ans)
print(ans)

### FIXED CODE ###

import math
L,R = map( int,input().split() )
ans = ( L * (L+1) ) % 2019  
for i in range(L,R):
    if ans == 0:
        break
    j = i + 1
    a = ( i * j ) % 2019
    ans = min(a, ans)
    plus = i % 2019
    while(True):
        over = math.ceil( ( 2019 - a ) / plus )
        j = j + over
        if j > R:
            break
        a = ( i * j) % 2019
        ans = min(a,ans)
        if ans == 0:
            break
print(ans)
### BUGGY CODE ###

# YouTube

def max12(x):
    if len(x) < 3:
        return x
    x.sort(reverse=True)
    return x[:2]

n = int(input())
nn = 2 ** n
aa = list(map(int, input().split()))
dp = [[a] for a in aa]
#print(dp)
for i in range(n):
    for j in range(nn - 1, -1, -1):
        if j & 1 << i == 0:
            dp[j + (1 << i)] = max12(dp[j + (1 << i)] + dp[j])
#    print(dp)
mx = 0
for dk in dp[1:]:
    mx = max(mx, sum(dk))
    print(mx)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Top2:
    def __init__(self,x=-1,y=-1):
        if x<y:x,y=y,x
        self.val=[x,y]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        return self

n=II()
aa=LI()
dp=[Top2(a) for a in aa]

for i in range(n):
    for j in range((1<<n)-1,-1,-1):
        if j>>i&1:continue
        dp[j|1<<i]+=dp[j]

mx=-1
for j in range(1,1<<n):
    mx=max(mx,int(dp[j].s))
    print(mx)
### BUGGY CODE ###

s = input()
n = len(s)
mod = 2019

total = [0] * (n + 1)
cnt = [0] * mod
cnt[0] = 1

for i in range(1, n + 1):
    now = int(s[n - i:])
    now %= mod
    cnt[now] += 1

ans = 0
for i in cnt:
    ans += i * (i - 1) // 2

print(ans)


### FIXED CODE ###

s = input()
n = len(s)

mod = 2019
cnt = [0] * mod
cnt[0] = 1
digit = 1
now = 0

for i in range(1, n + 1):
    now += int(s[-i]) * digit
    digit *= 10
    digit %= mod
    now %= mod
    cnt[now] += 1

ans = 0
for i in cnt:
    ans += i * (i - 1) // 2

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

print(sum([i for i in range(int(input()))]))

### FIXED CODE ###

N = int(input())

print(str(int((N-1)*N//2)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

from functools import lru_cache
@lru_cache(maxsize=None)
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

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

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

A = [[0]*(W+1)]
for i in range(H):
    A.append([0] + list(map(int, input().split())))

B = [[0]*(W+1)]
for i in range(H):
    B.append([0] + list(map(int, input().split())))

C = [[0 for j in range(W+1)] for i in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j] = A[i][j] - B[i][j]

dp = [[set() for j in range(W+1)] for i in range(H+1)]
dp[0][1] = set([0])
dp[1][0] = set([0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in list(dp[i-1][j]):
            dp[i][j].add(k + C[i][j])
            dp[i][j].add(k - C[i][j])
        for k in list(dp[i][j-1]):
            dp[i][j].add(k + C[i][j])
            dp[i][j].add(k - C[i][j])

ans = list(dp[H][W])
ans = [abs(i) for i in ans]
print(sorted(ans)[0])

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

A = [[0]*(W+1)]
for i in range(H):
    A.append([0] + list(map(int, input().split())))

B = [[0]*(W+1)]
for i in range(H):
    B.append([0] + list(map(int, input().split())))

C = [[0 for j in range(W+1)] for i in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1<<6400
dp[1][0] = 1<<6400
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] = dp[i-1][j]<<C[i][j] | dp[i-1][j]>>C[i][j] | dp[i][j-1]<<C[i][j] | dp[i][j-1]>>C[i][j]

for i in range(6400,INF):
    if dp[H][W]>>i & 1:
        print(i-6400)
        sys.exit()
### BUGGY CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295

def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    q = [(sy, sx, 0)]
    t = max(W, H)
    n = 1
    i = 0
    while n > 0:
        r, c, k = q[i]
        n -= 1
        visited[r][c] = True
        t = min(t, r, H - 1 - r, c, W - 1 - c)

        if t == 0:
            print(1)
            return

        for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                q.append((nr, nc, k + 1))
                n += 1
        i += 1

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


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

def Lucas(n):
	if n==0:
		return 2
	elif n==1:
		return 1
	else:
		return Lucas(n-1)+Lucas(n-2)

print(Lucas(int(input())))

### FIXED CODE ###

dp=[0 for _ in range(88)]

dp[0]=2
dp[1]=1

for i in range(88):
	if i>1:
		dp[i]=dp[i-1]+dp[i-2]

print(dp[int(input())])
### 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)

def makeState(state, sign):
    ret = 0
    for s in state[::-1]:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = makeState(state, 1)
    stateY = makeState(state, 2)

    cost = 0
    for i, (x, y, p) in enumerate(XYP):
        cost += min(costX[stateX][i], costY[stateY][i])

    M = N - state.count(0)
    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()