Harryxun/stf_run huggingface dataset:
import queue
n,m = map(int,input().split()) 

conne = [[0]*(n+1) for _ in range(m+1)]
dist = [99999]*(n+1)
par = [0] * (n+1)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a][b] = 1
    conne[b][a] = 1
    
q=queue.Queue()
dist[1] = 0
q.put((1,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in range(len(conne[x])):
        if conne[x][i]==1 and dist[i]>d+1:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1
            
for i in par[2:]:
    print(i)
    


### FIXED CODE ###

import queue
import sys
imput = sys.stdin.readline

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

conne = [[] for _ in range(n)]
dist = [99999]*(n)
par = [0] * (n)

for i in range(m):
    a,b = map(int,input().split()) 
    conne[a-1].append(b-1)
    conne[b-1].append(a-1)
    
q=queue.Queue()
dist[0] = 0
q.put((0,0))

while not q.empty():
    
    x,d = q.get()
    
    for i in conne[x]:
        if dist[i]==99999:
            q.put((i,d+1))
            par[i] = x
            dist[i] = d+1

print("Yes")    

for i in par[1:]:
    print(i+1)
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse= True)
B.sort(reverse= True)
C.sort(reverse= True)
LIS = []
for i in range(X):
    INTB = 3000//(j+1)
    for j in range(min(INTB+1,Y):
        INT = 3000//((i+1)*(j+1))
        for k in range(min(INT+1,Z)):
            SUM = A[i] + B[j] + C[k]
            LIS.append(SUM)
LIS.sort(reverse = True)
for i in range(K):
    print(LIS[i])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse= True)
B.sort(reverse= True)
C.sort(reverse= True)
LIS = []
for i in range(X):
    INTB = 3000//(i+1)
    for j in range(min(INTB+1,Y)):
        INT = 3000//((i+1)*(j+1))
        for k in range(min(INT+1,Z)):
            SUM = A[i] + B[j] + C[k]
            LIS.append(SUM)
LIS.sort(reverse = True)
for i in range(K):
    print(LIS[i])
def main():
    a = input()
    b = input()
    c = input()

    def check(x, y):
        for i in range(len(x)):
            for j in range(len(x)-i):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                cnt = i
                break
        else:
            cnt = len(x)
        ans = x[:cnt]
        x_rest = x[cnt:]
        for i in range(max(len(x_rest), len(y))):
            if i >= len(x_rest):
                ans += y[i]
            elif i >= len(y):
                ans += x_rest[i]
            else:
                if x_rest[i] == "?":
                    ans += y[i]
                else:
                    ans += x_rest[i]
        return ans
    print(min([len(check(check(i, j), k)) for i, j, k in [
          (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]]))


main()


### FIXED CODE ###

def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        lx, ly, lz = len(x), len(y), len(z)
        ans = lx+ly+lz
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            ans = min(ans, max(lx, i+ly)+lz)
            for j in dyz:
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
            for j in range(ly, lx-i):
                if i+j in dxz:
                    ans = min(ans, max(lx, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()
A= input()
B= input()
C= input()
K= input()
u = max(A,B,C)
print(A+B+C+(2**K-1)*u)

### FIXED CODE ###

line = input()
numbers = [int(n) for n in line.split()]
numbers.sort()
K = int(input())
N = numbers[-1]
for _ in range(K):
    N*=2
for num in numbers[:2]:
    N+=num
print(N)
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*(H*W*1)
for i in range(D+1,H*W*1):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])


### FIXED CODE ###

import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*(H*W+1)
for i in range(D+1,H*W+1):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])
count = 1

whie (true) :
    x = input().strip()
    if x == '0' :
        break;
    print('Case %s: %s'%(count,x))
    count += 1;

### FIXED CODE ###

count = 1

while True :
    x = input().strip()
    if x == '0' :
        break
    print('Case %s: %s'%(count,x))
    count = count + 1;
n,m = map(int,input().split())

# 0-indexed
visited = [False]*n
aa = []
bb = []
edge = []
for i in range(7):
    edge.append([False]*7)
