Harryxun/stf_run huggingface dataset:
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
  
n = int(input())
ls = prime_factorize(n)

for i in range(len(ls) //2 + 1):
  ans = []
  ans.append(i + n / i - 2)

ans.sort()
print(ans[0])



### FIXED CODE ###

def prime_factorize(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
n = int(input())
ls = prime_factorize(n)
for i in range(len(ls)):
  ans = []
  pair = n // ls[i]
  ans.append(ls[i] + n // ls[i] - 2)
 
ans.sort()
print(ans[0])
# 前の提出だとTLEなっちゃった
# じゃあ全部保存していってやるよ
n = int(input())
d = {}
arr = []
for _ in range(n):
    x = list(sorted(input()))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)


### FIXED CODE ###

# じゃあ全部保存していってやるよ
# atcoderのpython3のバージョンが古すぎて(3.4.3)TypeError: unhashable type: 'list'なるのでため息つきながら直した

n = int(input())
d = {}
arr = []
for _ in range(n):
    x = "".join(list(map(str, list(sorted(input())))))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

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

list.sort(A, reverse=True)
print(A)
for m in range(M):
    tmp = int(A[0] / 2)
    del A[0]
    for i in range(len(A)):
        if A[i] < tmp:
            A.insert(i, tmp)
            break

print(sum(A))

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
q = []
for x in A:
    heapq.heappush(q, -x)
for m in range(M):
    x = heapq.heappop(q)
    x /= 2
    heapq.heappush(q, x)
ans = 0
for x in q:
    ans += int(-x)
print(ans)
import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for d in range(n):
    for e in range(d+1, n):
        a, b = l[d], l[e]
        idx = bisect.bisect_left(l, a + b)
        ans += max(idx - e - 1,)
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for d in range(n):
    for e in range(d+1, n):
        a, b = l[d], l[e]
        idx = bisect.bisect_left(l, a + b)
        ans += max(idx - e - 1, 0)
print(ans)
N = list(map(int, str(input())))

s = 0
for n in range(N):
  s += n

if(s % 9 == 0): print('Yes')
else: print('No')

### FIXED CODE ###

N = list(map(int, str(input())))
s = sum(N)
 
if(s % 9 == 0): print('Yes')
else: print('No')
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & b:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        b = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & b:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            b <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        if h == h2[i][0] and (h != 0 and h2[i][0] != 0):
            ans = min(ans,c+h2[i][1])
        else:
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = [INF] * 10000

    for i in range(1,2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        if h1[dif] > tc: h1[dif] = tc

    ans = h1[0]

    for i in range(1,2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        if dif == 0:
            ans = min(ans,tc)
        else:
            ans = min(ans,h1[dif]+tc)

    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()
N = int(input())
S = input()
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

new_S = list()
for word in S:
    num = alpha.index(word)+N
    if num > 25:
        num -= 25
    new_S.append(alpha[num])
print(''.join(new_S))


### FIXED CODE ###

N = int(input())
S = input()
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

new_S = list()
for word in S:
    num = alpha.index(word)+N
    if num > 25:
        num -= 26
    new_S.append(alpha[num])
print(''.join(new_S))
n = int(input())

a = []
maximum = 0
second_maximum = 0
for i in range(n):
    input_num = int(input())
    a.append(input_num)
    if input_num > maximum:
        second_maximum = maximum
        maximum = input_num
    elif input_num > second_maximum:
        second_maximum = input_num
        
for a_num in a:
    if a_num == maximum:
        print(second_maximum)
    else:
        print(maximum)

### FIXED CODE ###

n = int(input())

print(3 * (n ** 2))
N = input()
A = input()
return N ** 2 - A

### FIXED CODE ###

def get_colored_cells():
    N = int(input())
    A = int(input())
    print(N ** 2 - A)

get_colored_cells()
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump(*objects):
    print(*objects, file=sys.stderr)


N = int(input())
A = [0] + list(map(int, input().split())) + [0]
dump(N, A)
B = cp.deepcopy(A)
C = cp.deepcopy(A)
for i in range(1, len(A)):
     dump(i)
    B[i] = B[i-1] + abs(A[i]-A[i-1])
for i in range(len(A)-2, -1, step=-1):
     dump(i)
    C[i] = C[i+1] + abs(A[i]-A[i+1])
dump(A, B, C)
for i in range(1, N+1):
    dump(i, B[i-1] + B[N+1] - B[i+1] + abs(A[i-1]-A[i+1]))
    print(B[i-1] + C[i+1] + abs(A[i-1]-A[i+1]))

exit(0)


### FIXED CODE ###

import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump(*objects):
    print(*objects, file=sys.stderr)


N = int(input())
A = [0] + list(map(int, input().split())) + [0]
# dump(N, A)
B = cp.deepcopy(A)
C = cp.deepcopy(A)
for i in range(1, len(A)):
    # dump(i)
    B[i] = B[i-1] + abs(A[i]-A[i-1])
for i in range(len(A)-2, -1, step=-1):
    # dump(i)
    C[i] = C[i+1] + abs(A[i]-A[i+1])
# dump(A, B, C)
for i in range(1, N+1):
    # dump(i, B[i-1] + B[N+1] - B[i+1] + abs(A[i-1]-A[i+1]))
    print(B[i-1] + C[i+1] + abs(A[i-1]-A[i+1]))

exit(0)
#printがpaiはおかしいのかな・・・
A,B= map(int, input().split())
print((3*A+P)//2)


### FIXED CODE ###

A,P= map(int, input().split())
print((3*A+P)//2)
import itertools
NK = input().split()
N = NK[0]
K = int(NK[1])

d = input().split()
D = [int[s] for s in d]

Da = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(len(D)):
    Da.remove(D[i])

nu = []
for j in itertools.combinations_with_replacement(Da, len(N)+1):
    b = ''.join([str(j[i]) for i in range(len(N)+1)])
    nu.append(int(b))

for i in nu:
    if i >= N:
        print(i)
        break
  

### FIXED CODE ###

import itertools
NK = input().split()
N = NK[0]
K = int(NK[1])
 
d = input().split()
D = [int(s) for s in d]
 
Da = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 
for i in D:
    Da.remove(i)
Da_str = [str(j) for j in Da]
 
a_1 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N))]
a_2 = [''.join(j) for j in itertools.product(Da_str, repeat=len(N)+1)]
a = a_1 + a_2
nu = [int(k) for k in a]
 
for i in nu:
    if i >= int(N):
        print(i)
        break
import sys

def split(g, n):
  gl = g[:-1]
  gr = g[1:]
  sub = [[(b - a), i+1] for a, b, i in zip(gl, gr, range(len(gl)))]
  sub = sorted(sub, key = lambda x: -x[0])
  j = []
  for i in range(n-1):
    j.append(sub[i][1])
  j = sorted(j)
  jl = [0] + j[:-1]
  res = []
  for l, r in zip(jl, j):
    s = g[l:r]
    res.append(s)
  res.append(g[j[-1]:])
  return res


def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  g = [int(a) for a in input().split()]
  g = sorted(g)
  ans = 0
  if N < M:
    sp = split(g, N)
    for s in sp:
      ans += s[-1] - s[0]
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  ans = 0
  if N < M:
    g = [int(a) for a in input().split()]
    g = sorted(g)
    L = g[:-1]
    R = g[1:]
    sub = [b - a for a, b in zip(L, R)]
    sub = sorted(sub)
    ans = sum(sub[:(M-N)])
  print(ans)


if __name__ == '__main__':
  main()
N = input()
X = list(map(int, input().split()))
for p in range(1, max(X)):
    for x in X:
        x_sum=0
        x_sum+=(x-p)**2
    ans = min(ans, x_sum)
print(ans)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
ans = float("inf")
for p in range(1, max(X)+1):
    x_sum=0
    for x in X:
        x_sum+=(x-p)**2
    ans = min(ans, x_sum)
print(ans)
W, H, N = map(int,input().split())
#白い領域の端
l = 0
r = W
u = H
d = 0
for i in range(N):
    x, y, a = map(int,input().split())
    if a == 1:
        l = max(x,l)
    elif a == 2:
        r = min(x,r)
    elif a == 3:
        d = max(y,d)
    else:
        u = min(y,u)
print(max((r-l),0)*max((u-d),0)

### FIXED CODE ###

W, H, N = map(int,input().split())
#白い領域の端
l = 0
r = W
u = H
d = 0
for i in range(N):
    x, y, a = map(int,input().split())
    if a == 1:
        l = max(x,l)
    elif a == 2:
        r = min(x,r)
    elif a == 3:
        d = max(y,d)
    else:
        u = min(y,u)
print(max((r-l),0)*max((u-d),0))
I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
for i in range(N-1,N-K-1,-1):
	if i>0:
		dp[i] = abs(H[i]-H[N])

for i in range(N-K-1,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])

### FIXED CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
for i in range(N-1,N-K-1,-1):
	if i>0:
		dp[i] = abs(H[i-1]-H[N-1])

for i in range(N-K-1,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]=len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans-sum(hL)-sum(hR))        
    
    

### FIXED CODE ###

t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))
n = int(input())
s, t = input().split()
a = ""

