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

X = int(input())
i = 0
while True:
  tmp1 = pow(X + pow(i, 5), 1/5)
  if tmp1.is_integer():
    print(int(tmp1), i)
    break
  tmp2 = pow(X - pow(i, 5), 1/5)
  if tmp2 != complex:
    if tmp2.is_integer():
      print(int(tmp2), -i)
      break
  else:
    i += 1

### FIXED CODE ###

X = int(input())
pin = 0
for i in range(-120, 120):
    if pin == 1:
        break
    for j in range(-120, 120):
        if pow(i, 5) - pow(j, 5) == X :
            pin =1
            print(i, j)
            break
### BUGGY CODE ###

def main(S=None):
    if not S:
        S = input()
    r = {k: 0 for k in range(0, 2019)}
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for k, v in r.items():
        # if v > 1:
        #     print(k, v)
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()


### FIXED CODE ###

def main(S=None):
    if not S:
        S = input()
    r = [0]*2019
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        base %= 2019
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for v in r:
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()
### BUGGY CODE ###

import numpy as np
def f():
  N,M=map(int,input().split())
  A=np.array(list(map(int,input().split())))
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  sa=(np.sort(np.array(l))[-M:]).sum()
  print(A.sum()-sa)
f()

### FIXED CODE ###

def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()
### BUGGY CODE ###

n=int(input())
ls=list(map(int,input().split()))
count_ls=[0]*n
answers=[]
m=0

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)
    divisors.remove(n)
    return divisors

for i in range(n,0,-1):
    plus_flag=False
    idx=i-1
    if count_ls[idx]%2!=ls[idx]:
        plus_flag=True
        m+=1
        answers.append(i)
    if plus_flag:
        divisors=make_divisors(i)
        for j in divisors:
            j_idx=j-1
            count_ls[j_idx]+=1

print(m)
if m:
    print(" ".join(list(map(str,answers))))

### FIXED CODE ###

n=int(input())
ls=list(map(int,input().split()))
count_ls=[0]*n
answers=[]
m=0

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)
    divisors.remove(n)
    return divisors

for i in range(n,0,-1):
    plus_flag=False
    idx=i-1
    if count_ls[idx]%2!=ls[idx]:
        plus_flag=True
        m+=1
        answers.append(i)
    if plus_flag:
        divisors=set(make_divisors(i))
        for j in divisors:
            j_idx=j-1
            count_ls[j_idx]+=1

print(m)
if m:
    print(" ".join(list(map(str,answers))))
### BUGGY CODE ###

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

exp = []
sum_list = [0]
result_list = []
for i in range(N):
    exp.append((p[i]+1)/2)
    sum_list.append(sum(exp))  
for i in range(N-K+1):
    result_list.append(sum_list[K+i] - sum_list[i])
print(max(result_list))


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
exp = []
sum_list = []
result_list = []
result = 0
count = 0
tmp = 0
for i in range(N):
    if count < K-1:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
    else:
        a = (p[i]+1)/2
        exp.append(a)
        tmp += a
        sum_list.append(tmp)
        tmp -= exp[count-K+1]
    count += 1

print(max(sum_list))
### BUGGY CODE ###

n = int(input())


s = [sorted(input()) for i in range(n)]

res = 0
for i in range(n):
    for j in range(i + 1, n):
       res += s[i] == s[j]

print(res)


### FIXED CODE ###

n = int(input())

res = 0
d = dict()
for i in range(n):
    s = ''.join(sorted(input()))
    if s in d.keys():
        res += d[s]
        d[s] += 1
    else:
        d[s] = 1

print(res)
### BUGGY CODE ###

from collections import defaultdict as dd
road = dd(list)
train = dd(list)
ans = []
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
n,k,l = map(int, input().split())
for _ in range(k):
    a,b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
for _ in range(l):
    a,b = map(int, input().split())
    train[a].append(b)
    train[b].append(a)
for i in range(1,n+1):
    ans.append(str(len(gr(road,i)&gr(train,i))))
print(" ".join(ans))

### FIXED CODE ###

from collections import defaultdict as dd
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True
n,k,l = map(int, input().split())
ufr = [-1]*(n+1)
uft = [-1]*(n+1)
for _ in range(k):
    a,b = map(int, input().split())
    unite(ufr,a,b)