"""
edge = [[False]*7]*7
"""

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    aa.append(a)
    bb.append(b)
    edge[a][b] = True
    edge[b][a] = True
    """
    for l in edge:
        print(l)
    print('')
    """

def dfs(vertex):
    visited[vertex] = True
    for i in range(n):
        if edge[vertex][i] and not visited[i]:
            #print(i, end=' ')
            dfs(i)

res = 0
for i in range(m):
    visited = [False]*n
    edge[aa[i]][bb[i]] = False
    edge[bb[i]][aa[i]] = False
    dfs(0)
    if not visited==[True]*n:
        res += 1
    #print(visited)
    edge[aa[i]][bb[i]] = True
    edge[bb[i]][aa[i]] = True

print(res)


### FIXED CODE ###

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

# 0-indexed
visited = [False]*n
aa = []
bb = []
edge = []
for i in range(51):
    edge.append([False]*51)
"""
edge = [[False]*7]*7
"""

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    aa.append(a)
    bb.append(b)
    edge[a][b] = True
    edge[b][a] = True
    """
    for l in edge:
        print(l)
    print('')
    """

def dfs(vertex):
    visited[vertex] = True
    for i in range(n):
        if edge[vertex][i] and not visited[i]:
            #print(i, end=' ')
            dfs(i)

res = 0
for i in range(m):
    visited = [False]*n
    edge[aa[i]][bb[i]] = False
    edge[bb[i]][aa[i]] = False
    dfs(0)
    if not visited==[True]*n:
        res += 1
    #print(visited)
    edge[aa[i]][bb[i]] = True
    edge[bb[i]][aa[i]] = True

print(res)
import numpy as np
W,H,x,y = map(int, input().split())

d_center_W = abs(W/2 - x)
d_center_H = abs(H/2 - y)
d_45_plus =  abs((H/W)*x-1*y)/np.sqrt((H/W)**2+(-1)**2)
d_45_minus = abs((H/W)*x+y-H)/np.sqrt((H/W)**2+1**2)

min_d = min(d_center_W,d_center_H,d_45_plus,d_45_minus)
smflg = False

if [d_center_W,d_center_H,d_45_plus,d_45_minus].count(min_d) > 1:
        smflg = True

ans = 0

if min_d == d_center_W:
        if x <= W/2:
                ans = x*H/1
        else:
                ans = (W-x)*H/1
elif min_d == d_center_H:
        if y <= H/2:
                ans = y*W/1
        else:
                ans = (H-y)*W/1
elif min_d == d_45_plus:
        if x == 0 and y == 0:
                ans = x/y/x
                ans = H*W/2
        elif x == 0:
                ans = (H-(y-(H/W)*x))*(W-(W/H)*y+x)/2
        elif y/x >= H/W:
                ans = (H-(y-(H/W)*x))*(W-(W/H)*y+x)/2
        else:
                ans = (H-(x-(W/H)*y))*(H+y-(W/H)*x)/2
elif min_d == d_45_plus:
        if x <= W/2:
                x += (W/2-x)*2
        else:
                x -= (x-W/2)*2
        if x == 0:
                ans = (H-(y-(H/W)*x))*(W-(W/H)*y+x)/2
        elif y/x >= H/W:
                ans = (H-(y-(H/W)*x))*(W-(W/H)*y+x)/2
        else:
                ans = (H-(x-(W/H)*y))*(H+y-(W/H)*x)/2
if smflg:
        smstr = '1'
else:
        smstr = '0'

if H == 1 and W == 1:
        ans = 1/2

print(str(ans) + ' ' + smstr)


### FIXED CODE ###

W,H,x,y = map(int, input().split())
print(W*H/2)
if x == W/2 and y == H/2:
    print(1)
else:
    print(0)
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if k>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**6) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

k = ni()
a = list(li())

exist = True

# lower
for i, ai in enumerate(a[::-1]):
    if i == 0:
        if ai != 2:
            exist = False
            break
        else:
            upper = 3
            lower = 2
            
    else:
        exist = False
        for yi in range(lower, upper+1):
            if yi % ai == 0:
                lower = yi
                upper = lower+ai-1
                exist = True
                break
            
        if not exist:
            break
                
                
                
