Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
a = [list(map(int, input().split())) for _ in range(N-1)]
b = [list(map(int, input().split())) for _ in range(M)]

ans=[0]*N
trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])

for i in b:
    ans[i[0]-1] += i[1]


def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)
def main():
    input = sys.stdin.readline
    import sys
    sys.setrecursionlimit(10**9)
    from collections import deque
    mod = 10**9+7
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    que = deque([0])
    children = [[] for _ in range(N)]
    while que:
        v = que.pop()
        for nv in G[v]:
            if children[nv]:
                continue
            children[v].append(nv)
            que.append(nv)   
    memo = [[-1]*2 for _ in range(N)]
    def dp(i, c):
        if memo[i][c] >=0:
            return memo[i][c]
        if c == 1:
            res = 1
            for j in children[i]:
                res*=dp(j, 0)
                res%=mod
            memo[i][c] = res
        else:
            res = 1
            for j in children[i]:
                res*=(dp(j, 0)+dp(j, 1))
                res%=mod
            memo[i][c]= res
        return memo[i][c]
    print((dp(0, 0)+dp(0, 1))%mod)
main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    from collections import deque
    mod = 10**9+7
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    que = deque([0])
    children = [[] for _ in range(N)]
    while que:
        v = que.pop()
        for nv in G[v]:
            if children[nv]:
                continue
            children[v].append(nv)
            que.append(nv)   
    memo = [[-1]*2 for _ in range(N)]
    def dp(i, c):
        if memo[i][c] >=0:
            return memo[i][c]
        if c == 1:
            res = 1
            for j in children[i]:
                res*=dp(j, 0)
                res%=mod
            memo[i][c] = res
        else:
            res = 1
            for j in children[i]:
                res*=(dp(j, 0)+dp(j, 1))
                res%=mod
            memo[i][c]= res
        return memo[i][c]
    print((dp(0, 0)+dp(0, 1))%mod)
main()
N,T = map(int,input().split())
ans = 1000
for i in N:
  c,t = map(int,input().split())
  if T >= t:
      ans = min(ans,c)
print(ans)

### FIXED CODE ###

N,T = map(int,input().split())
ans = 1001
for i in range(N):
    c,t = map(int,input().split())
    if T >= t:
        ans = min(ans,c)
if ans == 1001:
    print("TLE")
else:
    print(ans)
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a_sum = [0]
b_sum = [0]
for i in range(n):
    a_sum.append(a[i]+a_sum[i])
    if a_sum[i]>1e+9:
        break
for i in range(m):
    b_sum.append(b[i]+b_sum[i])
    if b_sum[i]>1e+9:
        break
        
ans = 0
for i in range(len(b_sum)):
    if a_sum[i]>k:
        break
    time = k - a_sum[i]
    for j in range(len(b_sum)):
        if time<b_sum[j+1]:
            break
    if time>=b_sum[m]:
        j = m
    ans = max(ans,i+j)
    
print(ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a_sum = [0]
b_sum = [0]
for i in range(n):
    a_sum.append(a[i]+a_sum[i])
    if a_sum[i]>k:
        break
for i in range(m):
    b_sum.append(b[i]+b_sum[i])
    if b_sum[i]>k:
        break
        
ans = 0
y = len(b_sum)-1
for i in range(len(a_sum)):
    if a_sum[i]>k:
        break
    time = k - a_sum[i]
    for j in range(y,-1,-1):
        if time>=b_sum[j]:
            y = j
            break
    if time>=b_sum[len(b_sum)-1]:
        j = len(b_sum)-1
    ans = max(ans,i+j)
    
print(ans)
from fractions import gcd
n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
for i in a:
    c=gcd(c,a)
print(c)


### FIXED CODE ###


n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

for i in a:
    c=gcd(c,i)
print(c)
def calcExValue(N):
    ev = []
    for i in range(1, N +1):
        ev.append(i * (1/N))
    return(sum(ev))

N, K = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]

max_numbers = []
max_num = 0

for i in range(N-K+1):
    if sum(array[i:i+K]) > max_num:
        max_num = sum(array[i:i+K])
        max_numbers = array[i:i+K]