for i in range(n):
    a += s[i] + t[i]
    
print(a)

### FIXED CODE ###

A = int(input())
B = int(input())
 
print(6-A-B)	#和から誤答を引けば正答
n = int(input())
a = list(input().split())

if n%2==1:
    print(*a[n-1::-2], *a[1:n+1:2])
else:
    print(*a[n::-2], *a[:n+1:2])

### FIXED CODE ###

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

if n%2==1:
    print(" ".join(a[n-1::-2]+a[1:n+1:2]))
else:
    print(" ".join(a[n::-2]+a[:n+1:2]))
A, B = map(int, input().split())

def gcd( x, y ):
    count = 0
    while y != 0:
        x, y = y, x%y        
    return x


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i: True for i in range(n + 1) if is_prime[i]}

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i in p:
                divisors.append(i)
            if i != n // i and n//i in p:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
x = gcd(A, B)
p = primes(x)
x = make_divisors(x)
print(len(x)+1)

### FIXED CODE ###

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

import math

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

import fractions
x = fractions.gcd(A, B)
divisors = make_divisors(x)
ans = 0
for d in divisors:
    if is_prime(d):
        ans += 1
print(ans)
N,M=map(int, input().split())
s=[0]*M
c=[0]*M
x=[0]*M
h=0
y=0
z=1
for i in range(M):
	s[i],c[i]=map(int, input().split())
	y=s[i]-1
	x[y]=c[i]