ans_lower = lower


# upper
for i, ai in enumerate(a[::-1]):
    if i == 0:
        if ai != 2:
            exist = False
            break
        else:
            upper = 3
            lower = 2
            
    else:
        exist = False
        for yi in range(upper, lower-1, -1):
            if yi % ai == 0:
                lower = yi
                upper = lower+ai-1
                exist = True
                break
            
        if not exist:
            break
                
    
ans_upper = upper

        
print(ans_lower, ans_upper) if exist else print(-1)
        
        

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def judge(k:int, a:list):
    mi = ma = 2
    for ai in a[::-1]:
        # miをaiの倍数に切り上げる
        if mi%ai:
            mi += ai - mi%ai
            
        ma += (ai - 1) - (ma % ai)
        
        if ma < mi:
            return False, (-1,-1)
        
    return True, (mi,ma)

k = ni()
a = list(li())

tf, (mi,ma) = judge(k,a)
if tf:
    print(mi,ma)
else:
    print(-1)
a = map(int, raw_input().split())
  
a.sort()
print '%d %d %d' % (a[1], a[2], a[3])

### FIXED CODE ###

a = map(int, raw_input().split())
  
a.sort()
print '%d %d %d' % (a[0], a[1], a[2])
import sys
import math

for line in sys.stdin.readlines():
     x, y = line.split(" ")

x = int(x)
y = int(y)

divide = 1

if x > y:
    x, y = y, x

for i in range(2, sort(x) + 1):
    if x % i == 0 and y % i == 0:
        divide *= i
        x /= i
        y /= i
        i -= 1

print divide

### FIXED CODE ###

import sys

def div(x, y):
    if x % y == 0:
        print y
    else:
        div(y, x%y)


line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

if x < y:
    x, y = y, x

if x == y:
    print x

else:
    div(x, y)
s = input()
if s in hi:
  print("Yes")
elif:
  print("No")

### FIXED CODE ###

s = input()
if s in ["hi", "hihi", "hihihi", "hihihihi", "hihihihihi"]:
  print("Yes")
else:
  print("No")
n,q=map(int,input().split())
s=list(input())
#print(s)
i=0
a=[]
x=0
while i!=len(s):
 if n>=10000:

    if s[i]=="C" and a1==1:
        x=x+1
        a1=0
    elif s[i]=="A":
        a1=1
    else:
        a1=0
    i=i+1
    a.append(x)

#print(a)
i=0
while i!=q:
  try:
    l,r=map(int,input().split())
    i=i+1
    s=a[r-1]-a[l-1]
    print(s)
  except:
      break

### FIXED CODE ###

n,q=map(int,input().split())
s=list(input())
#print(s)
i=1
a=[0]
x=0
while i!=n:
    if s[i-1]=="A":
        if s[i]=="C":
            x=x+1
    i=i+1
    a.append(x)

#print(a)
i=0
while i!=q:
  try:
    l,r=map(int,input().split())
    i=i+1
    s=a[r-1]-a[l-1]
    print(s)
  except:
      break
n = input()
a = int(n.split()[0])
b = int(n.split()[1])
c = int(n.split()[2])

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


### FIXED CODE ###

n = input()
tmp_n = n.split(" ")

N = tmp_n[0]
M = tmp_n[1]
n_list = []

for i in range(int(M)):
    num = input()
    tmp_num = num.split()
    n_list.append(int(tmp_num[0]))
    n_list.append(int(tmp_num[1]))
    
for j in range(1,int(N)+1):
    count = 0
    for k in n_list:
        if k == j:
            count = count + 1        
    print(count)
a = int(raw_input())
    b = int(raw_input())
    h = int(raw_input())
    print "{}".format(int((a+b)*h/2))


### FIXED CODE ###

a = int(raw_input())
b = int(raw_input())
h = int(raw_input())
print "{}".format(int((a+b)*h/2))
from functools import reduce
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
max = sum(p[0:k])
tmp = max
idx = 0
for i in range(1, len(p) - k + 1):
	tmp -= p[i - 1]
	if i + k - 1 < len(p):
	    tmp += p[i + k - 1]
	if tmp > max:
		max = tmp
		idx = i
