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

#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x):
    Q = []
    while forest[x] != x:
        x = forest[x]
        Q.append(x)
    """
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    """
    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)
    


### FIXED CODE ###

#coding:utf-8

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

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for i in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return 1
        return 0


cnt = 0
tree = UnionFind3(n)
for i in range(m):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)

for i in range(n):
    a = tree.find(i)
    b = tree.find(List[i]-1)
    if a == b:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
wv = np.array([list(map(int, input().split())) for i in range(n)])

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i - 1, 0], wv[i - 1, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n])


### FIXED CODE ###

import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


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

# coding: utf-8
# Your code here!
from itertools import chain
from collections import Counter

N, M = map(int,input().split())
li = [list(map(int,input().split())) for i in range(M)]
arr = [[j for j in range(li[k][0], li[k][1] + 1)] for k in range(M)]
set_arr = list(chain.from_iterable(arr))
arr_duplicate = [l for l in Counter(set_arr).values() if l == M]
print(len(arr_duplicate))


### FIXED CODE ###

# coding: utf-8
# Your code here!

N, M = map(int,input().split())
li = [list(map(int,input().split())) for i in range(M)]
L = [li[j][0] for j in range(M)]
R = [li[k][1] for k in range(M)]
ctr = 0

if min(R) - max(L) >= 0:
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
s = input()

array = list(s)
r = len(s.replace('W', ''))
w = n - r
ans = min(r,w)

i = 0
j = len(array)-1
count = 0

while True:
  while len(array) > i and array[i] == 'R':
    i += 1
    
  while j > 0 and array[j] == 'W':
    j -= 1
    
  if(i>j):
    break
    
  array[i], array[j] = array[j], array[i]
  count += 1
  
print(min(count, ans))

### FIXED CODE ###

n = int(input())
s = input()

array = list(s)
r = len(s.replace('W', ''))
w = n - r
ans = min(r,w)

i = 0
j = len(array)-1
count = 0
for i in range(r):
  if array[i] == 'W':
    count += 1
  
print(min(count, ans))
### BUGGY CODE ###

def search(keys,dic,now,goal):
    if len(keys)==now:
        if goal==0:
            return True
        else:
            return False
    k=keys[now]
    for i in range(dic[k]+1):
        if search(keys,dic,now+1,goal-k*i+k*(dic[k]-i)):
            return True
    return False

s=input()+'T'
x,y=list(map(int,input().split()))
xdic={}
ydic={}

flag='x+'
ini=0
tmp=0
for c in s:
    if c =='F':
        tmp+=1
    else:
        if flag=='x':
            if xdic.get(tmp,0)==0:
                xdic[tmp]=1
            else:
                xdic[tmp]+=1
        elif flag=='y':
            if ydic.get(tmp,0)==0:
                ydic[tmp]=1
            else:
                ydic[tmp]+=1
        else:
            ini=tmp
        tmp=0
        if flag=='y':
            flag='x'
        else:
            flag='y'
if xdic.get(0,0)!=0:
    xdic.pop(0)
if ydic.get(0,0)!=0:
    ydic.pop(0)
if search(list(xdic.keys()),xdic,0,x-ini) and search(list(ydic.keys()),ydic,0,y):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s=input()+'TE'
x,y=list(map(int,input().split()))

ini = s.find('T')
s=s[ini+1:]

is_y=1
point=[set([ini]),set([0])]

while len(s)>1:
    tmp=s.find('T')
    if tmp != 0:
        set_=set()
        for z in point[is_y]:
            set_.add(z+tmp)
            set_.add(z-tmp)
        point[is_y]=set_
    is_y+=1
    is_y%=2
    s=s[tmp+1:]

if x in point[0] and y in point[1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
S = input()

R = []
G = []
B = []
for i, s in enumerate(S):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)

count = 0
for r in R:
    for g in G:
        for b in B:
            l = sorted([r, b, g])
            if (l[0] + l[2])/2 != l[1]:
                count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