if len(x)==N:
	x.reverse()
	for j in x:
		h=h+j*z
		z=10*z
	print(h)
else:
	print('-1')

### FIXED CODE ###

N,M=map(int,input().split())
s=[0]*M
c=[0]*M
a=0
for i in range(M):
	s[i],c[i]=map(int,input().split())
ans=-1
if M==0:
	ans=1*(10**(N-1))
	if ans==1:
		ans=0
	print(ans)
	exit()
if max(s)>N:
	print(ans)
	exit()
for j in range(0,1000):
	value=str(j)
	if len(value)==N:
		for S,C in zip(s,c):
			if int(value[S-1])==C:
				a+=1
		if a==M:
			ans=int(j)
			break
		else:
			a=0
	else:
		continue
print(ans)
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)


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

num_bombs_each_row = [0] * H
num_bombs_each_col = [0] * W
bombs = set()

for _ in range(M):
    h, w = map(int, input().split())
    # 0-index
    h -= 1
    w -= 1

    bombs.add((h, w))
    num_bombs_each_row[h] += 1
    num_bombs_each_col[w] += 1

max_bombs_in_row = max(num_bombs_each_row)
max_bombs_in_col = max(num_bombs_each_col)

rows_with_max_bombs = []
for row in range(H):
    if num_bombs_each_row[row] == max_bombs_in_row:
        rows_with_max_bombs.append(row)