lst = p[idx:idx+k]

total_tasu = 0
total_kake = reduce(lambda a, b: a*b, lst)
for i, v in enumerate(lst):
	kake = total_kake / v
	total_tasu += sum([k for k in range(1, v + 1)]) * kake
print(total_tasu/total_kake)


### FIXED CODE ###

from functools import reduce
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
tmp_max = sum([i / 2 + 0.5 for i in p[0:k]])
tmp = tmp_max
idx = 0
for i in range(1, len(p) - k + 1):
	tmp -= p[i - 1] / 2 + 0.5
	if i + k - 1 < len(p):
		tmp += p[i + k - 1] / 2 + 0.5
	tmp_max = max(tmp_max, tmp)
print(tmp_max)
if __name__ == '__main__':
    t = int(input())
    s = []
    for i in range(t):
        s.append(int(input()))
    print(len(set(s)))

### FIXED CODE ###

if __name__ == '__main__':
    t = list(input())

    t[3] = '8'
    print(''.join(t))
X, Y = map(int, input())
print((X+Y)//2)


### FIXED CODE ###

X, Y = map(int, input().split())
print(X+Y//2)
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    a, b = input_to_int_map()
    import itertools
    _a = itertools.repeat(str(a), b)
    _b = itertools.repeat(str(b), a)
    ret = _b
    if _a < _b:
        ret = _a

    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    a, b = input_to_int_map()
    import itertools
    _a = "".join(itertools.repeat(str(a), b))
    _b = "".join(itertools.repeat(str(b), a))
    ret = _b
    if _a < _b:
        ret = _a

    return ret


if __name__ == "__main__":
    print(main())
import sys
input = sys.stdin.readline


def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    ans = 0
    for i in range(1, 10**6+1):
        y = i**N
        if y > P:
            break
        if P % y == 0:
            ans = i
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


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


def main():
    N, P = map(int, input().split())
    p = prime_factorize(P)
    import collections
    ans = 1
    for k, v in collections.Counter(p).most_common():
        while v >= N:
            ans *= k
            v -= N
    print(ans)


if __name__ == '__main__':
    main()
import sympy

sympy.divisors(10**9)

n = int(input())
print(len(list(filter(lambda x: sympy.divisors(x) == 8, range(0, n + 1)))))

### FIXED CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
print(len(list(filter(lambda x: len(make_divisors(x)) == 8, range(1, n + 1,2)))))
K = [None]*30
A = [None]*30
Ms = [0]*30
def main():
    N, M = map(int, input().split())
    for i in range(N):
        K[i], *A[i], = map(int, input().split())
    for i in A:
        if i == None:
            break
        for j in i:
            Ms[j] += 1
    print(Ms.count(N))

main()


### FIXED CODE ###

K = [None]*30
A = [None]*30
Ms = [0]*31
def main():
    N, M = map(int, input().split())
    for i in range(N):
        K[i], *A[i], = map(int, input().split())
    for i in A:
        if i == None:
            break
        for j in i:
            Ms[j] += 1
    print(Ms.count(N))

main()
n = int(input())
a = [int(input()) for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(0, n, -1):
    if sum(b[i::i])%2 == a[i]:
        b[i] = 0
    else:
        b[i] = 1
if sum(b) != 0:
    print(sum(b))
    ans = []
    for i in range(n):
        if b[i] == 1:
            ans.append(i)
    print(ans.join(" "))
else:
    print("0")


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
for i in range(n, 0, -1):
    if sum(b[i-1::i])%2 != a[i-1]:
        b[i-1] = 1

c = [i+1 for i in range(n) if b[i] == 1]
if len(c) != 0:
    print(len(c))
    print(*c)
else:
    print("0")
k = int(input())
a, b = map(int,input().split())

for i in range(a,b+1):
    if i % k == 0:
        print('OK')
        sys.exit()
print('NG')


### FIXED CODE ###

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

def main():
    for i in range(a,b+1):
        if i % k == 0:
            print('OK')
            return
    print('NG')

main()
import math

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

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

num = a[0]
for i in range(1, n):
	num = lcm(num, a[i])

ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007

print(ans)

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))
from math import pi

r = int(input())
print(pi*r**2, 2*pi*r)



### FIXED CODE ###

from math import pi

r = float(input())
print(pi*r**2, 2*pi*r)
import numpy as np

N = int(input())

ans = np.zeros(int(N))

if N<10001 and N>0:
    maxa = int(np.sqrt(N-2))
    for x in range(1,maxa):
        for y in range(1,x):
            for z in range(1,y):
                p = x*x+y*y+z*z+x*y+y*z+z*x
                if p<N+1:
                    ans[p-1] += 6


    for x in range(1,maxa):
        for y in range(1,x):
            p = x*x*3+y*y+x*y*2
            if p<N+1:
                ans[p-1] += 3
            p = y*y*3+x*x+x*y*2
            if p<N+1:
                ans[p-1] += 3

    for x in range(1,maxa):
        p = x*x*6
        if p<N+1:
            ans[p-1] += 1

    for x in range(0,N):
        print(int(ans[x]))

### FIXED CODE ###

import numpy as np

N = int(input())

ans = np.zeros(int(N))

if N<10001 and N>3:
    maxa = int(np.sqrt(N-2))
    for x in range(1,maxa):
        for y in range(1,x):
            for z in range(1,y):
                p = x*x+y*y+z*z+x*y+y*z+z*x
                if p<N+1:
                    ans[p-1] += 6


    for x in range(1,maxa):
        for y in range(1,x):
            p = x*x*3+y*y+x*y*2
            if p<N+1:
                ans[p-1] += 3
            p = y*y*3+x*x+x*y*2
            if p<N+1:
                ans[p-1] += 3

    for x in range(1,maxa):
        p = x*x*6
        if p<N+1:
            ans[p-1] += 1

for x in range(0,N):
    print(int(ans[x]))
import itertools

N = int(input())
x = list()
y = list()

for i in range(N):
    #print(i)
    xy = list(input().split())
    x.append(int(xy[0]))
    y.append(int(xy[1]))

lis = list(itertools.permutations(list(range(1, N + 1))))

ans = 0    
for i in range(N):
    for j in range(N):
        tmp = math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        ans += tmp
 
print(ans/N)

### FIXED CODE ###

import math

N = int(input())
x = []
y = []

for k in range(N):
    #print(i)
    X, Y =  map(int,input().split())
    x.append(X)
    y.append(Y)

ans = 0    
for i in range(N):
    for j in range(N):
        tmp = math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        ans += tmp
 
print(ans/N)
import math
n, m = map(int, input().split())
false_count = [1]*n
ans_false_count = [0]*n
ans_success_count = [0]*n

for i in range(m):
    p, s = input().split()
    p = int(p)
    s = str(s)

    if s=='WA':
        false_count[p-1] = false_count[p-1]*2 
    else:
        ans_false_count[p-1] += false_count[p-1]
        ans_success_count[p-1] = 1
        false_count[p-1] = 0

false_count = [math.log(i,2) for i in false_count] 

new_ans_false_count = false_count + ans_false_count
print(sum(ans_success_count), int(sum(new_ans_false_count)))    

### FIXED CODE ###

import math
n, m = map(int, input().split())
false_count = [1]*n
ans_false_count = [0]*n
ans_success_count = [0]*n

for i in range(m):
    p, s = input().split()
    p = int(p)
    s = str(s)

    if s=='WA':
        false_count[p-1] = int(false_count[p-1]*2)
    else:
        ans_false_count[p-1] += int(false_count[p-1])
        ans_success_count[p-1] = 1
        false_count[p-1] = 0

for j in range(n):
    if ans_false_count [j] != 0:
        ans_false_count[j] = math.log(ans_false_count[j],2)

new_ans_false_count = ans_false_count
print(sum(ans_success_count), int(sum(new_ans_false_count)))
n=int(input())

if n%1000==0:
  print(0)
  
else
  print(1000-n%1000)

### FIXED CODE ###

n=int(input())

if n%1000==0:
  print(0)
  
else:
  print(1000-n%1000)