exv = 0
ev_dict = {}
for n in max_numbers:
    if n in ev_dict:
        evn += ev_dict[n]
    else :
        ev_dict.setdefault(n, 0)
        ev = calcExValue(n)
        exv += ev
        ev_dict[n] = ev
    
print(exv)

### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
numbers = [int(i) for i in input().split()]

ary = np.array([(1 + n) / 2 for n in numbers])

cumsum = ary.cumsum()

max_exv = cumsum[K-1]
for i in range(N - K):
    if cumsum[i+K] - cumsum[i] > max_exv:
        max_exv = cumsum[i+K] - cumsum[i]
    
print(max_exv)
a = defaultdict(int)
for w in input():
  a[w] += 1
print('Yes' if sum(c % 2 for c in a.values()) == 0 else 'No')


### FIXED CODE ###

from collections import defaultdict

a = defaultdict(int)
for w in input():
  a[w] += 1
print('Yes' if sum(c % 2 for c in a.values()) == 0 else 'No')
N = int(input())
A = [int(_) for _ in input().split()]
 
i = 0
j = 0
x = 0
 
result = 0
 
while i < N or j < N:
    while j < N and x & A[j] == 0:
        x |= A[j]
        j += 1
    result += j - i
    x &= ~A[i]
    i += 1
    
print(result)
N = int(input())
A = [int(_) for _ in input().split()]

i = 0
j = 0
x = 0

result = 0

while i < N or j < N:
    while j < N and x & A[j] == 0:
        x |= A[j]
        j += 1
    result += j - i
    x &= ~A[i]
    i += 1
    
print(result)
提出情報

### FIXED CODE ###

import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n = int(input())

a = l()

ans = 0
l = 0
r = 0
su = 0
for i in range(n):
	while(r < n and (su^a[r]) == (su + a[r])):
		su += a[r]
		r += 1
	ans += r - i
	if r == i:
		r += 1
	else:
		su -= a[i]
print(ans)
from math import log, ceil


def _check(aaa):
    ret = 0
    cur = 0
    pa = -1
    for a in aaa:
        if pa == a:
            ret += cur
        else:
            d = ceil(log(pa / a, 4)) * 2
            cur += d
            ret += cur
            # print(pa, a, d, cur, ret)
        pa = a
    return ret