cols_with_max_bombs = []
for col in range(H):
    if num_bombs_each_col[col] == max_bombs_in_col:
        cols_with_max_bombs.append(col)

found = False
for row in rows_with_max_bombs:
    for col in cols_with_max_bombs:
        if not (row, col) in bombs:
            found = True
            break

ans = max_bombs_in_row + max_bombs_in_col
if found:
    print(ans)
else:
    print(ans - 1)


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)


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

num_bombs_each_row = [0] * H
num_bombs_each_col = [0] * W
bombs = set()

for _ in range(M):
    h, w = map(int, input().split())
    # 0-index
    h -= 1
    w -= 1

    bombs.add((h, w))
    num_bombs_each_row[h] += 1
    num_bombs_each_col[w] += 1

max_bombs_in_row = max(num_bombs_each_row)
max_bombs_in_col = max(num_bombs_each_col)

rows_with_max_bombs = []
for row in range(H):
    if num_bombs_each_row[row] == max_bombs_in_row:
        rows_with_max_bombs.append(row)

cols_with_max_bombs = []
for col in range(W):
    if num_bombs_each_col[col] == max_bombs_in_col:
        cols_with_max_bombs.append(col)

found = False
for row in rows_with_max_bombs:
    for col in cols_with_max_bombs:
        if not (row, col) in bombs:
            found = True
            break

ans = max_bombs_in_row + max_bombs_in_col
if found:
    print(ans)
else:
    print(ans - 1)
# -*- coding: utf-8 -*-
def main():
    n, q = inputAsIntArr()
    s = input()

    idxes = []
    for i in range(n):
        if s[i] != 'A':
            continue
        if s[i+1] == 'C':
            idxes.append(i)
            i += 1

    num_acs = ""
    for i in range(q):
        li, ri = inputAsIntArr()
        num_ac = len([v for v in idxes if li-2 < v < ri-1])
        num_acs += str(num_ac) + "\n"

    print(num_acs.strip())


def inputAsIntArr():
    return [int(i) for i in input().split(' ')]


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    # 累積出現数を格納: 指定される番号が1始まりなのでズラして格納
    p = [0] * (n+1)
    for i in range(n):
        p[i+1] = p[i] + (1 if s[i:i+2] == "AC" else 0)

    for i in range(q):
        l, r = map(int, input().split())
        # 終端(=l-1)から始端-1(=r-1)の累積出現数を引いた数が指定区間内での出現回数
        print(p[r-1] - p[l-1])


if __name__ == '__main__':
    main()
