Harryxun/stf_run huggingface dataset:
def p_d():
    from sys import stdin

    input = stdin.readline
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        route[u - 1].append((v - 1, w))
        route[v - 1].append((u - 1, w))

    ans = [-1] * n

    def dfs(p, d):
        ans[p] = d
        for i, j in route[p]:
            if ans[i] < 0:
                dfs(i, d & j)

    dfs(0, 0)
    print("\n".join(map(str, ans)))
    
p_d()

### FIXED CODE ###

def p_d():
    from sys import stdin
    input = stdin.readline
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        route[u - 1].append((v - 1, w))
        route[v - 1].append((u - 1, w))

    ans = [-1] * n

    def dfs(p, d):
        ans[p] = d
        for i, j in route[p]:
            if ans[i] < 0:
                dfs(i, d ^ j)

    dfs(0, 0)
    print("\n".join(map(str, ans)))
    
p_d()
def x(p0, p1):
    d = abs(p0 - p1)
    if d > 2:
        return []
    elif d == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        l = abs(w)
        h = (1 - l ** 2) ** .5 * w / l
        return [m + h, m - h]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float, input().split(','))) for _ in [0] * n]
    Q = []
    for i in range(n):
        for j in range(i + 1, n):
            Q += x(P[i], P[j])
    print(max(1, *[sum(1.01 >= abs(q - p) for p in P) for q in Q]))


### FIXED CODE ###

def x(p0, p1):
    d = abs(p0 - p1)
    if d > 2:
        return []
    elif d == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        l = abs(w)
        h = (1 - l ** 2) ** .5 * w / l
        return [m + h, m - h]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float, input().split(','))) for _ in [0] * n]
    Q = []
    for i in range(n):
        for j in range(i + 1, n):
            Q += x(P[i], P[j])
    print(max([sum(1.01 >= abs(q - p) for p in P) for q in Q] + [1]))
N = int(input())
A = input()
A = int(eval(A.replace(" ","^")))
print(A)
print("Yes" if A == 0 else "No")



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
flag = False
x = len(set(A))
if x == 1 and A[0] == 0:
  flag = True
elif x == 2 and A.count(0) == N // 3:
  flag = True
elif x == 3:
  X = A[0]
  Y = -1
  Z = -1
  i = 1
  while i < N:
    if A[i] != X:
      Y = A[i]
      break
    i += 1
  while i < N:
    if A[i] != X and A[i] != Y:
      Z = A[i]
    i += 1
  if X ^ Y ^ Z == 0 and A.count(X)  == N // 3 and A.count(Y)  == N // 3:
    flag = True
