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

import math
A, B, N = list(map(int, input().split()))
max = -10000
for i in range(1, N+1):
  temp = math.floor(A*i/B)-A*math.floor(i/B)
  if temp >= max:
    max =  temp
    
print(max)
  

### FIXED CODE ###

import math
A, B, N = list(map(int, input().split()))
if B-1 >= N:
  num = N
else:
  num = B-1
  
print(math.floor(A*num/B)-A*math.floor(num/B))
### BUGGY CODE ###

import sys
import itertools

input = sys.stdin.readline


def main():
    n = int(input())
    l = map(int, input().split())
    # 種類組み合わせ・条件
    l = sorted(l)
    hoge = []
    for a, b in itertools.combinations(l, 2):
        target = l[:]
        target.remove(a)
        target.remove(b)
        hoge += [sorted([a, b, c]) for c in filter(lambda x: b - a < x < a + b, target)]
    print(len(set(["{}{}{}".format(a, b, c) for a, b, c in hoge])))
    # sum([str(i) for i in


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline


def main():
    n = int(input())
    l = map(int, input().split())
    # 種類組み合わせ・条件
    l = sorted(l)
    hoge = 0
    for i, a in enumerate(l[:-2], start=1):
        for j, b in enumerate(l[i:-1], start=i):
            index = bisect.bisect_left(l, a + b)
            hoge += index - j - 1
    print(hoge)


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

import math
from functools import reduce
n = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
	while (b):
		a, b = b, a % b
	return a

def gcd_list(numbers):
    return reduce(gcd, numbers)

ans = 0
for i in range(n):
    ans = max(ans, gcd_list(A[0:i] + A[i + 1:]))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
	while (b):
		a, b = b, a % b
	return a


L = [0] + [None] * (n - 1)
R = [0] + [None] * (n - 1)
for i in range(1, n):
	L[i] = gcd(L[i - 1], A[i - 1])
	R[i] = gcd(R[i - 1], A[-i])

M = [None] * n
R = R[::-1]
for i in range(n):
	M[i] = gcd(L[i], R[i])

print(max(M))
### BUGGY CODE ###

import queue

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

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

q = queue.Queue()
q.put(0)
seen = [0] * n
ans = [0] * n

while True:
    if q.empty(): break
    v = q.get()
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        q.put(next_v)
        ans[next_v] += ans[v]

print(*ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from queue import Queue

n, q = map(int, input().split())
nodes = [[] for _ in range(n)]  # 隣接ノード
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

counts = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    counts[p-1] += x

ans = [0] * n
ans[0] = counts[0]
done = [0] * n
queue = Queue()
queue.put(0)
while True:
    node = queue.get()
    done[node] = 1
    next_nodes = nodes[node]
    for next_node in next_nodes:
        if not done[next_node]:
            queue.put(next_node)
            ans[next_node] = ans[node] + counts[next_node]
    if queue.empty():
        break

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

h, w = map(int, input().split())
grid = [['#' for i in range(w+2)]]
for i in range(h):
  grid.append(['#'] + [s for s in str(input())] + ['#'])
grid.append(['#' for i in range(w+2)])
#print(grid)
ans = 0
for i in range(1, h+1):
  for j in range(1, w+1):
    if grid[i][j] == '#': continue
    cnt = 1
    u, d = i-1, i+1
    l, r = j-1, j+1
    while True:
      if grid[u][j] == '#': break
      cnt += 1
      u -= 1
    while True:
      if grid[d][j] == '#': break
      cnt += 1
      d += 1
    while True:
      if grid[i][l] == '#': break
      cnt += 1
      l -= 1
    while True:
      if grid[i][r] == '#': break
      cnt += 1
      r += 1
    ans = max(ans, cnt)
    #print(i, j, cnt)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
grid = [['#' for i in range(w+2)]]
for i in range(h):
  grid.append(['#'] + [s for s in str(input())] + ['#'])
grid.append(['#' for i in range(w+2)])

ud = [[0 for j in range(w+2)] for i in range(h+2)]
lr = [[0 for j in range(w+2)] for i in range(h+2)]

for i in range(1, h+1):
  for j in range(1, w+1):
    if grid[i][j] == '#': continue

    if ud[i-1][j] > 0:
      ud[i][j] = ud[i-1][j]
    else:
      cnt = 0
      d = i
      while grid[d][j] != '#':
        cnt += 1
        d += 1
      ud[i][j] = cnt

    if lr[i][j-1] > 0:
      lr[i][j] = lr[i][j-1]
    else:
      cnt = 0
      r = j
      while grid[i][r] != '#':
        cnt += 1
        r += 1
      lr[i][j] = cnt

ans = 0
for i in range(1, h+1):
  for j in range(1, w+1):
    if grid[i][j] == '#': continue
    cnt = ud[i][j] + lr[i][j] - 1
    ans = max(ans, cnt)
    #print(i, j, cnt)
print(ans)
### BUGGY CODE ###

_ = input()
b = []
for i in input().split():
    b.append(i)
    b.reverse()
else:
    print(" ".join(b))

### FIXED CODE ###

from collections import deque

n = int(input())
a = input().split()
b = deque()

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])
else:
    print(*b)