def check(x, aaa):
    ret = x
    ret += _check(aaa[x:])
    ret += _check(reversed(aaa[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, aaa)
        res2 = check(m2, aaa)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m2
        else:
            r = m1
    return check(r, aaa)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
import numpy as np

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

C = np.arange(A,B+1)

if max(C)<=K:
    for x in range(B):
        print(C[x])

        
else:
    for y in range(K):
        print(C[y])
    for z in range(B-K-2,B-2):
        print(C[z])


### FIXED CODE ###

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

L = B - A + 1

if L >= 2*K:
    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)
s = input().counter(1)
print (s)


### FIXED CODE ###

print(input().count("1"))
str = input()
if str[0] == "7" or str[1] == "7" or str[2] == "7": print("Yes")
else: print("No")

### FIXED CODE ###

num = int(input())
ans = 0
for x in range(num + 1):
    if x % 3 == 0 or x % 5 == 0: pass
    else: ans += x
print(ans)
A, B = map(int, input().split())
import math
c = math.ceil((B - A) / (B - 1))
print(c + 1)


### FIXED CODE ###

A, B = map(int, input().split())
import math
c = math.ceil((B - A) / (A - 1))
print(c + 1)
s = list(str(input()))
p = 0
for i in s:
    if i == o:
        p = p + 100
        
print(700 + p)

### FIXED CODE ###

s = list(str(input()))
p = 0
for i in s:
    if i == 'o':
        p = p + 100
        
print(700 + p)
import numpy as np

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

base = np.zeros(n)
seen = np.diag(np.ones(n))
temp = 1

for i in range(m):
  a,b = map(int,input().split())
  seen[a-1] += seen[b-1]
  seen[b-1] += seen[a-1]
  
seen = np.where(seen > 0,1,0) - np.diag(np.ones(n))
ans = 0
for i in range(n):
  temp = np.multiply(seen[i],h)
  temp_1 = np.max(temp)
  if h[i] > temp_1:
    ans += 1
  elif temp_1 == 0:
    ans += 1
    
print(ans)

### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
h = list(map(int,input().split()))

base = np.ones(n)

for i in range(m):
  a,b =  map(int,input().split())
  if h[a-1] > h[b-1]:
    base[b-1] = 0
  elif h[a-1] < h[b-1]:
    base[a-1] = 0
  elif h[a-1] == h[b-1]:
    base[a-1] = 0
    base[b-1] = 0
    
print(int(np.sum(base)))
import sys
n=int(input())
s=[[int(i) for i in l.split()] for l in sys.stdin]
for cx in range(101):
  for cy in range(101):
    H=[]
    Z=[]
    for i in range(n):
      x,y,h=s[i]
      if h==0:
        H.append(abs(x-cx)+(y-cy)+h)
      else:
        Z.append(abs(x-cx)+(y-cy))
    if H.count(H[0])==len(H) and min(Z)>=H[0]:
      print(cx,cy,H)
      exit()

### FIXED CODE ###

import sys
n=int(input())
s=[[int(i) for i in l.split()] for l in sys.stdin]
for cx in range(101):
  for cy in range(101):
    H=[]
    Z=[]
    for i in range(n):
      x,y,h=s[i]
      if h!=0:
        H.append(abs(x-cx)+abs(y-cy)+h)
      else:
        Z.append(abs(x-cx)+abs(y-cy))
    if len(Z)==0:
      Z.append(10**18)
    if H.count(H[0])==len(H) and min(Z)>=H[0]:
      print(cx,cy,H[0])
      exit()
n,k=map(int,input().split())
a,b=map(int,input().split())
d=[]*(10**5+1)
for i in range(n-1):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>k:
    print(i)
    break
  else:k-=d[i]


### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
    sd[j]=e[i][1]+s-mx
    mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

### FIXED CODE ###

n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
      sd[j]+=e[i][1]+s-mx
      mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)
