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

import collections
N = int(input())

P = [0] * N
uvw1 = []
for i in range(1, N):
    u, v, w = map(int, input().split())
    uvw1.append((u, v, 0 if w % 2 == 0 else 1 ))

d = {}
uvw = collections.deque()
for x in sorted(uvw1):
    uvw.append(x)

u, v, w = uvw[0]
d[u] = 0

while len(uvw):
    u, v, w = uvw.popleft()
    if d.get(u, -1) >= 0:
        d[v] = d[u] ^ w
        continue
    elif d.get(v, -1) >= 0:
        d[u] = d[v] ^ w
        continue
    uvw.append((u, v, w))

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


### FIXED CODE ###

import collections
N = int(input())

g = [dict() for _ in range(N+1)]
for i in range(1, N):
    u, v, w = map(int, input().split())
    w = 0 if w % 2 == 0 else 1
    g[u][v] = w
    g[v][u] = w

ret = {1:0}
q = collections.deque()
q.append(1)
while len(q):
    d = q.pop()
    for h in g[d]:
        if ret.get(h, -1) < 0:
            ret[h] = ret[d] ^ g[d][h]
            q.append(h)

for i in range(1, N+1):
    print(ret[i])
### BUGGY CODE ###

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

r = 1
for a in A:
    r *= a

if r > pow(10, 18):
    print(-1)
else:
    print(r)


### FIXED CODE ###

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

A.sort(reverse=True)

for i in range(N - 1, -1, -1):
    if A[i] == 0:
        print(0)
        exit()

r = 1
upper = pow(10, 18)
for i in range(N):
    r *= A[i]

    if r > upper:
        print(-1)
        exit()

print(r)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
n1,n2=0,1
for i in range(1,N+1):
    if i in A:
        n1=n2
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)

### FIXED CODE ###

N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
ai=0
n1,n2=0,1
for i in range(1,N+1):
    if ai<M and i==A[ai]:
        ai+=1
        n1=n2
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

p = [0] * n
for _ in range(q):
    pp, x = [int(i) for i in input().split()]
    p[pp - 1] += x


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j != r:
            dfs(j, i)
dfs()