print(-(-sum(int,input(),split()))//2)

### FIXED CODE ###

a,b=map(int,input().split())
print(-((-a-b)//2))
from operator import itemgetter

N_shop, M_required_drink  = map(int, raw_input().split())

shop_list = []
for tmp_shop in range(N_shop):
  shop_list.append(map(int, raw_input().split()))

total_money = 0
got_drink = 0
for i in sorted(shop_list, key=itemgetter(0)):
  limit_at_shop = i[1]
#  print(i)

  while got_drink < M_required_drink and limit_at_shop > 0:
    total_money = total_money + i[0]
    got_drink   = got_drink + 1
    limit_at_shop = limit_at_shop - 1
#    print("  %s %s %s" % (total_money, got_drink, limit_at_shop))

print(total_money)


### FIXED CODE ###

first_args = raw_input().split()
second_args = raw_input().split()

max_row = int(first_args[0])
max_col = int(first_args[1])

fill_row = int(second_args[0])
fill_col = int(second_args[1])

if(fill_row <= max_row and fill_col <= max_col):
  all_cells = max_row * max_col
  filled_cells = (fill_row * max_col) + (fill_col * max_row) - (fill_row * fill_col)

  print all_cells - filled_cells
print(map(lambda x:x*(x+1)/2,input())

### FIXED CODE ###

x = int(input())
print(int(x*(x+1)/2))
k,n=map(int,input().split())
a=list(map(int,input().split()))
j=[int(k+a[0]-a[-1])]
j.append(a[i+1]-a[i] for i in range(n-1))
print(k-max(j))




### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
j=[int(k+a[0]-a[-1])]
for i in range(n-1):
    j.append(a[i+1]-a[i])
print(k-max(j))
N,Q=map(int,input().split())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
p=[0 for i in range(N-1)]
q=[0 for i in range(N-1)]
for i in range(N-1):
  a[i],b[i]=map(int,input().split())
for i in range(Q):
  p[i],q[i]=map(int,input().split())
#print(N,Q)
#print(a)
#print(b)
#print(p)
#print(q)

#c=list(zip(a,b))
#c.sort()
#a,b=list(zip(*c))

K=[0 for i in range(N)]
for i in range(N-1):
  K[p[i]-1]+=q[i]
#print(K)

#for i in range(N-1):
#  K[b[i]-1]+=K[a[i]-1]
#print(K)

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

### FIXED CODE ###

import collections

N,Q=map(int,input().split())
M=[[] for i in range(N+1)]
P=[0 for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  M[a].append(b)
  M[b].append(a)
#print("M:",M)

S=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  S[p]+=x
#print(S)
  
d=collections.deque([1])

while len(d):
  dd=d.popleft()
  if P[dd]==0:
    P[dd]=1
    for i in M[dd]:
      if P[i]==0:
        S[i]+=S[dd]
      d.append(i)
  #print(d,S)
print(*S[1:])
S =int(input())
W =int(input())

if S <=W:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

S,W=(int(x) for x in input().split())

if S <= W:
  print('unsafe')
else:
  print('safe')
s = input()
if (s[:4] < 2019) or (s[:4] == 2019 and s[5] == 0 and s[6] <= 4):
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
S = input()
W = input()

if S <= W:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

s, w =  map(int, input().split())
if s <= w:
    print('unsafe')
else:
    print('safe')
N = int(input())
A = list(map(int, input().split()))

# res = 0
# for i in range(N):
#     res += A[i] - (i+1)
# b = res // N
# print(res, b)
A_sorted = sorted(A)
b = A_sorted[int((len(A)-1)/2)]
b2 = A_sorted[int((len(A)-1)/2 + 1)]

sadness_1 = sum([abs(A[i] - b) for i in range(N)])
sadness_2 = sum([abs(A[i] - b2) for i in range(N)])

print(min(sadness_1, sadness_2))

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N)
else:
    print(2*N)
s = input()
ans = ''
lst = []
for ss in s:
    if ss in ['A', 'C', 'G', 'T']:
        ans += ss
    else:
        lst.append(len(ans))
        ans = ''
print(max(lst))

### FIXED CODE ###

s = input()
s += 'q'
ans = ''
lst = []
for ss in s:
    if ss in ['A', 'C', 'G', 'T']:
        ans += ss
    else:
        lst.append(len(ans))
        ans = ''
print(max(lst))
import math
import statistics

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

for i in range(N):
  a = []
  for index, k in enumerate(li):
    if i == index:
      continue
      
    a.append(k)
    
  print(statistics.median(a))

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
sx = sorted(s)
a = sx[(n//2)-1]
b = sx[n//2]
for i in s:
  if i <= a:
    print(b)
  else:
    print(a)
n,k = map(int,input().split())
hlist = list(map(int,input().split()))
hp_list = sorted(hlist)
if k <len(hlist):
  for i in range(k):
    del hp_list[-i-1]
  print(sum(hp_list))
else:
  print(0)



### FIXED CODE ###

import heapq
n,k = map(int,input().split())
hlist = list(map(lambda x: int(x)*(-1),input().split()))

heapq.heapify(hlist)
if k < n:
  for i in range(k):
    heapq.heappop(hlist)
  print(-sum(hlist))
else:
  print(0)
n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))