for _ in range(l):
    a,b = map(int, input().split())
    unite(uft,a,b)
tot = dd(int)
for i in range(1,n+1):
  tot[(find(ufr,i),find(uft,i))] += 1
print(" ".join([str(tot[(find(ufr,i),find(uft,i))]) for i in range(1,n+1)]))
### BUGGY CODE ###

N = int(input())
S = input()
M = 3 * 10 ** 5
#print(M)
for i in range(N-1):
    A = S[:i]
    B = S[i+1:]
#    print(A,B,A.count("W")+B.count("E"))
    M = min(M, A.count("W")+B.count("E"))
print(M)


### FIXED CODE ###

N = int(input())
S = input()
a = S.count("E")
c = 0
A = N
for i in range(N):
    a += c
    c = 0
    if S[i] == "E":
        a -= 1
    else:
        c = 1
    A = min(A, a)
print(A)
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n,k,q = MI()

A = [k]*n
for i in range(q):
    c = I()
    A = list(map(lambda x: x-1, A))
    A[c-1] += 1

for a in A:
    if a > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n,k,q = MI()

A = [0]*n
for i in range(q):
    c = I()
    A[c-1] += 1

for a in A:
    if q < k + a:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,k = list(map(int,input().split()))
a =[]
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort()
b =[]
for i in range(n):
    for j in range(a[i][1]):
        b.append(a[i][0])
print(b[k-1])

### FIXED CODE ###

n,k = list(map(int,input().split()))
a =[]
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort()
b =[]
c =[]
for i in range(n):
    b.append(a[i][0])
    c.append(a[i][1])
for i in range(n-1):
    c[i+1] = c[i]+c[i+1]
ans = c[-1]
for i in range(1,n):
    if c[i] >= k:
        ans = b[i]
        break

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

N, M = (int(i) for i in input().split(' '))
ten = [i+1 for i in range(N)]
H = [int(i) for i in input().split(' ')]
dic = {}
for i in range(len(H)):
    list_item = H[i]
    dic[i+1] = list_item
A = []
for i in range(M):
    x, y = (int(a) for a in input().split(' '))
    if x in ten and y in ten:
        if dic[x] == dic[y]:
            A.append(x)
            A.append(y)
    if y in ten:
        if dic[x] > dic[y]:
            A.append(y)
    if x in ten:
        if dic[y] > dic[x]:
            A.append(x)
    
B = set(A)
for i in B:
    ten.remove(i)
print(len(ten))

### FIXED CODE ###

n,m=map(int,input().split())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=0
for v in range(1,n+1):
  for u in g[v]:
    if arr[u]>=arr[v]:
      break
  else:
    ans+=1
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
c = []
h = []
for i in range(b):
    d, e = map(int, input().split())
    c.append([e, d, 0])
    h.append([e, d, 0])
h.sort()
for i in range(a):
    g = 1
    for j in range(b):
        if h[j][1] == i + 1:
            h[j][2] = g
            g += 1
for i in range(b):
    for j in range(b):
        if c[i][0] == h[j][0] and c[i][1] == h[j][1]:
            print(("000000" + str(h[j][1]))[-6:] + ("000000" + str(h[j][2]))[-6:])
            break


### FIXED CODE ###

a, b = map(int, input().split())
c = []
for i in range(b):
    d, e = map(int, input().split())
    c.append([i, d, e, 0])
c = sorted(c, key=lambda x: x[2], reverse=False)
d = [0] * a
for i in range(b):
    d[c[i][1]-1] += 1
    c[i][3] = d[c[i][1]-1]
c.sort()
for i in range(b):
    print(("000000" + str(c[i][1]))[-6:] + ("000000" + str(c[i][3]))[-6:])
### BUGGY CODE ###

n= int(input())
s = input()
ans = 0
li_r = []
li_g = []
li_b = []
for i in range(n):
  if s[i] == "R":
    li_r.append(i+1)
  elif s[i] == "G":
    li_g.append(i+1)
  elif s[i] == "B":
    li_b.append(i+1)
for i in li_r:
  for j in li_g:
    for k in li_b:
      li = [i,j,k]
      li.sort()
      a = li[0]
      b = li[1]
      c = li[2]
      if b-a != c-b:
        ans += 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = I()