print("Yes" if flag else "No")
a,b,c = map(int,input.split()
print(b*(c//a))
            

### FIXED CODE ###

a,b,c = map(int,input().split())
print(b*int(c/a))
s = list(input())
t = list(input())

b = []

for i in range(len(s)):
    c1 = s[i]
    c2 = t[i]
    if c1 == c2:
        if b[j][0] == c1:
            print("No")
            exit()
    if c1 != c2:
        for j in range(len(b)):
            if b[j][0] == c1 and b[j][1] != c2:
                print("No")
                exit()
            if b[j][0] != c1 and b[j][1] == c2:
                print("No")
                exit()
            if b[j][0] == c1 and b[j][1] == c2:
                break
        b.append([c1, c2])
else:
    print("Yes")


### FIXED CODE ###

S = input()
T = input()

converter = dict()

for s, t in zip(S, T):
    if converter.get(s) is not None:
        if converter[s] != t:
            print("No")
            break
    else:
        converter[s] = t
else:
    if len(converter.values()) != len(set(converter.values())):
        print("No")
    else:
        print("Yes")
N=int(input())
A=list(map(int,input().split()))
b=0
for i in range(N):
  b=b+1/A[i]
print 1/b


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
b=0
for i in range(N):
  b=b+1/A[i]
print(1/b)
, X, T = map(int,input().split())
n = 0
total = 0

if N % X == 0:
    n = N / X
    total = n * T
else:
    n = N // X + 1
    total = n * T

print(int(total))

### FIXED CODE ###

N, X, T = map(int,input().split())
n = 0

if N % X == 0:
    n = N / X
else:
    n = N // X + 1

print(int(n * T))
import math

n = int(input())

faccs = [0 for i in range(int(n**0.5))]


def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True

    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True

if isPrime(n):
    print(1)
else:

    while n % 2 == 0: 
        faccs[2] += 1
        n = n / 2

    for i in range(3,int(math.sqrt(n))+1,2): 
          

        while n % i== 0: 
            faccs[i] += 1 
            n = n / i 

    if n > 2: 
        faccs[int(n)] += 1 

    count = 0

    for i in faccs:
        if i > 0:
            temp = 1
            while (i-temp)>=0:
                i -= temp
                temp +=1
                count += 1
    print(count)
        


### FIXED CODE ###


import math

n = int(input())

#faccs = [0 for i in range(int(n/2) +1)]
faccs = {}


def isPrime(n) : 
  
    if (n <= 1) : 
        return False
    if (n <= 3) :
        return True

    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True

if isPrime(n):
    print(1)
else:
    while n % 2 == 0:
        if 2 in faccs:
            faccs[2] += 1
        else:
            faccs[2] = 1
        n = n / 2

    for i in range(3,int(math.sqrt(n))+1,2): 
          

        while n % i== 0:
            if i in faccs:
                faccs[i] += 1
            else:
                faccs[i] = 1
            n = n / i 

    if n > 2:
        faccs[math.floor(n)] = 1 

    count = 0

    for i in faccs.values():
        if i > 0:
            temp = 1
            while (i-temp)>=0:
                i -= temp
                temp +=1
                count += 1
    print(count)
N = int(input())
K = int(input())
prices = list()
for i in range(N):
    prices.append(int(input()))
sum = 0
for i in prices:
    x = min(prices)
    sum = sum + x
    prices.remove(x)
    K = K - 1
    if K == 0: break
print(sum)

### FIXED CODE ###

n, k = map(int,input().split())
li = list(map(int, input().split()))[:n]
count = 0
li.sort()
for i in range(k):
    count+=li[i]

print(count)
a,b, k = map(int,input().split())

lis = list(range(a,b+1))


for i in lis:
    if (i >= a and i <a+k) or (i <=b and b-k < i):
        print(i)

### FIXED CODE ###

a,b,k = map(int, input().split())
if k*2+a-1<=b:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)
a,b,c = map(int, input(split))

if a < b < c:
print("Yes")
else:
print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())

if a < b < c:
    print("Yes")
else:
    print("No")
n
a = list(map(int, input().split()))
print(max(a)-min(a))


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
print(max(a)-min(a))
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(N+100)]
for i in range(2,N+100):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+100)]
B[N+100-1] = pow(A[N+100-1],p-2)
for i in range(N+100-2,1,-1):
    B[i] = (B[i+1]*(i+1))%p
P = [1 for _ in range(10**5)]
P[0]=0
P[1]=0
for i in range(2,int((10**5)**0.5)+1):
    for j in range(i*i,10**5,i):
        P[j] = 0
Q = []
for i in range(2,10**5):
    if P[i]==1:
        Q.append(i)
N,M = map(int,input().split())
C = {q:0 for q in Q}
for q in Q:
    if M%q==0:
        while M%q==0:
            M = M//q
            C[q] += 1
prod = 1
for q in Q:
    k = C[q]
    a = A[k+N-1]
    a = (a*B[N-1])%p
    a = (a*B[k])%p
    prod = (prod*a)%p
print(prod)

### FIXED CODE ###

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,M = map(int,input().split())
A = [1 for _ in range(N+100)]
for i in range(2,N+100):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+100)]
B[N+100-1] = pow(A[N+100-1],p-2)
for i in range(N+100-2,1,-1):
    B[i] = (B[i+1]*(i+1))%p
P = [1 for _ in range(10**5)]
P[0]=0
P[1]=0
for i in range(2,int((10**5)**0.5)+1):
    for j in range(i*i,10**5,i):
        P[j] = 0
Q = []
for i in range(2,10**5):
    if P[i]==1:
        Q.append(i)

C = {q:0 for q in Q}
for q in Q:
    if M%q==0:
        while M%q==0:
            M = M//q
            C[q] += 1
if M>1:
    C[M] = 1
    Q.append(M)
prod = 1
for q in Q:
    k = C[q]
    a = A[k+N-1]
    a = (a*B[N-1])%p
    a = (a*B[k])%p
    prod = (prod*a)%p
print(prod)
nums = []
while True:
    num =[int(e) for e in input().split()]
    if num[0]==0 and num[1]==0 and num[2]==0:
        break
    nums.append(num)
    
for i in range(len(nums)):
    yakusuu = []
    yakusuu_count = 0
    for j in range(1,nums[i][2]+1):
        if nums[i][2]%j== 0:
            yakusuu.append(j)
    for k in range(len(yakusuu)):
        if nums[i][0]<=yakusuu[k] and yakusuu[k]<=nums[i][1]:
            yakusuu_count += 1
    print(yakusuu_count)