### BUGGY CODE ###

N=int(input())

for n in range(1,N+1):
    count=0
    for x in range(1,(n+1)//3):
        for y in range(1,(n+1)//3):
            for z in range(1,(n+1)//3):
                if (x+y+z)**2-(x*y+y*z+z*x)==n:
                    count=count+1
    print(count)








### FIXED CODE ###

N=int(input())

a=[0]*10**4

for x in range(1,100):
     for y in range(1,100):
         for z in range(1,100):
             n=(x+y+z)**2-(x*y+y*z+z*x)
             if n<=10000:
                 a[n-1]+=1

for n in range(N):
    print(a[n])
### BUGGY CODE ###

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

while True:
    if not n%k:
        n = 0
        break
    num = n
    n = n-k
    if n < 0:
        n = min(abs(n), num)
        break

print(n)

### FIXED CODE ###

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

a = n%k

num = min(a, abs(a-k))

print(num)
### BUGGY CODE ###

k,s=map(int,input().split())
temp=[x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)].count(s)
print(temp)


### FIXED CODE ###

k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))
### BUGGY CODE ###

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

a=[]
b=[]
l=[]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if a[i]==1 or b[i]==1:
        l.append(a[i]*b[i])


for i in range(m):
    if b[i]==n:
        if a[i] in l:
            print("POSSIBLE")        
            sys.exit()
    if a[i]==n:
        if b[i] in l:
            print("POSSIBLE")
            sys.exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