s = input()
c = Counter(s)
ans = 0
for i in range(n):
    for k in range(i+1,n):
        if (i+k)%2 == 0:
            j = (i+k)//2
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans+=1
ans_2 = c["R"]*c["G"]*c["B"]
print(ans_2-ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l == 0:
            print(0)
            exit()
        continue
    else:
        if l == 0:
            print(0)
            exit()
        #print(l,'l')
        ans *= l
        #print(ans)
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()

ans = li[0]
for i,l in enumerate(li):
    if i == 0:
        continue
    else:
        #print(l,'l')
        ans *= l
        if ans > 10**18:
            print(-1)
            exit()
        #print(ans)
if ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import bisect
import collections
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]

q = collections.deque()

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 0
for i in range(H):
    for j in range(W):
        M = max(C[i][j], M)

dp = [[set() for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j].add(C[i][j])
            else:
                for x in dp[i][j-1]:
                    dp[i][j].add(abs(x-C[i][j]))
                    dp[i][j].add(x+C[i][j])

        else:
            if j != 0:
                for x in dp[i][j-1]:
                    dp[i][j].add(abs(x-C[i][j]))
                    dp[i][j].add(x+C[i][j])

            for x in dp[i-1][j]:
                dp[i][j].add(abs(x-C[i][j]))
                dp[i][j].add(x+C[i][j])

print(min(dp[H-1][W-1]))


### FIXED CODE ###


H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = (H+W)*80

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j] = (1 << M) << C[i][j]
            else:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

        else:
            if j != 0:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

            dp[i][j] |= dp[i-1][j] >> C[i][j]
            dp[i][j] |= dp[i-1][j] << C[i][j]

dp = bin(dp[i][j])[2:]
dp = dp[::-1]
ans = M
for i, x in enumerate(dp):
    if x == "1":
        ans = min(ans, abs(i - M))

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

import itertools as it
n = int(input())
s = input()
s_dic = {}
for c in s:
    if not c in s_dic.keys():s_dic[c] = 1
    else:s_dic[c] += 1
#print(s_dic)
ndic = {}
for i in range(1,len(s_dic)+1):
    a = it.combinations(s_dic.keys(), i)
    for t in a:
        key = ''.join((t))
        #print(key)
        if len(key) == 1:
            #print('one word key')
            ndic[key] = s_dic[key]
        else:
            #print('keys:)',key[:-1],key[-1])
            #print('value:',ndic[key[:-1]],ndic[key[-1]])
            ndic[key] = (ndic[key[:-1]] * ndic[key[-1]]) % (10**9+7)
#print(ndic)
print(sum(ndic.values()) % (10**9+7))

### FIXED CODE ###

def mul(a,b,p):
    return ((a % p) * (b % p)) % p

def div(a,b,p):
    return mul(a, power_func(b, p-2,p),p)

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

modp = 1000000007
_ = input()
s = input()
d = dict()
for c in s:d[c] = d.get(c,0)+1

g = power_func(2,len(d),modp)
g = (g+modp-1) % modp

for c in sorted(d.keys()):
    subsubg = div((g+1)%modp,2,modp)
    subg = (subsubg % modp) * ((d[c]-1)%modp) % modp
    g = (g + subg) % modp
print(g)
### BUGGY CODE ###

N,M=map( int, input().split())
A=list( map( int, input().split()))
for i in range(M):
    A[A.index(max(A))] = int(A[A.index(max(A))]/2)
print(sum(A))

### FIXED CODE ###

import heapq
def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    A = list(map(lambda x: x*(-1), A))
    heapq.heapify(A)
    for _ in range(M):
        u = heapq.heappop(A)
        heapq.heappush(A,int(u/2))
    print(-sum(A))


    

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def solve():
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                if len(us[i])>len(us[fr]):
                    us[i].extend(us[fr])
                    for aa in us[fr]:
                        us[aa] = us[i]
                else:
                    us[fr].extend(us[i])
                    for aa in us[i]:
                        us[aa] = us[fr]
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if blo in us[i]:
                frens -= 1
        print(frens, end=" ")
    print()
    return


n, m, k = [int(s) for s in input().split(" ")]

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]

for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)
solve()


### FIXED CODE ###


def solve():
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                if len(us[i])>len(us[fr]):
                    us[i].extend(us[fr])
                    for aa in us[fr]:
                        us[aa] = us[i]
                else:
                    us[fr].extend(us[i])
                    for aa in us[i]:
                        us[aa] = us[fr]
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if us[i] is us[blo]:
                frens -= 1
        print(frens, end=" ")
    print()
    return



