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

n,q=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a-1].append(b)
    ab[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
yn=[0]*n
yn[0]=1
n1=1
queue=[]
queue2=[]
for i in range(n+10):
    for j in range(len(ab[n1-1])):
        if yn[ab[n1-1][j]-1]==0:
            yn[ab[n1-1][j]-1]=1
            queue.append(ab[n1-1][j])
    for j in range(len(queue)):
        ans[queue[0]-1]+=ans[n1-1]
        queue2.append(queue[0])
        del(queue[0])
    if len(queue)==0 and len(queue2)==0:
        break
    n1=queue2.pop(-1)
print(*ans)


### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
queue=deque()
queue.append(0)
seen=[False]*n
for i in range(n):
    if len(queue)==0:
        break
    num1=queue.popleft()
    seen[num1]=True
    num2=num[num1]
    for j in range(len(num2)):
        if seen[num2[j]-1]==False:
            ans[num2[j]-1]+=ans[num1]
            queue.append(num2[j]-1)
for i in ans:
    print(i)
### BUGGY CODE ###

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
for i in [0]*M:
	b,c = map(int,input().split(' '))
	A.extend([c]*b)

A.sort(reverse=True)
print(sum(A[:N]))







### FIXED CODE ###

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
A.sort(reverse=True)
A.append(-1)


ans = 0
BC = [list(map(int,input().split(' '))) for i in [0]*M]
BC.sort(reverse=True, key= lambda x:x[1])
BC.append([0,-1])

i = 0
j = 0
k = N
while(True):
	if k <= 0:
		break
	a = A[i]
	b,c = BC[j]
	if a > c:
		k = k-1
		ans += A[i]
		i = i+1
	else:
		if b < k:
			ans += b*c
			k = k-b
			j = j+1
		else:
			ans += k*c
			break

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

N, M = map(int, input().split())
PY = []
ken_d = {k:[]  for k in range(1, N+1)}

for i in range(M):
    p = list(map(int,input().split()))
    PY.append(p)
    ken_d[p[0]].append(p[1])

for k in ken_d.keys():
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict,deque
from itertools import combinations
from heapq import heappush, heappop
xs,ys,xt,yt = map(int,input().split())
N = int(input())
xyr = [list(map(int,input().split())) for i in range(N)]
xyr = [[xs,ys,0]] + xyr + [[xt,yt,0]]

cost = {}
for s,t in combinations(range(N+2),2):
    x1,y1,r1 = xyr[s]
    x2,y2,r2 = xyr[t]
    R = pow((x2-x1)**2+(y2-y1)**2,0.5)
    c = max(0, R-r1-r2)
    cost[(s,t)] = c
    cost[(t,s)] = c

h = [(0,0)]
visited = [False] * (N+2)
dist = [10**15] * (N+2)
dist[0] = 0
while h:
    v,d = heappop(h)
    for nv in range(N+2):
        if v == nv:
            continue
        temp = d + cost[(v,nv)]
        if temp < dist[nv]:
            dist[nv] = temp
            heappush(h, (nv,temp))

print(dist[N+1])








### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict,deque
from itertools import combinations
from heapq import heappush, heappop

xs,ys,xt,yt = map(int,input().split())
N = int(input())
xyr = [list(map(int,input().split())) for i in range(N)]

#import random
#N = 1000
#xs,ys = (-10**9,-10**9)
#xt,yt = (10**9, 10**9)
#xyr = [[random.randint(-10**9, 10**9),random.randint(-10**9, 10**9),random.randint(1,10)] for i in range(N)]
#xyr = [[2*i,2*i,1] for i in range(N)]

xyr = [[xs,ys,0]] + xyr + [[xt,yt,0]]

cost = {}
for s in range(0,N+1):
    for t in range(s+1,N+2):
        x1,y1,r1 = xyr[s]
        x2,y2,r2 = xyr[t]
        R = pow((x2-x1)**2+(y2-y1)**2,0.5)
        c = max(0, R-r1-r2)
        cost[(s,t)] = c
        cost[(t,s)] = c

h = [(0,0)]
dist = [10**15] * (N+2)
dist[0] = 0
while h:
    d,v = heappop(h)
    if dist[v] < d:
        continue
    for nv in range(N+2):
        if v == nv:
            continue
        temp = d + cost[(v,nv)]
        if temp < dist[nv]:
            dist[nv] = temp
            heappush(h, (temp,nv))

print(dist[N+1])
### BUGGY CODE ###

INF = 1000000000

def BellmanFord(s, v, graph):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for k in range(0, v):
            dp1 = [dp[k] + graph[k][j] if dp[k] != INF and graph[k][j] != INF and dp[j] > dp[k] + graph[k][j]
                  else dp[j]
                  for j in range(0, v) ]
            if dp1 != dp and i == v - 1:
                return -1
            dp = dp1
    return dp

dp = []
line = input()
v, e = list(map(int, line.split()))
graph = [ [INF] * v for _ in range(0, v)]
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    graph[s][t] = d
for s in range(0, v):
    dp = BellmanFord(s, v, graph)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))