a=[]
b=[]
l1=[False for i in range(n)]
ln=[False for i in range(n)]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if c[0]==1 or c[1]==1:
        l1[c[0]*c[1]]=True
    if c[0]==n or c[1]==n:
        ln[c[0]*c[1]//n]=True

for i in range(n):
    if l1[i] and ln[i]:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=a[i]^a[j]
        ans%=mod
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
for i in range(60):
    iti=0
    zero=0
    for j in range(n):
        if (a[j]>>i)&1:
            iti+=1
        else:
            zero+=1
    ans+=(2**i)*(iti*zero)
    ans%=mod
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
rr = 0
gg = 0
bb = 0
for i in range(n):
    if s[i] == "R":
        rr += 1
    if s[i] == "G":
        gg += 1
    if s[i] == "B":
        bb += 1

ans = rr * gg * bb

for i in range(n):
    for j in range(n):
        if j - i >= 0 and j + i < n:
            if s[j - i] != s[j] and s[j] != s[j + i] and s[j + i] != s[j - i]:
                ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
rr = 0
gg = 0
bb = 0
for i in range(n):
    if s[i] == "R":
        rr += 1
    if s[i] == "G":
        gg += 1
    if s[i] == "B":
        bb += 1

ans = rr * gg * bb

for j in range(n):
    for i in range(min(j+1, n-j)):
        if s[j - i] != s[j] and s[j] != s[j + i] and s[j + i] != s[j - i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            flag = 0
            for c in s:
                p = flag == 0 and c == str(i)
                q = flag == 1 and c == str(j)
                r = flag == 2 and c == str(k)
                if p or q or r:
                    flag += 1
            if flag == 3:
                ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            flag = 0
            for c in s:
                p = flag == 0 and c == str(i)
                q = flag == 1 and c == str(j)
                r = flag == 2 and c == str(k)
                if p or q or r:
                    flag += 1
            if flag == 3:
                ans += 1
print(ans)
### BUGGY CODE ###

def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  e=defaultdict(list)
  s=[]
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    e[a].append((1,x))
    e[b].append((1,y))
    e[x].append((0,a))
    e[x].append((0,y))
    e[y].append((0,b))
    e[y].append((0,x))
    s.extend([a,b,x,y])
  if not(f and g):
    print(-1)
    exit()
  d={i:v for v,i in enumerate(sorted(set(s)))}
  l=[d[i]for i in l]
  n=len(d)
  edge=[[]for _ in range(n)]
  for i in e:
    edge[d[i]]=[(c,d[j])for c,j in e[i]]
  edge=tuple(edge)
  d=[inf]*n
  used=[True]*n
  d[0]=0
  used[0]=False
  edgelist=[]
  for e in edge[0]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in l)
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count + 100 > N : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

# 任意のj <= iに対して P[i] <= P[j]

N = int(input())
P = [int(e) for e in input().split()]
i_count = 0

for i in range(N):
  if P[i] == min(P[:i+1]):
    i_count += 1

print(i_count)


### FIXED CODE ###

N = int(input())
P = [int(e) for e in input().split()]
i_count = 0
min_P = 200001

for i in range(N):
  if min_P > P[i]:
    min_P = P[i]
    i_count += 1

print(i_count)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= max(d[t]):
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


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


### FIXED CODE ###

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    T = str(input().strip())

    if not set(T) <= set(S):
        return -1

    n = len(S)
    d = defaultdict(list)
    for i, s in enumerate(S, start=1):
        d[s].append(i)

    cnt = 0
    pos = 0
    for t in T:
        if pos >= d[t][-1]:
            cnt += 1
            pos = d[t][0]
        else:
            left = 0
            right = len(d[t])
            while left < right:
                mid = (left + right) // 2
                np = d[t][mid]
                if np <= pos:
                    left = mid + 1
                else:
                    right = mid
            pos = d[t][left]

    return n * cnt + pos


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

import sys
import os
import math


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.buffer.readline().rstrip())
    A = list(map(int, sys.stdin.buffer.readline().split()))
    P = set(A)

    ary = {}
    for n in range(N):
        ary[n] = A[n + 1:] + A[:-len(A) + n]

    for a in ary.values():
        tmp = 0
        for p in P:
            t = a.count(p)
            tmp += (t * (t - 1)) // 2

        print(tmp)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import collections

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.buffer.readline().rstrip())
    A = list(map(int, sys.stdin.buffer.readline().split()))

    obj = collections.Counter(A)

    p = 0
    for v in obj.values():
        if v > 1:
            p += v * (v - 1) // 2

    for a in A:
        print(p - (obj[a] - 1))


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

from collections import Counter

n = int(input())
lst = [input() for _ in range(n)]

counter_lst = []
counter_num = []
for i in range(n):
    a = Counter(lst[i])
    if a in counter_lst:
        m = counter_lst.index(a)
        counter_num[m] += 1
    else:
        counter_lst.append(a)
        counter_num.append(1)
    
res = 0
for i in counter_num:
    if i > 0:
        res += i * (i-1) // 2
print(res)

### FIXED CODE ###

n = int(input())
lst = [input() for _ in range(n)]

dic = dict()
res = 0
for i in range(n):
    sorted_string = "".join(sorted(lst[i]))
    if sorted_string in dic:
        dic[sorted_string] += 1
        res += dic[sorted_string]
    else:
        dic[sorted_string] = 0
    
print(res)
### BUGGY CODE ###

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

A.sort()
CB = list(reversed(sorted(CB)))

ind = 0
for i in range(M):
    (c, b) = CB[i]
    for _ in range(b):
        if ind >= N:
            break
        if A[ind] < c:
            A[ind] = c
            ind += 1
    if ind >= N:
        break

print(sum(A))


### FIXED CODE ###

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

A.sort()
CB = list(reversed(sorted(CB)))