cnt = 0
for i in range(n):
    j = 1
    while i + 2*j <= n-1:
        if s[i] != s[i+j] and s[i+j] != s[i+2*j] and s[i+2*j] != s[i]:
            cnt += 1
        j += 1

print(r*g*b-cnt)
### BUGGY CODE ###


def main():
    M = 2019
    s = input()

    x = 0
    dp = [0] * M
    for c in s:
        c = int(c)
        dp2 = [0] * M
        for j in range(M):
            dp2[(j*10 + c) % M] += dp[j]
        dp2[c] += 1
        dp = dp2
        x += dp[0]
    print(x)

main()


### FIXED CODE ###

M = 2019
dp = [0] * M
s = input()
x = 0
for c in s:
    c = int(c)
    dp2 = [0] * M
    for j in range(M):
        index = (j*10 + c) % M
        dp2[index] += dp[j]
    dp = dp2
    dp[c] += 1
    x += dp[0]
print(x)
### BUGGY CODE ###

from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

dot_comb = combinations(dots, K)

ans = 10 ** 37
for dots in dot_comb:
    x_min = 10 ** 9 + 1
    x_max = (-1) * (10 ** 9 + 1)
    y_min = 10 ** 9 + 1
    y_max = (-1) * (10 ** 9 + 1)
    for dot in dots:
        x, y = dot
        x_min = min(x_min, x)
        x_max = max(x_max, x)
        y_min = min(y_min, y)
        y_max = max(y_max, y)
    ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)


### FIXED CODE ###

from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 10 ** 37
for i in range(N):
    for j in range(i+K-1, N):
        width = dots[j][0] - dots[i][0]
        y = sorted([l for _, l in dots[i:j+1]])
        for a, b in zip(y, y[K-1:]):
            height = b - a
            ans = min(ans, width*height)

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

if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[]] * n
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        if len(nexts[ai]) == 0:
            nexts[ai] = [bi]
        else:
            nexts[ai].append(bi)
        if len(nexts[bi]) == 0:
            nexts[bi] = [ai]
        else:
            nexts[bi].append(ai)

    depth = [[0]]
    l = [0]
    new_l = []
    uncheck = [x + 1 for x in range(n - 1)]
    arrows = [0] * n

    while len(uncheck) != 0:
        for x in l:
            for nxt in nexts[x]:
                if (nxt in uncheck) and (nxt not in new_l):
                    new_l.append(nxt)
        
        depth.append(new_l)
        l = new_l
        new_l = []
    
    for i, d in enumerate(depth):
        for room in d:
            for nxt in nexts[room]:
                if nxt in depth[i - 1]:
                    arrows[room] = nxt
                    break

    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)
    

### FIXED CODE ###

from sys import stdin
from collections import deque
input = stdin.readline


def main():
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for _ in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    blues = [-1] * n # 1 is in blues
    blues[0] = 0 # 0 is not in blues
    checked = [0] * n

    red_deque = deque([0])

    while len(red_deque) > 0:
        rd = red_deque[0]
        red_deque.popleft()
        if checked[rd] == 0:
            checked[rd] = 1
            for nxt in nexts[rd]:
                if blues[nxt] == -1:
                    blues[nxt] = rd
                    red_deque.append(nxt)

    print("Yes")
    for blue in blues[1:]:
        print(blue + 1)
    

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

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


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    if i < K:
        A = [dp[i-k] + abs(H[i-k] - H[i]) for k in range(1, i+1)]
        dp[i] = min(A)
    else:
        A = [dp[i - k] + abs(H[i - k] - H[i]) for k in range(1, K+1)]
        dp[i] = min(A)


print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1, N):
    s = max(i-K, 0)
    dp[i] = np.min(dp[s:i]+np.abs(H[s:i]-H[i]))


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

import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

c = collections.Counter(A)
#print(c)