### FIXED CODE ###

INF = 999999999999

def BellmanFord_edge(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        dp1 = dp[:]
        for fr, to, d in edge:
            if dp[fr] == INF:
                continue
            if dp[to] > dp[fr] + d:
                dp[to] = dp[fr] + d
                if i == v - 1:
                    return -1
        if dp == dp1:
            break
    return dp

def BellmanFord_graph(s, v, graph):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for k in range(0, v):
            dp1 = [dp[k] + graph[k][j] if dp[k] != INF and graph[k][j] != INF and dp[j] > dp[k] + graph[k][j]
                  else dp[j]
                  for j in range(0, v) ]
            if dp1 != dp and i == v - 1:
                return -1
            dp = dp1
    return dp

dp = []
line = input()
v, e = list(map(int, line.split()))
graph = [ [INF] * v for _ in range(0, v)]
edge = []
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    edge += [[s, t, d]]
    graph[s][t] = d
for s in range(0, v):
#    dp = BellmanFord(s, v, graph)
    dp = BellmanFord_edge(s, v, edge)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))
### BUGGY CODE ###

N, M, Q = [int(_) for _ in input().split()]
train = [[int(_) for _ in input().split()] for i in range(M)]
question = [[int(_) for _ in input().split()] for i in range(Q)]

l = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        if i >= j:
            a = train.count([j+1, i+1])
        else:
            a = train.count([i+1, j+1])
        l[i][j] = s + a
        s += a

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if i == 0:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][i-1]
        ans += d
    print(ans)


### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]

l = [[0 for i in range(N+1)] for j in range(N+2)]
for t in [input().split() for _ in range(M)]:
    i = int(t[0])
    j = int(t[1])
    l[i][j] += 1

for k in range(N):
    for i in range(1, N-k+1):
        j = i + k
        l[i][j] += l[i][j-1] + l[i+1][j] - l[i+1][j-1]

for k in [input().split() for _ in range(Q)]:
    p = int(k[0])
    q = int(k[1])
    print(l[p][q])
### BUGGY CODE ###

# encoding: "utf-8"

from collections import defaultdict

# class Stdin:
#     @staticmethod
#     def read_line(converter=str):
#         return [converter(x) for x in input().split()]
    
#     @staticmethod
#     def read_lines(n, converter=str):
#         result = list()
#         for _ in range(n):
#             result.append(Stdin.read_line(converter))
#         return result
    
#     @staticmethod
#     def convert(data, converter):
#         assert(len(data) == len(converter))
#         return tuple(map(lambda x, f: f(x), data, converter))

#     @staticmethod
#     def convert_lines(datas, n, converter):
#         return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    cnt = xs.count(fst)
    # for x in xs:
    #     if x != fst:
    #         break
    #     cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    # xs = Stdin.read_line(converter=int)
    xs = [int(x) for x in input().split()]
    xs.sort()
    ys = defaultdict(int)
    while xs:
        key = xs[0]
        cnt, xs = first_count_and_pop(xs)
        ys[key] += cnt
        ys[key-1] += cnt
        ys[key+1] += cnt

    print(max(ys.values()))

# def main_():
#     input()
#     xs = Stdin.read_line(converter=int)
#     xs.sort()
#     counts = list()
#     for i in range(100000):
#         if not xs:
#             counts.extend([0] * (100000 - len(counts)))
#             break     
#         elif i == xs[0]:
#             cnt, xs = first_count_and_pop(xs)
#             counts.append(cnt)
#         else:
#             counts.append(0)
#     m = 0
#     for i in range(0, 100000):
#         if i == 0:
#             temp = counts[i] + counts[i+1]
#         elif i == 100000 - 1:
#             temp = counts[i-1] + counts[i]
#         else:
#             temp = counts[i-1] + counts[i] + counts[i+1]
#         if m < temp:
#             m = temp
#     print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