ind = 0
for i in range(M):
    (c, b) = CB[i]
    for _ in range(b):
        if ind >= N:
            break
        if A[ind] < c:
            A[ind] = c
            ind += 1
        else:
            break
    if ind >= N:
        break

print(sum(A))
### BUGGY CODE ###

import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
for i in range(Q):
    p,q = map(int,input().split())
    I = index_dict[p]
    r = sorted(lr_t[1][I:])
    I = bisect.bisect(r,q)
    print(I)

### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])
### BUGGY CODE ###

import collections

n = int(input())
s = [collections.Counter(input()) for _ in range(n)]
cnt = 0
for i in range(n):
    a = s[i]
    for b in s[i+1:]:
        if a == b:
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]
cnt = 0
dic = {}
for s in S:
    s.sort()
    s_ = "".join(s)
    if s_ in dic.keys():
        cnt += dic[s_]
        dic[s_] += 1
    else:
        dic[s_] = 1
print(cnt)
### BUGGY CODE ###

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

dp = [0]*N

for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0,i-K), i))
print(dp[-1])

### FIXED CODE ###

def main2(N,h,K):
    dp = [0] * N
    for i in range(1,N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
    return dp[-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))
print(main2(N,h,K))
### BUGGY CODE ###

a, b, c = map(int, input().split())
cnt = 0
while True:
    if a == b == c and a%2 == 0:
        cnt = -1
    elif a%2 == 0 and b%2 == 0 and c%2 == 0:
        a, b, c, = (b+c)//2, (a+c)//2, (a+b)//2
        cnt += 1
print(cnt)

### FIXED CODE ###

a, b, c = map(int, input().split())
cnt = 0
while True:
    if a == b == c and a%2 == 0:
        cnt = -1
        break
    elif a%2 != 0 or b%2 != 0 or c%2 != 0:
        break
    elif a%2 == 0 and b%2 == 0 and c%2 == 0:
        a, b, c, = (b+c)//2, (a+c)//2, (a+b)//2
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq

def main():
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    h = []
    for v in A:
        heapq.heappush(h, v)

    BC = []
    for _ in range(M):
        BC.append([int(x) for x in input().split()])

    for i in range(M):
        for _ in range(BC[i][0]):
            x = heapq.heappop(h)
            if BC[i][1] > x:
                heapq.heappush(h, BC[i][1])
            else:
                heapq.heappush(h, x)
                break

    print(sum(h))



if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter

def main():
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    h = []
    for v in A:
        heapq.heappush(h, v)

    BC = []
    for _ in range(M):
        BC.append([int(x) for x in input().split()])

    BC_sorted = sorted(BC, key=itemgetter(1), reverse=True)

    is_end = False
    for i in range(M):
        for _ in range(BC_sorted[i][0]):
            x = heapq.heappop(h)
            if BC_sorted[i][1] > x:
                heapq.heappush(h, BC_sorted[i][1])
            else:
                heapq.heappush(h, x)
                is_end = True
                break

        if is_end:
            break

    print(sum(h))



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

import sys
input = sys.stdin.readline

class UnionFind():
  def __init__(self, n):
    self.n = n
    # n+1なのはノード番号とリストのインデックスを一致させるため
    # root[x]<0ならそのノードが根かつその絶対値が木の要素数
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  
  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
    
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1
 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  
n, k, l = map(int, input().split())
UFd= UnionFind(n)
UFt= UnionFind(n)

for i in range(k):
  p, q = map(int, input().split())
  UFd.Unite(p, q)

for j in range(l):
  p, q = map(int, input().split())
  UFt.Unite(p, q)
  
ids = [0]*n
d = {}
for i in range(n):
  if UFd.root[i+1] > 0:
    idd = UFd.root[i+1]
  else:
    idd = i+1
  if UFt.root[i+1] > 0:
    idt = UFt.root[i+1]
  else:
    idt = i+1
  iddt = idd*10**6+idt
  ids[i] = iddt
  if iddt in d:
    d[iddt] += 1
  else:
    d[iddt] = 1
ans = ''
for i in range(n):
  if i != 0:
    ans += ' '
  ans += str(d[ids[i]])
print(ans)    

### FIXED CODE ###

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)