csum = 0
for i in c.values():
    if i == 1:
        csum += 0
    else:
        csum += combinations_count(i, 2)

#print(csum)

#print(A)
for i in A:
    #print(c[i], i)
    if c[i] == 1:
        print(csum)
    elif c[i] == 2:
        print(csum-1)
    else:
        print(csum - combinations_count(c[i], 2) + combinations_count(c[i]-1, 2))


### FIXED CODE ###

import collections
import math

def combinations_count2(n):
    return n*(n-1) // 2

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

c = collections.Counter(A)
#print(c)

d = {}
csum = 0
for i,j in c.items():
    if j == 1:
        d[i] = 0
        csum += 0
    else:
        d[i] =  combinations_count2(j)
        csum += d[i]

#print(c)
#print(d)
#print(csum)

#print(A)
for i in A:
    #print(c[i], i)
    if c[i] == 1:
        print(csum)
    elif c[i] == 2:
        print(csum-1)
    else:
        print(csum - combinations_count2(c[i]) + combinations_count2(c[i]-1))
### BUGGY CODE ###

n = int(input())

aa = []
for i in range(n):
	k,l = map(int,input().split())
	aa.append([k,l])
aa.sort(key = lambda x:x[1])
aa.reverse()
co = 0
ma = 0
kkk = 0
for i in range(n):
	if i % 2 == 0:
		ma = max(aa,key = lambda x:x[0])[0]
		for j in range(len(aa)):
			if ma == aa[j][0]:
				co += aa.pop(j)[0]
				break
	else:
		co -= aa.pop(0)[1]

print(co)


### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()

po = []
su = 0
for i in range(n):
    a,b = m()
    po.append([a+b,a])
po.sort(reverse = True)

for i in range(n):
    if i % 2 == 0:
        su += po[i][1]
    else:
        su -= po[i][0] - po[i][1]
print(su)
### BUGGY CODE ###

N = int(input())
C = dict()
i, cp, r = 0, 0, ['x'] * N
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            r[C[c]] = i
        C[c], cp = i, c
        i += 1
length = i
hist, add, temp, ans = [0] * length, [0] * length, 0, 0
for l in range(length):
    temp += add[l]
    hist[l] = temp
    if r[l] != 'x':
        add[r[l]] += temp + 1
        ans += temp + 1
print((ans+1) % (10**9+7))

### FIXED CODE ###

N = int(input())
C = dict()
i, cp, hist, ans = 0, 0, [0]*N, 0
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            temp = hist[C[c]] + 1
            hist[i] = hist[i-1] + temp
            ans += temp
        else:
            hist[i] += hist[i-1]
        C[c], cp = i, c
        i += 1
print((ans+1) % (10**9+7))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
div = 1000000007

A = [0]*(N+1)
A[0] = 1

for i in range(1, N+1):
  if i in a: A[i] = 0
  else:
    if i==1: A[i] = 1
    else:
      A[i] = (A[i-1] + A[i-2])%div

