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

import fractions
import functools

def gcd(*numbers):
    return functools.reduce(fractions.gcd, numbers)

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for p in range(1,k+1):
            ans+=gcd(i,j,p)
print(ans)

### FIXED CODE ###

def gcd2(i,j):
    if i<j:
        i,j=j,i
    while j>0:
        i=i%j
        i,j=j,i
    return i

k=int(input())
ans=0
for i in range(1,k+1):
    if i==1:
        ans+=k**2
        continue
    for j in range(1,k+1):
        tmp=gcd2(i,j)
        if tmp==1:
            ans+=k
            continue
        for p in range(1,k+1):
            ans+=gcd2(tmp,p)
print(ans)
### BUGGY CODE ###

s = str(input())
n=len(s)
left :int=1
mlist=[0]
while left<int(n)+1:
  m = int(s[n-left:n])%2019
  mlist.append(m)
  left+=1

sorted_mlist = sorted(mlist)

i :int=0
count :int=0
while i<len(sorted_mlist):
  if sorted_mlist[i-1]==sorted_mlist[i]:
    count+=1
  i+=1

print(count)

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0] + [0 if e == "#" else 1 for e in s[i]] + [0] for i in range(h)]
    m.append([0] * (w + 2))
    m.insert(0, [0] * (w + 2))

    m_t = [[m[i][j] for i in range(h+2)] for j in range(w+2)]

    lr = []
    for i in range(h + 2):
        sm = 0
        row = []
        for j in range(w + 2):
            if m[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        lr.append(row)

    ud = []
    for i in range(w + 2):
        sm = 0
        row = []
        for j in range(h + 2):
            if m_t[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        ud.append(row)

    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            sm = lr[i][j] + ud[j][i] - 1
            ans = max(ans, sm)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0] + [0 if e == "#" else 1 for e in s[i]] + [0] for i in range(h)]
    m.append([0] * (w + 2))
    m.insert(0, [0] * (w + 2))

    m_t = [[m[i][j] for i in range(h+2)] for j in range(w+2)]

    lr = []
    for i in range(h + 2):
        sm = 0
        row = []
        for j in range(w + 2):
            if m[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        lr.append(row)

    ud = []
    for i in range(w + 2):
        sm = 0
        row = []
        for j in range(h + 2):
            if m_t[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        ud.append(row)

    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            sm = lr[i][j] + ud[j][i] - 1
            ans = max(ans, sm)

    print(ans)


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

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i + j + k == S: cnt += 1
print (cnt)


  

### FIXED CODE ###

K, S = map(int, input().split())

L = [1 for z in range(K+1) for y in range(K+1) if 0 <= S-y-z <= K]
print (L.count(1))
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
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 = MI()

A = LI()

multi = {}

start = 1
for k in range(0,K):
    start = start * A[k]

for j in range(K, N+1):
    if j == K:
        multi[j] = start
        continue
    start = start // A[j-K-1] * A[j-1]
    multi[j] = start

    if j-1 in multi:
        if multi[j] > multi[j-1]:
            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 itertools
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 = MI()

A = LI()

for j in range(K, N+1):
    if j == K:
        continue
    if A[j-K-1] < A[j-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

r,g,b,n = I()
a = []
a.append(r)
a.append(g)
a.append(b)
a.sort()
a[0],a[1],a[2] = r,g,b

mx_b = n//b
amari = n%b
for i in range(n//r + 1):
    for j in range(n//g + 1):
        if (r*i+g*j) % b == amari and (r*i+g*j)//b <= mx_b:
            cnt += 1

print(cnt)

### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

r,g,b,n = I()
a = []
a.append(r)
a.append(g)
a.append(b)
a.sort()
a[0],a[1],a[2] = r,g,b

mx_b = n//b
amari = n%b
for i in range(n//r + 1):
    for j in range((n-r*i)//g + 1):
        if (n-r*i-g*j) % b == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
num=0
for i in range(0,n):
    if a[i]+1<n-i:
        for j in range(max(i+1,a[i]+1),n):
            if a[i]+a[j]==j-i:
                num=num+1
print(num)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
tempi=[0]*n
tempj=[0]*n
for i in range(n):
  tempi[i]=a[i]+i+1
for i in range(n):
  tempj[i]=-a[i]+i+1
import collections
tempid=collections.Counter(tempi)
tempjd=collections.Counter(tempj)
for k in tempid.keys():
  a=tempid[k]
  b=tempjd[k]
  ans=ans+a*b
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
MOD = 10**9+7
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
ans = 0
for ai in aa:
  ans += l//ai % MOD

print(ans % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
MOD = 10**9+7
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
ans = 0
for ai in aa:
  ans += l//ai

print(ans % MOD)
### BUGGY CODE ###


N = int(input())
s = list(input())
Q = int(input())

# print()
# s = s * 10000
# print(len(s))

# @elapsed_time
def convert(s: list, q1: int, q2: str):
    # return s[:q1] + q2 + s[q1+1:]
    s[q1] = q2
    return s


# @elapsed_time
def calc(s: list, q1: int, q2: int):
    res = list(set(s[q1:q2+1]))
    # checks = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n','o', 'p', 'q',
    #           'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    # print(res)
    return len(res)


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        s = convert(s, int(q1) - 1, q2)
    if q == 2:
        print(calc(s, int(q1) - 1, int(q2) - 1))


### FIXED CODE ###

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

'''
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7
'''

# from helper import elapsed_time
from bisect import bisect_left, insort_left


N = int(input())
s = list(input())
Q = int(input())

# a-zまでの26文字に対して、s文字列の各文字に該当するindexを格納しておく
d = {i: [] for i in range(26)}
for i, c in enumerate(s):
    d[ord(c) - ord("a")].append(i)


# @elapsed_time
def convert(d: dict, s: list, q1: int, q2: str):
    if s[q1] == q2:
        return d, s

    didx_before = ord(s[q1]) - ord("a")
    didx_after = ord(q2) - ord("a")

    idx = bisect_left(d[didx_before], q1)
    d[didx_before].pop(idx)
    s[q1] = q2
    insort_left(d[didx_after], q1)

    return d, s


# @elapsed_time
def calc(d: dict, q1: int, q2: int):
    ans = 0
    for i in range(26):
        idx = bisect_left(d[i], q1)
        if d[i] and q1 <= d[i][-1] and d[i][idx] < q2 + 1:
            ans += 1

    return ans


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        d, s = convert(d, s, int(q1) - 1, q2)
    if q == 2:
        print(calc(d, int(q1) - 1, int(q2) - 1))
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    da = [[None]*n for _ in range(64)]
    for i in range(n):
        da[0][i] = a[i]-1
    for i in range(1, 64):
        for j in range(n):
            da[i][j] = da[i-1][da[i-1][j]]
    ans = 0
    for i in range(64):
        p = k&1
        if p == 1:
            ans = da[i][ans]
        k//= 2
    print(ans+1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = [True]*n
    cnt = 0
    ans = -1
    x = 0
    while f[x]:
        f[x] = False
        cnt += 1
        x = a[x] - 1
        if cnt == k:
            ans = x+1
            break
    if ans != -1:
        print(ans)
    else:
        k -= cnt
        y = a[x] - 1
        tmp = [x]
        while y != x:
            tmp.append(y)
            y = a[y] - 1
        print(tmp[k%(len(tmp))] + 1)

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

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

H.sort(reverse=True)

if(N<=K):
  print(0)
else:
  for i in range(K):
    H.pop(0)
  print(sum(H))

### FIXED CODE ###

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

H.sort()

if(N<=K):
  print(0)
else:
  for i in range(K):
    H.pop()
  print(sum(H))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i):
        b[i] = 0
        q = [i]
        qi = 0
        while len(q) > qi:
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] == False:
                    b[r] = c+d
                    q.append(r)
                else:
                    if b[r] != c+d:
                        return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i):
            return 'No'
    return 'Yes'


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

import bisect

N = int(input())
A = [int(x) for x in input().split()]
A.sort()
B = [True] * N
for i in range(N):
    if not B[i]: continue
    jr = bisect.bisect_right(A, A[i])
    if jr > i + 1:
        for jj in range(i, jr):
            B[jj] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        jl = bisect.bisect_left(A, a)
        jr = bisect.bisect_right(A, a)
        if A[jl] == a:
            for jj in range(jl, jr):
                B[jj] = False
print(B.count(True))

### FIXED CODE ###

from collections import Counter, defaultdict

N = int(input())
A = [int(x) for x in input().split()]
A.sort()

C = Counter(A)
D = defaultdict(bool)
for key in C.keys():
    D[key] = True

B = [True] * N
ans = 0
for i in range(N):
    if not D[A[i]]: continue
    if C[A[i]] > 1:
        D[A[i]] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        D[a] = False

ans = 0
for key in D:
    if D[key]:
        ans += 1
print(ans)
### BUGGY CODE ###

def countAC(s):
    index = []
    for i in range(N-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                index.append(1)
                continue
        index.append(0)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    s = SIndex[l-1:r-1]
    print(sum(s))
    out = 0


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

N,M = map(int,input().split())
P = list(map(lambda x: int(x)-1,input().split()))
tree = list(range(N))

def root(n):
    while True:
        if tree[n] == n:
            return n
        n = tree[n]

for i in range(M):
    x,y = map(lambda x: int(x)-1,input().split())
    rx = root(x)
    ry = root(y)
    if rx == ry:
        continue
    tree[rx] = ry

print(sum(map(lambda x: root(x)==root(P[x]),range(N))))


### FIXED CODE ###

N,M = map(int,input().split())
P = list(map(lambda x: int(x)-1,input().split()))
tree = list(range(N))

def root(n):
    O = {n}
    while True:
        if tree[n] == n:
            for o in O:
                tree[o] = n
            return n
        n = tree[n]
        O.add(n)

for i in range(M):
    x,y = map(lambda x: int(x)-1,input().split())
    rx = root(x)
    ry = root(y)
    if rx == ry:
        continue
    tree[rx] = ry

print(sum(map(lambda x: root(x)==root(P[x]),range(N))))
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []

for i in range(M):
    x, y, z = map(int, input().split())
    m.append([x, y, z])
m.sort(reverse = True, key=lambda x: x[2])

for j in m[:min(len(a),len(b)+1)]:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[j[0]-1] + b[j[1]-1] - j[2])
        exit()

print(min(a) + min(b))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []
am = min(a)
bm = min(b)

for i in range(M):
    x, y, z = map(int, input().split())

    m.append(a[x-1] + b[y-1] - z )



if am + bm > min(m):
    print(min(m))
else:
    print(am + bm)
### BUGGY CODE ###

# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N, A, B = ILI()
    h = [II() for __ in range(N)]
    return (N, A, B, h)


def solve(N, A, B, h):
    mons = []
    for i in h:
        heapq.heappush(mons, -i)
    dif_ab = A - B
    count = 0
    while True:
        mons_max = -heapq.heappop(mons)
        if mons_max <= count * B:
            ans = count
            break
        else:
            heapq.heappush(mons, -(mons_max - dif_ab))
            count += 1

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N, A, B = ILI()
    h = [II() for __ in range(N)]
    return (N, A, B, h)


def bool_exc(h, dif_ab, B, count):
    dif_count = 0
    for mon in h:
        dif_mon = mon - B * count
        if dif_mon <= 0:
            continue
        else:
            dif_count += math.ceil(dif_mon / dif_ab)
            if dif_count > count:
                break

    dif = count - dif_count
    return dif


def solve(N, A, B, h):
    right = max(h) // B + 1
    left = min(h) // A + 1
    dif_ab = A - B
    while left != right:
        mid = (left + right) // 2
        dif = bool_exc(h, dif_ab, B, mid)
        if dif >= 0:
            right = mid
        else:
            left = mid + 1

    ans = left
    return ans


def main():
    params = read()
    print(solve(*params))


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

import sys
input = sys.stdin.readline
import numpy as np
from bisect import bisect_left, bisect_right
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A = np.array(A)
for i in range(M):
  B,C = map(int,input().split())
  if C <= A[0]:
    continue
  else:
    l = bisect_left(A,C)
    if l>=B:
      A[:l-B] = A[B:l]
      A[l-B:l] = C
    else:
      A[:l] = C
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
from collections import Counter
A = list(map(int,input().split()))
A=Counter(A)
cnt = [(0,0) for _ in range(len(A)+M)]
i = 0
for _ in A.most_common():
  cnt[i]=_
  i+=1
for j in range(M):
  B,C = map(int,input().split())
  cnt[i]=(C, B)
  i+=1
cnt.sort(key=lambda x:x[0],reverse=True)
nn = 0
ans = 0
for k in range(len(cnt)):
  d = min(N-nn,cnt[k][1])
  nn += d
  ans += d * cnt[k][0]
  if nn == N:
    break
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
ans=[]
for i in range(n):
  x=set(uf1.members(i))&set(uf2.members(i))
  ans.append(len(x))
print(*ans)

### FIXED CODE ###

from collections import defaultdict
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
d=defaultdict(int)
for i in range(n):
  d[(uf1.find(i),uf2.find(i))]+=1
ans=[d[(uf1.find(i),uf2.find(i))] for i in range(n)]
print(*ans)