Harryxun/stf_run huggingface dataset:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    heapq.heapify(ls)
    heapq.heapify(lt)
    dl = set()
    for i in range(Q):
        d = int(input())
        while len(lt) > 0 and lt[0][0] <= d:
            t, x = heapq.heappop(lt)
            dl.remove(x)
        while len(ls) > 0 and ls[0][0] <= d:
            s, x = heapq.heappop(ls)
            dl.add(x)
        if not dl:
            print('-1')
        else:
            print(min(dl))
main()


### FIXED CODE ###

import heapq
def main():
    N, Q = map(int, input().split())
    l = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        l.append((s-x, 1, x))
        l.append((t-x, 0, x))
    for i in range(Q):
        d = int(input())
        l.append((d, 2, i))
    r = [-1] * Q
    l.sort()
    h = []
    se = set()
    for a, b, c in l:
        if b == 0:
            se.remove(c)
        elif b == 1:
            se.add(c)
            heapq.heappush(h, c)
        else:
            while h and h[0] not in se:
                heapq.heappop(h)
            r[c] = h[0] if h else -1
    print('\n'.join(map(str, r)))
            
main()
n=int(input())
A=list(map(int,input().split()))
cnt = [0]*100002
for a in A:
  cnt[a-1]+=1
  cnt[a]+=1
  cnt[a+1]+=1