print(A[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
div = 1000000007

a.sort()
A = [0]*(N+1)
A[0] = 1

flag = True
if M==0: flag = False

for i in range(1, N+1):
  if flag and i == a[0]:
    A[i] = 0
    a.remove(i)
    if len(a)==0: flag = False
  else:
    if i==1: A[i] = 1
    else:
      A[i] = (A[i-1] + A[i-2])%div

print(A[N])
### BUGGY CODE ###

import math

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

Ai= sorted(A, reverse=True)
Bi= sorted(B, reverse=True)
Ci= sorted(C, reverse=True)

def su(a,b,c):
	return(Ai[a]+Bi[b]+Ci[c])

a=0
b=0
c=0

pq=[[su(a,b,c),a,b,c]]
ck=[[su(a,b,c),a,b,c]]

dl=0
for i in range(k):
	dl=pq.index(max(pq))
	res=pq.pop(dl)
	print(res[0])
	#print(pq)
	
	a=res[1]
	b=res[2]
	c=res[3]
	if a+1<=x-1 and (not [su(a+1,b,c),a+1,b,c] in ck):
		pq.append([su(a+1,b,c),a+1,b,c])
		ck.append([su(a+1,b,c),a+1,b,c])
	if b+1<=y-1 and (not [su(a,b+1,c),a,b+1,c] in ck):
		pq.append([su(a,b+1,c),a,b+1,c])
		ck.append([su(a,b+1,c),a,b+1,c])
	if c+1<=z-1 and (not [su(a,b,c+1),a,b,c+1] in ck):
		pq.append([su(a,b,c+1),a,b,c+1])
		ck.append([su(a,b,c+1),a,b,c+1])

### FIXED CODE ###

import math

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

Ai= sorted(A, reverse=True)
Bi= sorted(B, reverse=True)
Ci= sorted(C, reverse=True)

def su(a,b,c):
	return(Ai[a]+Bi[b]+Ci[c])

a=0
b=0
c=0

pq=[[su(a,b,c),a,b,c]]
ck=[a,b,c]

dl=0
for i in range(k):
	dl=pq.index(max(pq))
	res=pq.pop(dl)
	print(res[0])

	a=res[1]
	b=res[2]
	c=res[3]
	if a+1<=x-1 and (not [a+1,b,c] in ck):
		pq.append([su(a+1,b,c),a+1,b,c])
		ck.append([a+1,b,c])
	if b+1<=y-1 and (not [a,b+1,c] in ck):
		pq.append([su(a,b+1,c),a,b+1,c])
		ck.append([a,b+1,c])
	if c+1<=z-1 and (not [a,b,c+1] in ck):
		pq.append([su(a,b,c+1),a,b,c+1])
		ck.append([a,b,c+1])
### BUGGY CODE ###

S = input()
T = ""
Q = int(input())
d = 0 # d=0:right, d=1:left
for i in range(Q):
  I = list(input().split())
  if I[0] == "1":
    d ^= 1
  else:
    if d + int(I[1]) == 2:
      S += I[2]
    else:
      T += I[2]
if d == 0:
  for i in range(len(T)-1, -1, -1):
    print(T[i], end="")
  for s in S:
    print(s, end="")
else:
  for i in range(len(S)-1, -1, -1):
    print(S[i], end="")
  for t in T:
    print(t, end="")
print()

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
d = 0 # d=0:right, d=1:left
for i in range(Q):
  I = list(input().split())
  if I[0] == "1":
    d ^= 1
  else:
    if d + int(I[1]) == 2:
      S.append(I[2])
    else:
      S.appendleft(I[2])
if d == 1:
  S.reverse()
for s in S:
  print(s, end="")
print()
### BUGGY CODE ###

A, B = map(int,input().split())
ans = 1
i = 2
while i <= A and i <= B:
    if A % i == 0 and B % i == 0:
        ans += 1
        A /= i
        B /= i
        while A % i == 0 and B % i == 0:
            A /= i
            B /= i
            continue
        i += 1
    else:
        i += 1
print(ans)

### FIXED CODE ###

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

def ssb(n):
    a = {1}
    while n % 2 == 0:
        a.add(2)
        n /= 2
    i = 3
    while i ** 2 <= n:
        if n % i == 0:
            a.add(i)
            n /= i
        else:
            i += 2
    if n != 1:
        a.add(n)
    return a

a = ssb(A)
b = ssb(B)

print(len(a&b))
### BUGGY CODE ###

#pythonで再帰は遅い_pypyだと再帰に関しては更に遅い
N,Q=map(int,input().split())
#dc={i:[] for i in range(1,N)}
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lf=[0 for i in range(N)]#行ったかどうかのフラグ
lv=[0 for i in range(N)]
#*で初期化するとあまり良くない
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
#print("lv",lv)
lque=[0]#次に訪れる親を入れておく(キュー(順番通り))
lf[0]=1
#p=0
while len(lque)!=0:
#count=1
#while count<N:
    #for i in range(len(lc[p]))
    p=lque[0]
    for i in lc[p]:#among children
        #lv[lque[0]]+=
        #c=lc[p][i]
        if lf[i]==0:
             lv[i]+=lv[p]
             lf[i]+=1
             lque.append(i)
             #count+=1
    #p=lque[0]
    lque.remove(p)
for i in lv:
    print(i,end=" ")
print()


### FIXED CODE ###

#import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
lp=[0]
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

isAC = [0] * len(S)
for x in range(len(S) - 1):
    if S[x] == "A" and S[x + 1] == "C":
        isAC[x] = 1

for x in range(Q):
    ans = 0
    for y in range(l[x] - 1, r[x] - 1):
        ans += isAC[y]
    print(ans)


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

countAC = [0] * len(S)
for x in range(len(S) - 1):
    countAC[x + 1] = countAC[x]
    if S[x] == "A" and S[x + 1] == "C":
        countAC[x + 1] += 1
for x in range(Q):
    print(countAC[r[x] - 1] - countAC[l[x] - 1])
### BUGGY CODE ###

from collections import deque

INF = 10000

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

poss = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if Sss[i][j] == '.':
            poss.append((i, j))

def bfsGridGraph(Sss, xSt, ySt, xEn, yEn, INF):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    distss = [[(INF if S != '#' else -1) for S in Ss] for Ss in Sss]
    distss[xSt][ySt] = 0
    Q = deque([(xSt, ySt)])
    while Q:
        x, y = Q.popleft()
        if (x, y) == (xEn, yEn): break
        dist = distss[x][y]
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if distss[x2][y2] == INF:
                distss[x2][y2] = dist + 1
                Q.append((x2, y2))
    return distss

N = len(poss)
ans = 0
for i in range(N):
    xSt, ySt = poss[i]
    for j in range(i+1, N):
        xEn, yEn = poss[j]
        distss = bfsGridGraph(Sss, xSt, ySt, xEn, yEn, INF)
        dist = distss[xEn][yEn]
        ans = max(ans, dist)

print(ans)


### FIXED CODE ###

dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

N = H*W
adjL = [[] for _ in range(N)]
for x in range(1, H+1):
    for y in range(1, W+1):
        if Sss[x][y] != '.': continue
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if Sss[x2][y2] != '.': continue
            z = (x-1)*W + y-1
            z2 = (x2-1)*W + y2-1
            adjL[z].append(z2)

# 重みなしグラフの直径を求める
def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])

maxDist = getDiameterOfUnweightedGraph(adjL)
print(maxDist)
### BUGGY CODE ###

n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]

DX = [[0] * n for s in range(2**n)]
DY = [[0] * n for s in range(2**n)]
for s in range(2**n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

pow2 = [2**i for i in range(n)]
A = [10**20] * (n + 1)
for s in range(3**n):
    tmp = s
    c, sx, sy = 0, 0, 0
    for i in range(n):
        if tmp % 3 == 1:
            sx += pow2[i]
            c += 1
        if tmp % 3 == 2:
            sy += pow2[i]
            c += 1
        tmp //= 3
    d = 0
    for i in range(n):
        d += min(DX[sx][i], DY[sy][i])
    A[c] = min(A[c], d)
print(*A, sep="\n")


### FIXED CODE ###

n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]
pow2 = [2**i for i in range(n + 1)]

DX = [[0] * n for s in range(pow2[n])]
DY = [[0] * n for s in range(pow2[n])]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(pow2[n])]

A = [10**20] * (n + 1)
for sx in range(pow2[n]):
    rx = (pow2[n] - 1) ^ sx
    sy = rx
    for _ in range(pow2[n - BC[sx]]):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")