A,B,C,D,E,F = map(int,input().split())
a_limit = int(-(-F//(100*A)))
b_limit = int(-(-F//(100*B)))
c_limit = int(-(-F*E//(100*C)))
d_limit = int(-(-F*E//(100*D)))

water_cand = []
for i in range(a_limit):
  for j in range(b_limit):
    water_cand.append(100*A*i+100*B*j)

water_cand = [x for x in list(set(water_cand)) if 0<x<F]

sugar_cand = []
for i in range(c_limit):
  for j in range(d_limit):
    sugar_cand.append(C*i + D*j)

sugar_cand = list(set(sugar_cand))

max_dens = 0
ans = 0
for i in water_cand:
  for j in sugar_cand:
    total = i + j
    dens = float(j)/total
    if total <= F and float(j)/i <= (E/100) and max_dens<dens:
            max_dens = dens
            ans_total = total
            ans_sugar = j
            
print(ans_total, ans_sugar)

### FIXED CODE ###

A,B,C,D,E,F = map(int,input().split())

a_limit = int(-(-F//(100*A)))
b_limit = int(-(-F//(100*B)))
c_limit = int(-(-F*E//(100*C)))
d_limit = int(-(-F*E//(100*D)))

water_cand = []
for i in range(a_limit):
  for j in range(b_limit):
    water_cand.append(100*A*i+100*B*j)

water_cand = [x for x in list(set(water_cand)) if 0<x<F]

sugar_cand = []
for i in range(c_limit):
  for j in range(d_limit):
    sugar_cand.append(C*i + D*j)

sugar_cand = list(set(sugar_cand))

max_dens = 0
ans_total = 100*A
ans_sugar = 0
for i in water_cand:
  for j in sugar_cand:
    total = i + j
    dens = float(j)/total
    if total <= F and float(j)/i <= (E/100) and max_dens<dens:
      max_dens = dens
      ans_total = total
      ans_sugar = j
            
print(ans_total, ans_sugar)
a,b,c=map(str,input().split())
printmax((int(a+b)+int(c),int(a)+int(b+c)))

### FIXED CODE ###

L=sorted(list(map(str,input().split())))
print(int(L[2]+L[1])+int(L[0]))
b = input()

bases = ('A', 'C', 'G', 'T')

for idx, base in enumerate(bases):
  if base == b:
    print(bases[int(~bin(idx))])
    break


### FIXED CODE ###

b = input()

bases = ('A', 'C', 'G', 'T')

for idx, base in enumerate(bases):
  if base == b:
    print(bases[int(~(idx))])
    break
from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while ans==0:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

L=list(set(A))

while True:
  if len(L)==1:
    ans = L[0]
    break
  if min(L)==1:
    ans = 1
    break
  if sum(list(map(lambda x: x%min(L), L)))==0:
  	ans = min(L)
  g = G(L[-2], L[-1])
  L[-2] = g
  L.pop()

print(ans)
    

### FIXED CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

L = np.array(list(set(A)))
mini = np.min(L)
yaku = [1]
i=2
r_mini = np.sqrt(mini)
while i<=r_mini:
  if mini%i==0:
    yaku.append(i)
  i+=1
yaku2 = list(map(lambda x: int(mini/x), yaku))
yaku = yaku[::-1]
yaku2.extend(yaku)
for y in yaku2:
  if np.sum(L%y)==0:
    ans = y
    break

print(ans)
n = str(input())

li_n = list(map(int,n))

s = li_n[-1] + 1

ans = int(n) - s

ans2 = list(map(int,str(ans)))

print(sum(ans2))

### FIXED CODE ###

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

if len(n) == 1:
    print(n[0])
    exit()

if n[1:].count(9) == len(n) -1:
    print(n[0] + (len(n)-1)*9)
else:
    print(n[0]-1 + (len(n)-1)*9)
import decimal 



def resolve():
    a,b,c = [decimal.Decimal(i) for i in input().split()]

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

if __name__ == "__main__":
    unittest.main()

### FIXED CODE ###

import decimal 



def resolve():
    a,b,c = [decimal.Decimal(i) for i in input().split()]

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

if __name__ == "__main__":
    resolve()
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cum_a = [0]*(n+1)
for i, v in enumerate(a):
    cum_a[i+1] = cum_a[i]+a[i]
cum_b = [0]*(m+1)
for i, v in enumerate(b):
    cum_b[i+1] = cum_b[i]+b[i]


a_idx = n
b_idx = 0
res = 0
for i in range(n+1):
    current_a_idx = a_idx-i
    sum_a = cum_a[current_a_idx]
    if sum_a > k:
        continue
    sum_b = cum_b[b_idx]
    while sum_a+sum_b <= k and b_idx < m:
        b_idx += 1
        sum_b = cum_b[b_idx]
        if sum_a + sum_b > k:
            b_idx -= 1
            break
    res = max(b_idx+current_a_idx, res)
a_idx = 0
b_idx = m
for i in range(n+1):
    current_b_idx = b_idx-i
    sum_b = cum_b[current_b_idx]
    if sum_b > k:
        continue
    sum_a = cum_a[a_idx]
    while sum_a+sum_b <= k and a_idx < n:
        a_idx += 1
        sum_a = cum_a[a_idx]
        if sum_a + sum_b > k:
            a_idx -= 1
            break
    res = max(current_b_idx+a_idx, res)


print(res)



### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cum_a = [0] * (n + 1)
for i, v in enumerate(a):
    cum_a[i + 1] = cum_a[i] + a[i]
cum_b = [0] * (m + 1)
for i, v in enumerate(b):
    cum_b[i + 1] = cum_b[i] + b[i]

a_idx = n
b_idx = 0
res = 0
for i in range(n + 1):
    current_a_idx = a_idx - i
    sum_a = cum_a[current_a_idx]
    if sum_a > k:
        continue
    sum_b = cum_b[b_idx]
    while sum_a + sum_b <= k and b_idx < m:
        b_idx += 1
        sum_b = cum_b[b_idx]
        if sum_a + sum_b > k:
            b_idx -= 1
            break
    res = max(b_idx + current_a_idx, res)
a_idx = 0
b_idx = m
for i in range(m + 1):
    current_b_idx = b_idx - i
    sum_b = cum_b[current_b_idx]
    if sum_b > k:
        continue
    sum_a = cum_a[a_idx]
    while sum_a + sum_b <= k and a_idx < n:
        a_idx += 1
        sum_a = cum_a[a_idx]
        if sum_a + sum_b > k:
            a_idx -= 1
            break
    res = max(current_b_idx + a_idx, res)

print(res)
N=int(input())
Destinations=[[0,0,0]]
for i in range(N):
    Destinations.append(list(map(int, input().split())))

for i in range(N-1):
    x_distance = Destinations[i+1][1] - Destinations[i][1]
    y_distance = Destinations[i+1][2] - Destination[i][2]
    if x_distance < 0:
        x_distance = -x_distance
    if y_distance < 0:
        y_distance = -y_distance
    move_distance = x_distance+y_distance

    move_time = Destinations[i+1][0] Destinations[i][0]

    if move_distance == 0:
        print("No")

    if move_distance > move_time*1:
        print("No")
    elif move_distance%2 == move_time%2:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N=int(input())
Destinations=[[0,0,0]]
for i in range(N):
    Destinations.append(list(map(int, input().split())))

for i in range(N):
    x_distance = Destinations[i+1][1] - Destinations[i][1]
    y_distance = Destinations[i+1][2] - Destinations[i][2]
    if x_distance < 0:
        x_distance = -x_distance
    if y_distance < 0:
        y_distance = -y_distance
    move_distance = x_distance+y_distance

    move_time = Destinations[i+1][0] - Destinations[i][0]

    if move_distance == 0:
        print("No")
        break

    if move_distance > move_time*1:
        print("No")
        break
    elif move_distance%2 == move_time%2:
        pass
    else:
        print("No")
        break

    if i == N-1:
        print("Yes")
n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in x:
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(0)
else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])


### FIXED CODE ###

n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])
N, M = map(int, input().split())
PM = []
for i in range(N):
  PM = input().split()
  P = str(PM[0]).zfill(6)
  M = str(PM[1]).zfill(6)
  print(P + M)

### FIXED CODE ###

X,Y=map(int,input().split())
print(X+Y//2)
import math

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

r = 0

if n == s:
    print(n + 1)
    exit()
elif n < s:
    print(-1)
    exit()
elif s == 1:
    print(n)
    exit()

nn = int(math.sqrt(n)) + 1    

for i in range(2, nn):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
for i in range(2, nn):
    nt = n
    st = 0

    tt = (n - s) // (i + 1)
    
    while nt > 0:
        st += nt % tt
        nt //= tt

    if st == s:
        print(tt)
        exit()

print(-1)

### FIXED CODE ###

import math

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


r = 0

if n == s:
    print(n + 1)
    exit()
elif n < s:
    print(-1)
    exit()

sq = int(math.sqrt(n))


# 2 <= d <= √n
for i in range(2, sq+1):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
# √n < d <= n
for i in range(sq+1, 0, -1):
    b = (n - s) // i + 1
    
    st = n % b + n // b

    if n // b != b and st == s:
        print(b)
        exit()

print(-1)
import sys
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
dif=[]
if m<=n:
  print(0)
  sys.exit()
else:
  for i in range(n-1):
    dif.append(x[i+1]-x[i]-1)
  dif.sort(reverse=True)
  ans=x[n-1]-x[0]+1
  for j in range(n):
    ans-=dif[j]
  print(ans-n+1)
  

### FIXED CODE ###

import sys
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
dif=[]
if m<=n:
  print(0)
  sys.exit()
else:
  for i in range(m-1):
    dif.append(x[i+1]-x[i])
  dif.sort(reverse=True)
  ans=x[m-1]-x[0]
  for j in range(n-1):
    ans-=dif[j]
  print(ans)