print(max(cnt)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
cnt = [0]*100002
for a in A:
  cnt[a-1]+=1
  cnt[a]+=1
  cnt[a+1]+=1
print(max(cnt))
n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
if q<k:
  print(0)
  exit()
point=[-k]*n
for i in range(q):
  point[a[i]]+=1
for i in range(n):
  if point[i]>0:
    print('Yes')
  else:
    print('No')
    
  


### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
point=[-k]*n
for i in range(q):
  point[a[i]-1]+=1
for i in range(n):
  if point[i]>-2*k+q:
    print('Yes')
  else:
    print('No')
def solve():
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    for i in range(N-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
    
    for i in range(Q):
        p, x = map(int, input().split())
        adder(p-1, x, counter, tree)

    print(counter)

def adder(ind, add_val, counter, tree):
    counter[ind] += add_val
    if not tree[ind]:
        return

    for i in tree[ind]:
        adder(i, add_val, counter, tree)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
def solve():
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    tree = [[] for i in range(N)]
    counter = [0] * N
    arrived = [False] * N
    for i in range(N-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    for i in range(Q):
        p, x = map(int, input().split())
        counter[p-1] += x
    
    arrived[0] = True
    adder(0, counter, tree, arrived)

    print(*counter)

def adder(ind, counter, tree, arrived):
    for i in tree[ind]:
        if arrived[i]:
            continue
        counter[i] += counter[ind]
        arrived[i] = True
        adder(i, counter, tree, arrived)
    if not tree[ind]:
        return

if __name__ == '__main__':
    solve()
N,x=map(int, input().split(' '))
a = list(map(int, input().split(' ')))
wa = [a[0]]+[a[i]+a[i+1] for i in range(N-1)]+[a[-1]]
ans = 0

for i in range(N):
    print(i, a,wa,ans)
    if wa[i] <= x:
        continue
    if a[i] >= x:
        ans += wa[i]-x
        a[i] -= wa[i]-x
        wa[i] -= wa[i]-x
        wa[i+1] -= wa[i+1]-x
        continue
    if a[i] < x:
        ans += wa[i]-x
        a[i] = 0
        a[i] = x
        wa[i] = x

print(ans)

### FIXED CODE ###

N,x=map(int, input().split(' '))
a = list(map(int, input().split(' ')))
wa = [a[0]]+[a[i]+a[i+1] for i in range(N-1)]+[a[-1]]
ans = 0

for i in range(N):
    if wa[i] <= x:
        continue
    if wa[i] > x:
        dif = wa[i]-x
        ans += dif
        a[i] -= dif
        wa[i] -= dif
        wa[i+1] -= dif
        continue

if wa[-1] > x:
    ans += wa[-1]-x
    a[-1] = wa[-1]-x
    wa[-1] -= wa[-1]-x

print(ans)
n=int(input())
import fractions
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n = n//i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
d=list(prime_decomposition(n))
cnt=n
ans=[]
a=1
if n==1:
    print(1)
else:
    if len(list(str(d[len(d)-1])))>=(len(list(str(n)))+1)//2:
        print(len(list(str(d[len(d)-1]))))
    else:
        for i in range(d):
            a*=d[i]
            if a>n**(1/2):
                break
        a=str(a)
        print(len(list(a)))

### FIXED CODE ###

n=int(input())
cnt=[]
for i in range(1,int(n**(1/2))+1000):
    if n%i==0:
        cnt.append(n//i)
        cnt.append(i)
#print(cnt)
ans=[]
for j in range(len(cnt)//2):
    a=list(str(cnt[2*j]))
    b=list(str(cnt[2*j+1]))
    ans.append(max(len(a),len(b)))
print(min(ans))
x,y = map(int,input().split())

li =[[1,3,5,7,8,10,12],[4,6,9,11],[2]]

for i in li:
    if x and y in i:
        print("Yes")
        sys.exit()
print("No")

### FIXED CODE ###

# coding: utf-8
gl=[[1,3,5,7,8,10,12],[4,6,9,11],[2]]
x,y=map(int,input().split())
for g in gl:
    if x in g and y in g:
        print('Yes')
        exit()
print('No')
# -*- coding: utf-8 -*-

import numpy as np

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

a = np.array(list(map(int, input().split())))
for i in range(n[0] - 1):
    a = np.vstack((a, list(map(int, input().split()))))

b = np.array(list(map(int, input().split())))
for i in range(n[1] - 1):
    b = np.vstack((b, list(map(int, input().split()))))

ab_sum = np.dot(a, b)
for i in range(n[0]):
    print('{0}'.format(int(ab_sum[i])))



### FIXED CODE ###

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

for i in range(n[0]):
    a.append(list(map(int, input().split())))

for i in range(n[1]):
    b.append(int(input()))

for i in range(n[0]):
    ab_sum = 0
    for j in range(n[1]):
        ab_sum += a[i][j] * b[j]
    print(ab_sum)
count = 1
while True:
    x = input("")
    print("Case",str(count)+":",x)
    count = int(count) + 1
    if x == 0:
        break

### FIXED CODE ###

t=[]
while True:
    x = str(input(""))
    if x == "0":
        break
    else:
        t.append(x)
for i,v in enumerate(t):
    print("Case",str(i+1)+":",v)
def main():
	N, M = [int(x) for x in input().split(" ")]
	A = [int(a) for a in input().split(" ")]
	A.sort()
	overwrite = []
	for i in range(M):
		B, C = [int(x) for x in input().split(" ")]
		overwrite.append({
			"count": B,
			"number": C
		})
	overwrite.sort(key=lambda o: -o["number"])
	j = 0
	k = 0
	flag = False
	while not flag and j < len(A) and k < len(overwrite):
		o = overwrite[k]
		for m in range(o["count"]):
			if A[j] <= o["number"]:
				A[j] = o["number"]
				j += 1
			else:
				flag = True
		k += 1

	print(sum(A))

main()


### FIXED CODE ###

def main():
	N, M = [int(x) for x in input().split(" ")]
	A = [int(a) for a in input().split(" ")]
	A.sort()
	overwrite = []
	for i in range(M):
		B, C = [int(x) for x in input().split(" ")]
		overwrite.append({
			"count": B,
			"number": C
		})
	overwrite.sort(key=lambda o: -o["number"])
	j = 0
	k = 0
	flag = False
	while not flag and j < len(A) and k < len(overwrite):
		o = overwrite[k]
		for m in range(o["count"]):
			if j < len(A) and A[j] <= o["number"]:
				A[j] = o["number"]
				j += 1
			else:
				flag = True
		k += 1

	print(sum(A))

main()
a,b,c=map(int,input().split())
if a==b:
  if a==c:
    print("No")
  else:
    print("Yes")
elif a==c:
  print("Yes")
elif b==c:
  prunt("Yes")
else:
  print("No")


### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b:
  if a==c:
    print("No")
  else:
    print("Yes")
elif a==c:
  print("Yes")
elif b==c:
  print("Yes")
else:
  print("No")
m = input()
print(chr(rd(m)+1))

### FIXED CODE ###

m = input()
print(chr(ord(m)+1))
[n], *e = [[*map(int, t.split())] for t in open(0)]
viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}

ans = 0


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp


for x in e[0]:

    def bfs(x):
        queue = [x]
        while queue:
            tmp = queue.pop(0)
            z = mem[tmp] + (tmp in viewers)
            for k in directions(tmp):
                if mem[k] > z:
                    mem[k] = z
                    queue.append(k)

    ans += mem[x]
    viewers.remove(x)
    bfs(x)

print(ans)


### FIXED CODE ###

_, *e = [[*map(int, t.split())] for t in open(0)]

for n, a, b, c, d in e:
    mem = {0: 0, 1: d}
    mult_cost = {2: a, 3: b, 5: c}

    def solve(n):
        if n not in mem:
            tmp = n*d
            for k in mult_cost:
                if n % k == 0:
                    tmp = min(tmp, solve(n//k) + mult_cost[k])
                else:
                    tmp = min(tmp, solve(
                        n//k) + mult_cost[k] + (n % k)*d, solve(n//k + 1) + mult_cost[k] + k*d - (n % k)*d)
            mem[n] = tmp
        return mem[n]

    print(solve(n))
n, x = map(int, input().split())
costs = [int(input()) for _ in range(n)]
print(len(costs) + (x - sum(costs)) // min(consts))


### FIXED CODE ###

n, x = map(int, input().split())
costs = [int(input()) for _ in range(n)]
print(len(costs) + (x - sum(costs)) // min(costs))
n = int(input())
ans = 0
lis = [int(input()) for i in range(n)]+[0]

count = 0
m = -1
for i in range(n):
    if lis[i]%2 == 0:
        count += l[i]//2
    else:
        if lis[i+1] > 1:
            count += lis[i]//2+1
            lis[i+1] -= 1
        else:
            count += lis[i]//2
print(count)

### FIXED CODE ###

n = int(input())
ans = 0
lis = [int(input()) for i in range(n)]+[0]

count = 0

for i in range(n):
    if lis[i]%2 == 0:
        count += lis[i]//2
    else:
        if lis[i+1] > 1:
            count += lis[i]//2+1
            lis[i+1] -= 1
        else:
            count += lis[i]//2
print(count)
a, b = map(int, input())
if a*b < 0:
  print("Zero")
elif a > 0:
  print("Positive")
else:
  if (b-a)%2:
    print("Positive")
  else:
    print("Negative")
  

### FIXED CODE ###

a, b = map(int, input().split())
if a*b < 0:
  print("Zero")
elif a > 0:
  print("Positive")
elif a == 0 or b == 0:
  print("Zero")
else:
  if (b-a)%2:
    print("Positive")
  else:
    print("Negative")
if int(input()) == 25:
  print("Christmas")
elif int(input()) == 24:
  print("Christmas Eve")
elif int(input()) == 23:
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")

### FIXED CODE ###

a = int(input())
if a == 25:
  print("Christmas")
elif a == 24:
  print("Christmas Eve")
elif a == 23:
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")
import networkx as nx

R, C = [int(x) for x in input().split()]
grid = [list(input()) for r in range(R)]


def pack(r, c):
    return r * C + c


graph = nx.Graph()
for r in range(R - 1):
    for c in range(C - 1):
        if grid[r][c] == grid[r + 1][c] == ".":
            graph.add_edge(pack(r, c), pack(r + 1, c))
        if grid[r][c] == grid[r][c + 1] == ".":
            graph.add_edge(pack(r, c), pack(r, c + 1))

matching = nx.bipartite.maximum_matching(graph)

count = 0
for u, v in matching.items():
    if u > v:
        assert matching[v] == u
        r1, c1 = divmod(u, C)
        r2, c2 = divmod(v, C)
        if r1 == r2:
            if c1 > c2:
                c1, c2 = c2, c1
            grid[r1][c1], grid[r2][c2] = ">", "<"
        elif c1 == c2:
            if r1 > r2:
                r1, r2 = r2, r1
            grid[r1][c1] = "v"
            grid[r2][c2] = "^"
        count += 1

print(count)
for row in grid:
    print("".join(row))



### FIXED CODE ###

import networkx as nx

R, C = [int(x) for x in input().split()]
grid = [list(input()) for r in range(R)]


def pack(r, c):
    return r * C + c


graph = nx.Graph()
top_nodes = set()  # top half of the bipartite graph
for r in range(R):
    for c in range(C):
        if r + 1 < R and grid[r][c] == grid[r + 1][c] == ".":
            u, v = pack(r, c), pack(r + 1, c)
            graph.add_edge(u, v)
            if (r + c) % 2 == 0:
                top_nodes.add(v)
            else:
                top_nodes.add(u)
        if c + 1 < C and grid[r][c] == grid[r][c + 1] == ".":
            u, v = pack(r, c), pack(r, c + 1)
            graph.add_edge(u, v)
            if (r + c) % 2 == 0:
                top_nodes.add(v)
            else:
                top_nodes.add(u)


matching = nx.bipartite.maximum_matching(graph, top_nodes=top_nodes)

count = 0
for u, v in matching.items():
    if u > v:
        assert matching[v] == u
        r1, c1 = divmod(u, C)
        r2, c2 = divmod(v, C)
        if r1 == r2:
            if c1 > c2:
                c1, c2 = c2, c1
            grid[r1][c1], grid[r2][c2] = ">", "<"
        elif c1 == c2:
            if r1 > r2:
                r1, r2 = r2, r1
            grid[r1][c1] = "v"
            grid[r2][c2] = "^"
        count += 1

print(count)
for row in grid:
    print("".join(row))
h, w = map(int,input().split()
a = [row for row in range(h)]

print('#' * w)           
for i in range(h):
  print('#' + a[i] + '#')
print('#' * w)           

### FIXED CODE ###

h, w = map(int,input().split())
a = [input() for _ in range(h)]

print('#' * (w+2))           
for i in range(h):
  print('#' + a[i] + '#')
print('#' * (w+2))
import math
import functools

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
print(functools.reduce(lcm, [int(input()) for i in range(n)]))


### FIXED CODE ###

def gcd(x, y):
    if y==0:
        return x
    else:
        return gcd(y, x%y)

def lcm(x, y):
    return (x * y) // gcd(x, y)

n = int(input())
a = [int(input()) for i in range(n)]
r = 1
for i in a:
    r = lcm(r, i)
print(r)
n = int(input())
ss = input().splist()

ans = "Three"

if any(ss[i] == 'Y' for i in range(n)):
    ans = "Four"

print(ans)

### FIXED CODE ###

n = int(input())
ss = input().split()

ans = "Three"

if any(ss[i] == 'Y' for i in range(n)):
    ans = "Four"

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

color=[]
free=0
count=0
for i in a:
    if i//400<8 and i//400 not in color:
        color.append(i//400)
        Sans+=1
    elif i>=3200:
        free+=1
        
Mans=Sans
if free+count>8:
    Mans=8
else:
    Mans=count+free
    
print(Sans,Mans)


### FIXED CODE ###

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

color=[]
free=0
Sans,Mans=0,0
for i in a:
    if i//400<8 and i//400 not in color:
        color.append(i//400)
        Sans+=1
    elif i>=3200:
        free+=1
        
#Mans=Sans
#if free+Sans>=8:
 #   Mans=8
#else:
 #   Mans=Sans+free

Mans=Sans+free
if Sans==0:
    Sans=1
print(Sans,Mans)
import numpy as np
n = int(input())
f = []
for i in range(1, int(np.sqrt(n + 1))):
  if ((n % i) == 0):
    a = int(i)
    b = int(n / i)
    alen = len(str(a))
    blen = len(str(b))
    f.append(max(alen, blen))
print(min(f))


### FIXED CODE ###

n = int(input())
f = []
for i in range(1, int(n ** 0.5) + 1):
  if ((n % i) == 0):
    a = int(i)
    b = int(n / i)
    alen = len(str(a))
    blen = len(str(b))
    maxlen = max(alen, blen)
    f.append(maxlen)
print(min(f))
n = int(input())
a = [0] + [int(i) for i in input().split()] + [0]
d1a = [abs(a[i + 1] - a[i]) for i in range(n + 1)]
d2a = [abs(a[i + 1] - a[i - 1]) for i in range(1, n + 1)]
sum_a = sum(a)
for i in range(1, n + 1):
    print(sum_a + d2a[i] - (d1a[i - 1] + d1a[i]))

### FIXED CODE ###

n = int(input())
a = [0] + [int(i) for i in input().split()] + [0]
d1a = [abs(a[i + 1] - a[i]) for i in range(n + 1)]
d2a = [abs(a[i + 1] - a[i - 1]) for i in range(1, n + 1)]
sum_a = sum(d1a)
for i in range(1, n + 1):
    print(sum_a + d2a[i - 1] - (d1a[i - 1] + d1a[i]))
s=input()
if s='AAA' or 'BBB':
  print ('No')
else ('Yes')  

### FIXED CODE ###

s=input()
if s=='AAA' or s=='BBB':
  print ('No')
else:
  print('Yes')
import collections
N = int(input())
alist = list(map(int,input().split()))
acount = collections.Counter(alist)
a = acount.most_common()
a.sort()
alen = len(a)
MAX = 0
if alen == 1:
    print(a[0][1])
elif alen == 2:
    if abs(a[0][1]-a[1][1])<=2:
        print(a[0][1]+a[1][1])
    else:
        print(max(a[0][1],a[1][1]))
else:
    for i in range(alen-2):
        if abs(a[i][0]-a[i+1][0]) == 1 and abs(a[i+2][0]-a[i+1][0]) == 1:
            kari = a[i][1]+a[i+1][1]+a[i+2][1]
        elif abs(a[i][0]-a[i+1][0]) <= 2 or abs(a[i+2][0]-a[i+1][0]) <= 2:
            if abs(a[i][0]-a[i+1][0]) <= 2:
                kari1 = a[i][1]+a[i+1][1]
            if abs(a[i+1][0]-a[i+2][0]) <= 2:
                kari2 = a[i+1][1]+a[i+2][1]
            kari = max(kari1,kari2)
        else:
            kari = max(a[i][1],a[i+1][1],a[i+2][1])
        if MAX <= kari:
            MAX = kari
    print(MAX)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(N):
    ans.append(a[i]-1)
    ans.append(a[i])
    ans.append(a[i]+1)
c = collections.Counter(ans)
print(c.most_common()[0][1])
def solve():
  n = int(input())
  a = list(map(int, input().split()))
  c = collections.Counter(a)
  s = 0
  for i in list(c.values()):
    s += i*(i-1)//2
  print(c)
  for i in a:
    print(c[i])
    print(s-(c[i]-1))
  return 0
 
if __name__ == "__main__":
  solve()


### FIXED CODE ###

import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools

def solve():
  n = int(input())
  a = list(map(int, input().split()))
  c = collections.Counter(a)
  s = 0
  for i in list(c.values()):
    s += i*(i-1)//2
  for i in a:
    print(s-(c[i]-1))
  return 0
 
if __name__ == "__main__":
  solve()
from collections import deque

N = int(input())
if N == 2:
  print(1, 2)
  quit()
elif N == 3:
  print(1, 2, 3)
  quit()

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

d = deque([[0, -1]])
g = dict(zip(range(N), [[] for i in range(N)]))
p = dict(zip(range(N), [[] for i in range(N)]))
c = dict(zip(range(N), [[] for i in range(N)]))
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    d.appendleft([child, node])
    if par >= 0:
      g[par].append(child)
    p[node].append(child)
    c[child].append(node)

s = dict(zip(range(N), [[] for i in range(N)]))
for gran in g:
  _g = g[gran]
  _p = p[gran]
  _c = c[gran]
  if _g:
    if _p:
      for __g in _g:
        for __p in _p:
          if __p in tree[__g]:
            continue
          if __g < __p:
            s[__g].append(__p)
          else:
            s[__p].append(__g)
    if _c:
      for __g in _g:
        for __c in _c:
          if __g < __c:
            s[__g].append(__c)
          else:
            s[__c].append(__g)

m0 = N//3
m2 = (N - m0)//2
m1 = N - m0 - m2
if m1*m2 + m0*(m1+m2) + m0*(m0-1)//2 < len(s):
  print(-1)
else:
  _m0 = 1
  num = [0] * N
  nums1 = set([i for i in range(1, N+1)][::3])
  nums2 = set([i for i in range(2, N+1)][::3])
  for n in s:
    if _m0 <= m0:
      num[n] = 3*_m0
      _m0 += 1
    else:
      pairs = s[n]
      if num[n] == 0:
        num[n] = 1
      if num[n] == 1:
        for pa in pairs:
          num[pa] = 2
      else:
        for pa in pairs:
          num[pa] = 1
  for i in range(N):
    if num[i] == 1:
      num[i] = nums1.pop()
    elif num[i] == 2:
      num[i] = nums2.pop()      
  print(*num)

### FIXED CODE ###

from collections import deque

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

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 > N//3:
  if count1 > N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)
from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

def dfs(a,b):
    seen[a]=1
    #distance of a to b
    for g,d in G[a]:
        if seen[g]==1:continue
        if g==b:
            return d
        seen[g]=1
        dis=dfs(g,b)
        if dis !=0:
            return d+dis
        seen[g]=0
    return 0

di[0]=0
for i in range(N):
    if di[i]!=-1:continue
    seen=[0]*N
    di[i]=dfs(0,i)

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)
n = int(input())

lastch = ''
answer = 'Yes'
words = []
for i in range(n):
    word = list(input())
    words.append(word)
    if lastch != word[0] and i != 0:
        answer = 'No'
    lastch = word[-1]

if len(set(words)) != len(words):
    answer = 'No'

print(answer)


### FIXED CODE ###

n = int(input())

lastch = ''
answer = 'Yes'
words = []
for i in range(n):
    word = list(input())
    words.append(''.join(word))
    if lastch != word[0] and i != 0:
        answer = 'No'
    lastch = word[-1]

if len(set(words)) != len(words):
    answer = 'No'

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

if n % 2:
    for k in range(n):
        if a[k] != (k+1)//2*2
        print(0)
        break
    else:
         print(2**((n-1)//2) % (10**9+7))
else:
    for k in range(n):
        if a[k] != k//2*2+1
        print(0)
        break
    else:
        print(2**(n//2) % (10**9+7))


### FIXED CODE ###

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

if n % 2:
    for k in range(n):
        if a[k] != (k+1)//2*2:
            print(0)
            break
    else:
         print(2**((n-1)//2) % (10**9+7))
else:
    for k in range(n):
        if a[k] != k//2*2+1:
            print(0)
            break
    else:
        print(2**(n//2) % (10**9+7))
N = int(input())
A = list(map(int,input().split())
ans = -100
for i in range(N):
    for j in range(i, N):
         s = abs(A[i] - A[j])
         ans = max(ans, s)
print(ans)
         

### FIXED CODE ###

N = input()
A=sorted(map(int,input().split()),reverse = True)
s = A[0]-A[-1]
print(s)