print(" ".join(map(str,p)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, q = [int(i) for i in input().split()]
ab = [[] for _ in range(n)]
for _ in range(n - 1):
    i, j = [int(i)-1 for i in input().split()]
    ab[i].append(j)
    ab[j].append(i)
p = [0]*n
for _ in range(q):
    i, j = [int(i) for i in input().split()]
    p[i-1] += j

al = [False]*n
pp = [0]*n


def a(i=0, j=0):
    al[i] = True
    j += p[i]
    pp[i] = str(j)
    for k in ab[i]:
        if not al[k]:
            a(k, j)


a()
print(" ".join(pp))
### BUGGY CODE ###

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

ret = []
for i in range(1,max(p)+1):
    ret.append(i)

l = []
for i in range(N):
    l.append(sum(ret[0:p[i]])/p[i])

k = []
for i in range(len(l)):
    k.append(sum(l[i:i+K]))

print(max(k))

### FIXED CODE ###

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

l = []
for i in range(N):
    l.append((1+p[i])/2)

a = [0] * N
a[0] = l[0]
for i in range(1,len(l)):
    a[i] = a[i-1] + l[i]

ans = 0
for i in range(K,len(l)):
    ans = max(ans,a[i]-a[i-K])

if N == 1 or N - K == 0:
    print(max(a))
else:
    print(ans)
### BUGGY CODE ###

s=input()
q=int(input())

rev=0

for _ in range(q):
    temp=input().split(" ")
    
    if temp[0]=="1":
        if rev==0:
            rev=1
        else:
            rev=0
    else:
        if rev==0:
            if temp[1]=="1":
                s=temp[2]+s
            else:
                s=s+temp[2]
        else:
            if temp[1]=="2":
                s=temp[2]+s
            else:
                s=s+temp[2]

if rev==0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

s=input()
q=int(input())

rev=0

sento=[]
matsubi=[]

for _ in range(q):
    temp=input().split(" ")
    
    if temp[0]=="1":
        if rev==0:
            rev=1
        else:
            rev=0
    else:
        if rev==0:
            if temp[1]=="1":
                sento.append(temp[2])
            else:
                matsubi.append(temp[2])
        else:
            if temp[1]=="2":
                sento.append(temp[2])
            else:
                matsubi.append(temp[2])

sento_s="".join(sento)
sento_s=sento_s[::-1]
matsubi_s="".join(matsubi)

s=sento_s+s+matsubi_s

if rev==0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

k = int(input())
if k%2==0:
    print(-1)
else:
    ret = 1
    res = 7%k
    while res != 0:
        res = (res * 10 + 7)%k
        ret += 1
    print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

k = int(input())
if k%2==0 or k%5==0:
    print(-1)
else:
    ret = 1
    res = 7%k
    while res != 0:
        res = (res * 10 + 7) % k
        ret += 1
    print(ret)
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

t = 0
ans = 0

for i in range(n):
  if sum(a[:i+1]) <= k and i + 1 > ans:
      ans = i + 1

  for j in range(m):
    if sum(a[:i+1]) + sum(b[:j+1]) <= k and i + j + 2> ans:
      ans = i + j + 2

print(ans)



### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())

two_count_list = np.array([])
for i in range(1, n+1):
    two_count =0
    score = i
    while score <= k-1:
        score *= 2
        two_count += 1

    two_count_list = np.append(two_count_list, two_count)    

print((1/n) * ((1/2) ** two_count_list).sum())

### FIXED CODE ###

import numpy as np
n,k = map(int, input().split())

two = 0
for i in range(1, n+1):
    two_count =0
    score = i
    while score <= k-1:
        score *= 2
        two_count += 1

    two += (1/2) ** two_count

print((1/n) * two)
### BUGGY CODE ###

def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])
    L.append(100000000001)
    R.append(100000000001)
    i = j = 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n]))))
print(S[n])


### FIXED CODE ###

def mergeSort(A, left, right, n):
    if left + 1 < right:
        mid = int((right + left ) / 2 )
        mergeSort(A, left, mid, n)
        mergeSort(A, mid, right, n)
        return (merge(A, left, mid, right, n))

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [10 ** 9 + 1]
    R = A[mid:right] + [10 ** 9 + 1]
    i , j = 0, 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n]))))
print(S[n])
### BUGGY CODE ###

n = int(input().rstrip())
R = [0 for _ in range(n)]
for i in range(n):
    R[i] = int(input().rstrip())

max_margin = 1 - 10**9
for i in range(n):
    for j in range(i+1, n):
        margin = R[j] - R[i]
        if margin > max_margin:
            max_margin = margin

print(max_margin) 


### FIXED CODE ###

n = int(input().rstrip())
R = [0 for _ in range(n)]
for i in range(n):
    R[i] = int(input().rstrip())

margin = - 10**9
min_R = R[0]
for j in range(1, n):
    margin = max(margin, R[j] - min_R)
    min_R = min(min_R, R[j])

print(margin)
### BUGGY CODE ###

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji2[b[m]-1]=1
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

### FIXED CODE ###

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
      moji2[b[m]-1]=1
      if moji2[N-1]:
        print("inf")
        sys.exit()
print(V[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np
import fractions
from functools import reduce

from copy import deepcopy

import warnings

def gcd_list(nums):
    return reduce(fractions.gcd, nums)


def main():
    warnings.simplefilter('ignore')

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

    bools = np.ones(N, dtype=bool)

    gcd_val = 0
    ans = 0
    for i in range(N):
        A_cop = deepcopy(A)
        bl_cop = deepcopy(bools)

        fal = [i]
        bl_cop[fal] = False

        gcd_val = gcd_list(A_cop[bl_cop])

        if ans == 0 or ans < gcd_val:
            ans = gcd_val

    print(ans)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import fractions


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

    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp

    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()

    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])

    print(max(LR_gcds))

main()
### BUGGY CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.shortest_path(A.tocsr(),method='D',directed=False)

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