s=input()
q=int(input())
cnt=0
for i in range(q):
    query=list(input().split())
    if query[0]=="1":
        cnt+=1
    else:
        if (cnt+int(query[1]))%2==1:
            s=query[2]+s
        else:
            s=s+query[2]
if cnt%2==1:
    s=s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s=deque(input())
q=int(input())
cnt=0
for i in range(q):
    query=list(input().split())
    if query[0]=="1":
        cnt+=1
    else:
        if (cnt+int(query[1]))%2==1:
            s.appendleft(query[2])
        else:
            s.append(query[2])
if cnt%2==1:
    s=reversed(s)
print("".join(s))
### BUGGY CODE ###

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

diff = 2020202020 * 200000 + 1

for i in range(N):
    temp1 = A[:i+1]
    temp2 = A[i+1:]
    temp3 = abs(sum(temp2) - sum(temp1))
    if temp3 <= diff:
        mid = i
        diff = temp3

print(diff)


### FIXED CODE ###

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


diff = 2020202020 * 200000 + 1
tot = sum(A)

temp1 = 0

for i in range(N):
    temp1 += A[i]
    # temp2 = A[i+1:]
    temp3 = abs(tot - 2 * temp1)
    if temp3 <= diff:
        # mid = i
        diff = temp3
    else:
        break

print(diff)
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
N=input()

A=[]
for i in range(N):
	x,y=map( int, raw_input().split() )
	A.append( [i+1,x,y] )

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


hq=[]
for i in range(N-1):
	idx1,x1=A[i][0], A[i][1]
	idx2,x2=A[i+1][0],A[i+1][1]
	heappush(hq, (x2-x1, idx1,idx2) )

A.sort(key=lambda x:x[2])


for i in range(N-1):
	idx1,y1=A[i][0], A[i][2]
	idx2,y2=A[i+1][0],A[i+1][2]
	heappush(hq, (y2-y1, idx1,idx2) )


par=[ i for i in range(N+1)]

def root(x):
	if par[x]==x: return x
	else:
		par[x]=root(par[x])
		return par[x]
def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y


ans=0
while hq:
	cost,x,y=heappop(hq)

	if not same(x,y):
		unite(x,y)
		ans+=cost

print ans


### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**6)
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	#２点が同じ根でない場合は、木を結合する
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans
### BUGGY CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s,t = map(int, input().split())

before_dict = {}
after_dict = {}
after_3 = {}

for i in range(1,n+1):
    before_dict[i] =[]
    after_dict[i] = []
    after_3[i] = []

for i in range(m):
    u, v = uv[i]
    before_dict[v].append(u)
    after_dict[u].append(v)

for i in range(m):
    u, v = uv[i]
    for j in before_dict[u]:
        for k in after_dict[v]:
            if( j != k):
                after_3[j].append(k)

from collections import deque
d = deque()
d.append(s)

length = [-1] * (n+1)
length[s] = 0

check = True

while(check):
    if(len(d) == 0):
        break
    num = d.popleft()
    for i in after_3[num]:
        if(length[i] == -1):
            length[i] = length[num] + 1
            d.append(i)

    if(length[t] > -1):
        break

print(length[t])


### FIXED CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

next_dict = {}

for i in range(1,n*3 + 1):
    next_dict[i] = []

for i in range(m):
    u,v = uv[i]
    for j in range(3):
        next_dict[u + (j * n)].append((v + ((j+1)%3 * n )))

from collections import deque
d = deque()
d.append(s)

length = [-1] * (3*n + 1)
length[s] = 0

while(True):
    if(len(d) == 0):
        break

    num = d.popleft()
    for i in next_dict[num]:
        if( length[i] == -1 ):
            d.append(i)
            length[i] = length[num] + 1

    if(length[t] != -1):
        break