n, m, k = [int(s) for s in input().split(" ")]

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]
for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)


solve()
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
T = lr()
A = lr()
MOD = 10 ** 9 + 7

T_spe = [T[0]] + [0] * (N-1)
A_spe = [0] * (N-1) + [A[-1]]

for i in range(1, N):
    if T[i] > T[i-1]:
        T_spe[i] = T[i]

for i in range(N-2, -1, -1):
    if A[i] > A[i+1]:
        A_spe[i] = A[i]

for i in range(N):
    if T_spe[i] > A[i] or A_spe[i] > T[i]:
        print(0)
        exit()

answer = 1
for i in range(N):
    if T_spe[i] == 0 and A_spe[i] == 0:
        answer *= min(T[i], A[i]) % MOD

print(answer%MOD)
# 34


### FIXED CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
T = np.array(lr()).astype('int64')
A = np.array(lr()).astype('int64')
MOD = 10 ** 9 + 7

T_low = T.copy()
T_low[1:][T[1:] <= T[:-1]] = 1
A_low = A.copy()
A_low[:-1][A[:-1] <= A[1:]] = 1

lower = np.maximum(T_low, A_low)
upper = np.minimum(T, A)
domain = np.maximum(0, upper - lower + 1) #変域が0の時は記録が間違い
L = len(domain); LSQ = int(L**.5 + 1)
domain = np.resize(domain, LSQ**2) #行列の形に無理やりする下準備（1次元）
domain[L:] = 1 #後半は全部1
domain = domain.reshape((LSQ, LSQ))
for n in range(1, LSQ):
    domain[:, n] *= domain[:, n-1]; domain[:, n] %= MOD
for n in range(1, LSQ):
    domain[n] *= domain[n-1, -1]; domain[n] %= MOD
answer = domain[-1, -1]
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

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

for i in range(1,N+1):
    Grin1[Group1[find1(i)]].append(i)
    Grin2[Group2[find2(i)]].append(i)

for i in range(1,N+1):
    Grin1[i]=set(Grin1[i])
    Grin2[i]=set(Grin2[i])

for i in range(1,N+1):
    print(len(Grin1[find1(i)] & Grin2[find2(i)]),end=" ")


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

from collections import defaultdict
ANS = defaultdict(int)

for i in range(1,N+1):
    ANS[(find1(i),find2(i))]+=1

for i in range(1,N+1):
    print(ANS[(find1(i),find2(i))])
### BUGGY CODE ###

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

ans_list = [[1, 0] for i in range(1000001)]
for i in range(N):
    now = A[i]
    ans_list[now][1] += 1
    for j in range(2*now, 1000001, now):
        ans_list[j][0] = 0

count = 0
for i in range(N):
    now = A[i]
    if ans_list[now][0] == 1 and ans_list[now][1] == 1:
        count += 1
        
print(count)

### FIXED CODE ###

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

num = [1 for i in range(1000001)]
ans_list = [0 for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now] == 2:
        continue
    elif ans_list[now] == 1:
        ans_list[now] = 2
    else:
        ans_list[now] = 1
    for j in range(2*now, 1000001, now):
        num[j] = 0

count = 0
for i in range(N):
    now = A[i]
    if num[now] == 1 and ans_list[now] == 1:
        count += 1
        
print(count)
### BUGGY CODE ###

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

def g(n, k, h):
    gk = [0] * n
    g = gk[1] = abs(h[1] - h[0])
    for i in range(2, n):
        g = min(abs(h[i] - h[i-j]) + gk[i-j] for j in range(1, min(i, k)+1))
        gk[i] = g
    return g

print(g(N, K, h))


### FIXED CODE ###

from collections import deque
N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
def g(n, k, h):
    gk = deque([abs(h[1] - h[0]), 0])
    g = gk[0]
    for i in range(2, n):
        g = min(abs(h[i] - h[i-j]) + gk[j-1] for j in range(1, min(i, k)+1))
        if i >= k:
            gk.pop()
        gk.appendleft(g)
    return g

print(g(N, K, h))
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(N-1):
  ans+=i+1
print(ans)

### FIXED CODE ###

N = int(input())


print(N*(N + 1) // 2 - N)