### FIXED CODE ###

from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
a=[0]*N

for n in range(len(A)):
  for i in range(N):
    if A[n]==i+1:
      a[i]=a[i]+1

for i in a:
  print(i)
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
a=[0]*N

for i in range(N-1):
	a[A[i]-1]=a[A[i]-1]+1

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

import collections
n,m=map(int,input().split())
l=[[]*i for i in range(m)]
a=set()
for i in range(m):
  s,e=map(int,input().split())
  for j in range(s,e+1):
    l[i].append(j)
for i in range(m):
  if i==0:
    a=set(l[i])
  else:
    a=a&set(l[i])
print(len(a))

### FIXED CODE ###

n,m=map(int,input().split())
l,r=0,1000000
for i in range(m):
  a,b=map(int,input().split())
  l=max(l,a)
  r=min(r,b)
print(len(range(l,r+1)))
### BUGGY CODE ###

N, K = map(int, input().split())
S = list(map(int, list(input())))
now = 1
cnt = 0
Nums = []
for i in range(N):
    if S[i] == now:
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    Nums.append(cnt)

if len(Nums)%2==0:
    Nums.append(0)

add = 2*K+1
ans = 0
for i in range(len(Nums))[::2]:
    tmp = 0
    left = i
    right = min(i + add, len(Nums))
    for j in range(left, right):
        tmp += Nums[j]
    ans = max(tmp, ans)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = list(map(int, list(input())))
now = 1
cnt = 0
Nums = []
for i in range(N):
    if S[i] == now:
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    Nums.append(cnt)

if len(Nums) % 2 == 0:
    Nums.append(0)

add = 2*K+1
ans = 0
left, right = 0, 0
tmp = 0  # sum of [left, right)
for i in range(len(Nums))[::2]:
    next_left = i
    next_right = min(i + add, len(Nums))
    while next_left > left:
        tmp -= Nums[left]
        left += 1
    while next_right > right:
        tmp += Nums[right]
        right += 1

    ans = max(tmp, ans)

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

#import sys
N = int(input())
ans = sum(range(1,N))
print(ans)


### FIXED CODE ###

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

n = int(input())
s = []
for i in range(n):
  s.append(input())

t = list(set(s))

p = []
for j in t:
  p.append([s.count(j), j])

a = []
b = 0
q = 0
for k in sorted(p, reverse = True):
  if k[0] >= b:
    a.append(k[1])
    b = k[0]
  else:
    break

for l in sorted(a):
  print(l)
  

### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
  S = input()
  if S in d:
    d[S] += 1
  else:
    d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
  print(s)
### BUGGY CODE ###

#Aの中でa番目、Bの中でb番目、Cの中でc番目のものがabc > Kの時、大きい順のK番目以内にabcの組が入ることはない
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()))

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

lst = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1) * (j+1) * (k+1) <= K:
                lst += [A[i]+B[j]+C[k]]
lst.sort(reverse = True)
for l in range(K):
    print (lst[l])
    
    


### FIXED CODE ###

#単純な全探索-->TLE-->Cの配列を扱うときに工夫
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()))

lst = []
for i in A:
    for j in B:
        lst += [i + j]

lst.sort(reverse = True)
C.sort(reverse = True)

ans = []
for i in range(min(K, len(lst))):
    for j in range(min(K, len(C))):
        ans += [lst[i]+C[j]]

ans.sort(reverse = True)
for i in range(K):
    print (ans[i])
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline

def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(L[i],val)
if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')



### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')
### BUGGY CODE ###