print(length[t] // 3)
### BUGGY CODE ###

n = int(input())
mod = 10**18
li = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans = ans * li[i]
if ans > mod:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
mod = 10**18
li = list(map(int, input().split()))
li.sort()
ans = 1
for i in range(n):
    ans *= li[i]
    if ans > mod:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

MOD = 10**9 + 7
MAX = r2 + c2 + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


def func(a, b):
    res = 0
    for i in range(a + 1):
        res += comb(i + b + 1, i + 1)
        res %= MOD
    return res


ans = func(r2, c2) - func(r2, c1 - 1) - func(r1 - 1, c2) + func(r1 - 1, c1 - 1)
ans %= MOD
print(ans)


### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())

MOD = 10**9 + 7
MAX = r2 + c2 + 10
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


def func(a, b):
    res = 0
    for i in range(a + 1):
        res += comb(i + b + 1, i + 1)
        res %= MOD
    return res


ans = func(r2, c2) - func(r2, c1 - 1) - func(r1 - 1, c2) + func(r1 - 1, c1 - 1)
ans %= MOD
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
g=M//N#最大公約数になる可能性のある最大値
for i in range(g):
  if M%(g-i)==0:
    print(g-i)
    exit()

### FIXED CODE ###

import sys
input= sys.stdin.readline

N,M = map(int,input().split())
g=M//N#最大公約数になる可能性のある最大値
for i in range(g):
  if M%(g-i)==0:
    print(g-i)
    exit()
  if M%(N+i)==0:
    print(M//(N+i))
    exit()
### BUGGY CODE ###

def main():
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  mod = 10**9+7
  rng = 10100
  fctr = [1]
  finv = [1]
  for i in range(1,rng):
    fctr.append(fctr[-1]*i%mod)
  for i in range(1,rng):
    finv.append(pow(fctr[i],mod-2,mod))
  def cmb(n,k):
    if n<0 or k<0:
      return 0
    else:
      return fctr[n]*finv[n-k]*finv[k]%mod
  dp0 = [0 for i in range(n+1)]
  dp1 = [0 for i in range(n+1)]
  dp0[0] = 1
  ans = 0
  for i in range(1,k+1):
    x = a[i-1]
    if i%2:
      for j in range(n+1):
        for t in range(min(n-j,x)+1):
          dp1[j+t] = (dp1[j+t]+dp0[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
      dp0 = [0 for i in range(n+1)]
    else:
      for j in range(n+1):
        for t in range(min(n-j,x)+1):
          dp0[j+t] = (dp0[j+t]+dp1[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
      dp1 = [0 for i in range(n+1)]
  if k%2:
    print(dp1[n])
  else:
    print(dp0[n])
main()

### FIXED CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])
### BUGGY CODE ###

count = int(input())

str_data = list()
result = 0
for i in range(count):
  judge_str = sorted(input())
  for data in str_data:
    if judge_str == data:
      result += 1
    
  str_data.append(judge_str)
print(result)

### FIXED CODE ###

count = int(input())
 
str_data = dict()
result = 0
for i in range(count):
    judge_str = ''.join(sorted(input()))
    if judge_str in str_data:
        str_data[judge_str] += 1
        result += str_data[judge_str]
    else:
        str_data[judge_str] = 0
    
print(result)
### BUGGY CODE ###

n = int(input())
l = []
for i in range(n):
    s = input()
    if s not in l:
        l.append(s)
print(len(l))


### FIXED CODE ###

n = int(input())
l = set()
for i in range(n):
    s = input()
    if s not in l:
        l.add(s)
print(len(l))
### BUGGY CODE ###

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())
A=prime_factorize(n)
l=len(A)

res=10**13
for i in range(2**l):
	cnt=1
	for j in range(l):
		if (i>>j)&1:
			cnt *= A[j]
	cnt = n//cnt + cnt
	res=min(cnt,res)
print(res-2)

### FIXED CODE ###

from math import sqrt
n=int(input())
ans=n+1
for i in range(1,int(sqrt(n))+1):
	if n%i==0:
		ans = i+n//i
print(ans-2)
### BUGGY CODE ###

l=[]
n=int(input())
for x in range(1,10**2+1):
    if x**2>n:continue
    for y in range(1,10**2+1):
        if x**2+y**2>n:continue
        for z in range(1,10**2+1):
            if x**2+y**2+z**2>n:continue
            l.append(x**2+y**2+z**2+x*y+y*z+z*x)

for x in range(1,n+1):
    print(l.count(x))

### FIXED CODE ###

import collections

l=[]
n=int(input())
for x in range(1,10**2+1):
    if x**2>n:continue
    for y in range(1,10**2+1):
        if x**2+y**2>n:continue
        for z in range(1,10**2+1):
            if x**2+y**2+z**2>n:continue
            l.append(x**2+y**2+z**2+x*y+y*z+z*x)

c=collections.Counter(l)
for x in range(1,n+1):
    print(c[x])
### BUGGY CODE ###

# -*- coding:utf-8 -*-
S = list(input())

loop_idx = 0
loop_len = -(-len(S)//2)
cnt = 0

if len(S) == 1:
    pass
else:
    while loop_idx < loop_len:
        """
        if S[0] == "W":
                S.pop(0)
        if S[-1] == "B":
                S.pop(-1)
        """
        for i in range(len(S)-1,loop_idx,-1):
            if S[i]=="W" and S[i-1] == "B":
                cnt += 1
                S[i],S[i-1] = "B","W"
        loop_idx += 1
        #print(S)
print(cnt)

### FIXED CODE ###

# -*- coding:utf-8 -*-
S = list(input())

cnt_b = 0 
ans = 0

for i in range(len(S)):
    if S[i] == "B":
        cnt_b += 1
    if S[i] == "W":
        ans += cnt_b
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
flag = 0b0
for i in range(q) :
    t = input()
    if t == "1" :
        flag ^= 1
        continue
    if (int(t[2]) - flag) == 1 :
        s = t[4] + s
    else :
        s = s + t[4]
if flag == 0 :
    print(s)
else :
    print(s[::-1])

### FIXED CODE ###

right = input()
Q = int(input())
flag = 0b1
left = ""
for i in range(Q):
    q = input()
    if q == "1":
        flag ^= 1
        continue
    m,f,c = q.split(" ")
    f = int(f)
    left += c*(1-flag)*(f-1)
    right += c*flag*(f-1)
    left += c*flag*(2-f)
    right += c*(1-flag)*(2-f)
if flag == 1:
    print(left[::-1]+right)
else:
    print(right[::-1]+left)
### BUGGY CODE ###

N,K = map(int,input().split())
X = list(map(int,input().split()))
ANS = []
for i in range(N-K+1) :
    L = X[i:K+i]
    cplus = 0
    cminus = 0
    czero = 0
    for j in range(len(L)) :

        if L[j] > 0 :
            cplus += 1
        elif L[j] < 0 :
            cminus += 1
        else :
            czero += 1
        if (cplus == K-czero) or (cminus == K-czero):
            ANS.append(max(abs(min(L)),max(L)))
        else :
            ANS.append(min(abs(min(L))*2+abs(max(L)),abs(max(L))*2+abs(min(L))))
print(min(ANS))



### FIXED CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
ANS = []
for i in range(len(L)-K+1) :
    p = L[i]
    q = L[i+K-1]
    if p*q == 0 :
        r = abs(p-q)
    elif p*q < 0 :
        r = 2*min(abs(p),q) + max(abs(p),q)
    else :
        if p > 0 :
            r = q
        else :
            r = abs(p)
    ANS.append(r)
ans = min(ANS)
print(ans)
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int,input().split()))
P.append(0)
M = 0

for i in range(N):
    if P[i+K-1] == 0:
        break
    B = P[i:i+K]
    S = sum(B)
    M = max(M, S)

ans = 0.5 * (M + K)

print(ans)

### FIXED CODE ###

import numpy as np
import numpy

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

S = numpy.cumsum(P)
P.append(0)
M = S[K-1]

for i in range(0,N):
    if P[i+K] == 0:
        break
    A = S[i+K] - S[i]
    M = max(M, A)

ans = 0.5 * (M + K)

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

n = int(input())
ss = [sorted(input()) for i in range(n)]
cnt=0
for i in range(n):
  for j in range(i+1, n):
    if ss[i]==ss[j]:
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
string_list=["".join(sorted(list(input()))) for i in range(n)]
counter=Counter(string_list)
cnt=0
for k, v in counter.items():
  cnt+=int(v*(v-1)/2)
print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
now = n

while True:
  n = abs(n - k)
  if n >= now:
    break
  now = n
print(now)

### FIXED CODE ###

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

now = abs((n % k) - k)
if now < n%k:
  print(now)
else:
  print(n%k)