### FIXED CODE ###

nums =[int(e) for e in input().split()]
yakusuu = []
yakusuu_count = 0
for j in range(1,nums[2]+1):
    if nums[2]%j== 0:
        yakusuu.append(j)
for k in range(len(yakusuu)):
    if nums[0]<=yakusuu[k] and yakusuu[k]<=nums[1]:
        yakusuu_count += 1
print(yakusuu_count)
n = int(input())
a = list(map(int,input().split()))
rate=[0]*9
for i in a:
    rate[i//400]+=1
min = 0
for i in range(8):
    if rate[i]>0:
        min+=1
max = min + rate[8]
if max>8:
    max=8
print(min,max)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
rate=[0]*13
for i in a:
    rate[i//400]+=1
min = 0
for i in range(8):
    if rate[i]>0:
        min+=1

max = min + rate[8] + rate[9] + rate[10] + rate[11] + rate[12]
if min ==0:
    min=1
print(min,max)
from collections import Counter, deque

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_cn = Counter(A)
B_cn = Counter(B)
AB_cn = Counter(A+B)
if AB_cn.most_common()[0][1] > 2*N:
    print("No")
else:
    print("Yes")
    0/0


### FIXED CODE ###

from collections import Counter, deque

N = int(input())
A = list(map(int, input().split())) + [N+1]
B = list(map(int, input().split())) + [N+1]
C = [0]
D = [0]

AB_cn = Counter(A+B)
if AB_cn.most_common()[0][1] > N:
    print("No")
else:
    print("Yes")
    for i in range(N+1):
        if len(C) != A[i]:
            C.extend([i]*(A[i]-len(C)))
        if len(D) != B[i]:
            D.extend([i]*(B[i]-len(D)))
    ans = 0
    for i in range(N):
        curr = C[i+1] - D[i]
        ans= max(curr, ans)
    B = B[:-1]
    ans = [B[(i-ans)%N] for i in range(N)]
 
    print(*ans)
import sys

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

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

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

if __name__ == '__main__':
    main()



### FIXED CODE ###


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

P+=A*3

print(P//2)
S = input().split("/")
 
if int(S[5]) < 5 and int(S[4]) == 0 :
	print('Heisei')
else :
	print('TBD')

### FIXED CODE ###

s = input()

if s <= "2019/04/30":
    print("Heisei")
else:
    print("TBD")
n = int(input())
print(int(n * (n - 1) / 2))

### FIXED CODE ###

s = list(input())
t = list(input())
p = []

for i in range(0,3):
    p.append(s[i] == t[i])
    
print(p.count(True))
input(a, b)
a = int(a)
b = int(b)
print (a*b, a*2+b*2)


### FIXED CODE ###

a, b = map(int, input().split())
print (a*b, 2*a+2*b)
import numpy as np
n, m = map(int, input().split())
ab = np.array([list(map(int, input().split())) for x in range(m)]) - 1

to = list(range(n))
ranks = [0] * n
nodes = [1] * n

def find(x):
    if to[x] == x:
        return x
    else:
        root = find(to[x])
        to[x] = root
        return root

entire = (n - 1) * n // 2
def merge(x, y):
    global entire
    xroot = find(x)
    yroot = find(y)
    # if xroot == yroot:
    #     return
    if ranks[xroot] < ranks[yroot]:
        to[xroot] = yroot
        # entire -= nodes[yroot] * nodes[xroot]
        # nodes[yroot] += nodes[xroot]
    else:
        to[yroot] = xroot
        # entire -= nodes[yroot] * nodes[xroot]
        # nodes[xroot] += nodes[yroot]
        if ranks[xroot] == ranks[yroot]:
            ranks[yroot] += 1


results = [entire]
for a, b in reversed(ab[1:]):
    merge(a, b)
#     results.append(entire)
#
# for v in reversed(results):
#     print(v)


### FIXED CODE ###

import numpy as np
n, m = map(int, input().split())
ab = np.array([list(map(int, input().split())) for x in range(m)]) - 1

to = list(range(n))
ranks = [0] * n
nodes = [1] * n

def find(x):
    if to[x] == x:
        return x
    else:
        root = find(to[x])
        to[x] = root
        return root

entire = (n - 1) * n // 2
def merge(x, y):
    global entire
    xroot = find(x)
    yroot = find(y)
    if xroot == yroot:
        return
    if ranks[xroot] < ranks[yroot]:
        to[xroot] = yroot
        entire -= nodes[yroot] * nodes[xroot]
        nodes[yroot] += nodes[xroot]
    else:
        to[yroot] = xroot
        entire -= nodes[yroot] * nodes[xroot]
        nodes[xroot] += nodes[yroot]
        if ranks[xroot] == ranks[yroot]:
            ranks[xroot] += 1


results = [entire]
for a, b in reversed(ab[1:]):
    merge(a, b)
    results.append(entire)

for v in reversed(results):
    print(v)
n = int(input())

d = {}

for i in range(n):
  a = input()
  if a not in d:
    d[a] = 1
  else:
    d[a] += 1

dsorted = sorted(d, key=lambda x:x[1])

cnt = 0
for i in dsorted:
  print(i)
  cnt += 1
  if cnt == 2:
    break

### FIXED CODE ###

n = int(input())

d = {}

for i in range(n):
  a = input()
  if a not in d:
    d[a] = 1
  else:
    d[a] += 1

dsorted = sorted(d.items(), key=lambda x:x[1], reverse=True)

name = []
cnt = dsorted[0][1]

for i in dsorted:
  if i[1] == cnt:
    name.append(i[0])
  else:
    break

name.sort()

for i in name:
  print(i)
a, b, c, d, e = map(int,input().split())
if a = 0:
　　　　print(‘1’)
elif b = 0:
　　　　print(‘2’)
elif c = 0:
　　　　print(‘3’)
elif d = 0:
　　　　print(‘4’)
else: 
　　　　print('5')
    

### FIXED CODE ###

x = [int(i) for i in input().split()]
print(x.index(0) + 1)
n = int(input())
a = list(map(int, input().split()))

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(*b[i], *c[-i-1])
    y = min(*b[i], *c[-i-1])
    r = min(r, x-y)
print(r,flush=True)

### FIXED CODE ###

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

l, r = a[:2]
m = 1
b = [(l,r)]
for i in range(2, n-2):
    r += a[i]
    for j in range(m, i):
        nl, nr = l+a[j], r-a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m += 1
    b.append((l,r))

l, r = a[-2:]
m = n-2
c = [(l,r)]
for i in range(2, n-2)[::-1]:
    l += a[i]
    for j in range(i+1, m+1)[::-1]:
        nl, nr = l-a[j], r+a[j]
        if abs(l-r) < abs(nl-nr): 
            break
        l, r = nl, nr
        m -= 1
    c.append((l,r))

r = 10**9
for i in range(n-3):
    x = max(b[i]+c[-i-1])
    y = min(b[i]+c[-i-1])
    r = min(r, x-y)
print(r)
n=int(input())
list_judge=[]
for i in range (n):
  list_judge.append(str(input()))

print("AC x ",acnum=list_judge.count("AC"))
print("WA x ",wanum=list_judge.count("WA"))
print("TLE x ",tlenum=list_judge.count("TLE"))
print("RE x ",renum=list_judge.count("RE"))

### FIXED CODE ###

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

acnum=list_judge.count("AC")
wanum=list_judge.count("WA")
tlenum=list_judge.count("TLE")
renum=list_judge.count("RE")

print("AC x ",acnum)
print("WA x ",wanum)
print("TLE x ",tlenum)
print("RE x ",renum)
import itertools
import pandas as pd
import math 
from collections import defaultdict as dd
import numpy as np
import pandas as pd
def main():
	a = int(input())
	b = int(input())
	c = int(input())
	x = int(input())

	count = 0
	for i in range(a+1):
		y = x- 500*i
		if y == 0:
			count += 1
			continue
		if y > 0:
			for j in range(b+1):
				z = y - j*100
				if z == 0:
					count += 1
					continue
				if z > 0:
					for k in range(c+1):
						if int(z-50*k) == 0:
							count += 1
							break

	print (count)

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()



### FIXED CODE ###

def main():
	a, b, c, x = (int(input()), int(input()), int(input()), int(input()))

	count = 0
	for i in range(a+1):
		y = x- 500*i
		if y == 0:
			count += 1
			continue
		if y > 0:
			for j in range(b+1):
				z = y - j*100
				if z == 0:
					count += 1
					continue
				if z > 0:
					for k in range(c+1):
						if int(z-50*k) == 0:
							count += 1
							break

	print (count)

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()
W = ["SUM", "MON", "TUE", "WED", "THU", "FRI", "SAT"]
S = input()
print(len(W) - W.index(S))


### FIXED CODE ###

s = input()

week = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"]

for i in range(len(week)):
    if s == week[i]:
        print(len(week)-i)
N,M = [int(i) for i in input().split()]
count = 0
if 2 * N <= M:
    count = N
    M -= 2 * N
    if M >= 4:
        count += M // 4
        print(count)
    else:
        print(count)
else:
    if N != 0:
        while N == 0 or M <= 1:
            count += 1
            N -= 1
            M - = 2
        print(count)
    else:
        print(count)


### FIXED CODE ###

N,M = [int(i) for i in input().split()]
count = 0
if 2 * N <= M:
    count = N + (M - 2 * N) // 4
else:
    count = M // 2

print(count)
mod = 10**9+7
def combination(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


X,Y = map(int,input().split())
s = (2*Y-X)//3
t = (2*X-Y)//3

if (2*Y-X)%3==0 and (2*X-Y)%3==0 :
    ans =  combination(s+t,t,mod)
    print(ans)
else:
    print(0)
    

### FIXED CODE ###

def combination(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p
 
    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p
 
    return (numerator * pow(denominator, p-2, p)) % p
 
 
X, Y = map(int, input().split())
 
a = (2*Y-X) / 3
b = (2*X-Y) / 3
 
if a >= 0 and b >= 0 and a == int(a) and b == int(b):
    a = int(a)
    b = int(b)
 
    print(combination(a+b, a, 10**9+7))
else:
    print(0)
import math
import sys
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))

T = []
T1 = []
for _ in range(N):
    T.append([float("inf")] * N)
    T1.append([float("inf")] * N)
for n in range(N):
    T[n][n] = 0
    T1[n][n] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = C
    T[B][A] = C

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T[i][j] > T[i][k] + T[k][j]:
                T[i][j] = T[i][k] + T[k][j]

for j in range(N):
    for i in range(N):
        if i == j:
            continue
        if T[j][i] <= L:
            T1[j][i] = 1
            T1[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T1[i][j] > T1[i][k] + T1[k][j]:
                T1[i][j] = T1[i][k] + Tq[k][j]

Q = int(input())
for _ in range(Q):
    S, G = list(map(int, input().split()))
    if math.isinf(T1[S-1][G-1]):
        print(-1)
    else:
        print(T1[S-1][G-1]-1)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))

T = []
T1 = []
for _ in range(N):
    T.append([float("inf")] * N)
    T1.append([float("inf")] * N)
for n in range(N):
    T[n][n] = 0
    T1[n][n] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = C
    T[B][A] = C

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T[i][j] > T[i][k] + T[k][j]:
                T[i][j] = T[i][k] + T[k][j]

for j in range(N):
    for i in range(N):
        if i == j:
            continue
        if T[j][i] <= L:
            T1[j][i] = 1
            T1[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T1[i][j] > T1[i][k] + T1[k][j]:
                T1[i][j] = T1[i][k] + T1[k][j]

Q = int(input())
for _ in range(Q):
    S, G = list(map(int, input().split()))
    if math.isinf(T1[S-1][G-1]):
        print(-1)
    else:
        print(T1[S-1][G-1]-1)
N = int(input())
A = list(map(int, input().split()))

for i in range(N - 1):
  if A[i] < 0 :
    A[i] *= -1
    A[i + 1] *= -1
  elif i == N - 2 and A[i] == 0:
    A[i + 1] *= -1
    A[i + 2] *= -1
print(sum(A))

### FIXED CODE ###

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

for i in range(N):
  if A[i] < 0:
    count += 1
    A[i] *= -1
print(sum(A) if count % 2 == 0 else sum(A) - min(A) * 2)
s = list(map(int,input().split()))
t = 0
h = 0
a = s.pop(0)
b = s.pop(0)
print(a)
print(b)
d = 0
if b ==0:
  print(a)
else:
  for i in range(a+1,a+2+b):
    c = 1
    for k in range(0,b):
      if i == s[k]:
        c = 0
        break
    if c==1:
      t = i
      break
  for i in range(a-1,a-2-b,-1):
    c = 1
    for k in range(0,b):
      if i == s[k]:
        c = 0
        break
    if c==1:
      h = i
      break
  if abs(t-a)>=abs(h-a):
    print (h)
  else:
    print(t)
    

### FIXED CODE ###

x,n=map(int,input().split())
l=list(map(int,input().split()))
a=0
for i in range(100):
    if x-i not in l:
        ans=x-i
        a=i+1
        break
for i in range(100):
    if x+i not in l:
        ansb=x+i
        ab=i+1
        break
if a>ab:
    print(ansb)
else:
    print(ans)
N = int(input())
A = sorted(list(map(int, input().split())))[]
print(sum(A[-1::-2])-sum(A[-2::-2]))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)[::-1]
Alice = 0
Bob = 0
for i in range(N):
  if i % 2 == 0:
    Alice += a[i]
  else:
    Bob += a[i]
print(Alice - Bob)