from collections import Counter
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def factorize(m, d):
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            d[i] += 1
            if i != m // i:
                d[m//i] += 1
    return d
def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = Counter()
    for i in A:
        l = factorize(i, l)
    m = 1
    for k in l:
        if l[k] >= N-1 and k > m:
            m = k
    print(m)
main()


### FIXED CODE ###

from collections import OrderedDict
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def factorize(m):
    d = []
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            d.append(i)
            if i != m // i:
                d.append(m//i)
    return d
def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = list(set(factorize(A[0]) + factorize(A[1])))
    l.sort(reverse=True)
    d = OrderedDict()
    for i in l:
    	d[i] = 0
    for i in A:
        for j in d:
            if i % j == 0:
                d[j] += 1
    m = 1
    for k in d:
        if d[k] >= N-1:
            print(k)
            return
    print(1)
main()
### BUGGY CODE ###

from collections import Counter

N = int(input())
C = tuple(map(lambda x: int(x)-1,input().split()))

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

ROOT = N//2

parent = [None]*N
parent[ROOT] = -1

degree = [0]*N
stack = [ROOT]
while stack:
    p = stack.pop()
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            degree[p] += 1
            stack.append(c)

leaves = [i for i in range(N) if degree[i] == 0]

dp = [Counter() for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [0]*N

while leaves:
    c = leaves.pop()
    p = parent[c]


    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] += x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        a,b = dp[p],dp[c]
        if len(a) > len(b):
            a += b
            dp[p] = a
        else:
            b += a
            dp[p] = b
        dp[c] = None
        degree[p] -= 1
        if degree[p] == 0:
            leaves.append(p)

dp[ROOT][C[ROOT]] = subtreesize[ROOT]+1
for c in range(N):
    x = subtreesize[ROOT]-dp[ROOT][c]+1
    cnt[c] += x*(x+1)//2

total = (subtreesize[ROOT]+1)*(subtreesize[ROOT]+2)//2

print(*(total-v for v in cnt), sep='\n')


### FIXED CODE ###

from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N = int(readline())
C = tuple(map(lambda x: int(x)-1, readline().split()))

temp = map(int,read().split())
temp = zip(temp,temp)

adj = [list() for _ in range(N)]
for a,b in temp:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

def merge(a,b):
    if len(a) > len(b):
        a,b = b,a
    for k,v in a.items():
        b[k] += v
    return b

dp = [defaultdict(int) for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        dp[p] = merge(dp[c],dp[p])
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')
### BUGGY CODE ###

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    idx = a.index(max(a))
    a[idx] = int(a[idx] / 2)
print(sum(a))


### FIXED CODE ###

import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    B = []
    M = 80 * (H + W)
    for _ in range(H):
        a = tuple(map(int, input().split()))
        A.append(a)
    for _ in range(H):
        b = tuple(map(int, input().split()))
        B.append(b)
    AB = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            AB[i][j] = abs(A[i][j] - B[i][j])
    l = [[[0] * (M+1) for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                l[i][j][AB[0][0]] = 1
            else:
                t = AB[i][j]
                for k in range(M+1):
                    if i > 0 and l[i-1][j][k] == 1:
                        if k + t <= M:
                            l[i][j][k+t] = 1
                        if k - t >= 0:
                            l[i][j][k-t] = 1
                        if t - k >= 0:
                            l[i][j][t-k] = 1
                    if j > 0 and l[i][j-1][k] == 1:
                        if k + t <= M:
                            l[i][j][k+t] = 1
                        if k - t >= 0:
                            l[i][j][k-t] = 1
                        if t - k >= 0:
                            l[i][j][t-k] = 1
    for k in range(M):
        if l[-1][-1][k] == 1:
            return k
print(main())



### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    B = []
    M = 80 * (H + W)
    for _ in range(H):
        a = tuple(map(int, input().split()))
        A.append(a)
    for _ in range(H):
        b = tuple(map(int, input().split()))
        B.append(b)
    AB = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            AB[i][j] = abs(A[i][j] - B[i][j])
    l = [set([]) for _ in range(W)]
    lt = [set([]) for _ in range(W)]
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                lt[j].add(AB[0][0])
            else:
                t = AB[i][j]
                if i > 0:
                    for k in l[j]:
                        lt[j].add(k+t)
                        lt[j].add(abs(k-t))
                if j > 0:
                    for k in lt[j-1]:
                        lt[j].add(k+t)
                        lt[j].add(abs(k-t))
        l = lt
        lt = [set([]) for _ in range(W)]
    return min(l[-1])
print(main())