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

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

def gcd(a,b):
    if(b==0):
        return a
    
    r = a%b
    while(r!=0):
        a = b
        b = r
        r = a%b
    
    return b
    

def lcm(a,b):
    return a * b / gcd(a, b)

l = 1
for i in range(len(a)):
    if(l>a[i]):
        l = lcm(l,a[i])
    else:
        l = lcm(a[i],l)

count = 0
for i in range(len(a)):
    count += int(l/a[i])
    count = count % (1000000007)
print(count)

### FIXED CODE ###

from fractions import gcd
 
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))
 
cnt = 0
for i in a:
    cnt += l // i
print(cnt % mod)
### BUGGY CODE ###

def main():
    n, k = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    
    def solve():
        nonlocal A
        for _ in range(k):
            b=[0]*(n+1)
            
            for i in range(n):
                b[max(0,i-A[i])]+=1
                b[min(n,i+A[i]+1)]-=1
            
            # update ans
            # cnt=0
            for i in range(1,n):
                b[i]+=b[i-1]
            A=b
            if min(A)==n:
                break
        print(*A[:-1])
    solve()

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

import bisect
n = int(input())
p = list(map(int, input().split()))

index = [0] * (n+1)

for i in range(n):
    index[p[i]] = i

poss = []
result = 0
for i in range(1, n+1)[::-1]:
    x = index[i]
    if len(poss) == 0:
        poss.append(x)
        continue
    dx = bisect.bisect_left(poss, x)
    # 左に１番目の数がある
    if dx > 0:
        lbl = 0
        if dx > 1:
            lbl = poss[dx-2]+1
        lbr = poss[dx-1]
        rbl = n-1
        if len(poss) != dx:
            rbl = poss[dx] -1
        result += (lbr-lbl+1) * (rbl-x+1) * i
    # 右に1番目の数がある
    if dx < len(poss):
        rbr = n-1
        if dx < len(poss) -1:
            rbr = poss[dx+1]-1
        rbl = poss[dx]
        lbr = 0
        if dx > 0:
            lbr = poss[dx-1] +1
        result += (rbr-rbl+1) * (x-lbr+1) * i
    poss.insert(dx, x)

print(result)

### FIXED CODE ###

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

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

index = [0] * (n+1)

for i in range(n):
    index[p[i]] = i+1

used = BIT(n)
result = 0
for i in range(1, n+1)[::-1]:
    x = index[i]
    if used.len() == 0:
        used.add(x, 1)
        continue
    dx = used.sum(x)
    # 左に１番目の数がある
    if dx > 0:
        lbl = 1
        if dx > 1:
            lbl = used.search(dx-1)+1
        lbr = used.search(dx)
        rbl = n
        if used.len() != dx:
            rbl = used.search(dx+1) -1
        result += (lbr-lbl+1) * (rbl-x+1) * i
    # 右に1番目の数がある
    if dx < used.len():
        rbr = n
        if dx < used.len() -1:
            rbr = used.search(dx+2)-1
        rbl = used.search(dx+1)
        lbr = 1
        if dx > 0:
            lbr = used.search(dx) +1
        result += (rbr-rbl+1) * (x-lbr+1) * i
    used.add(x, 1)
 
print(result)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
arr = list(map(int, input().split(" ")))
new_arr = set(arr)
# print(arr)
# print(new_arr)

ans_date = []
for i in new_arr:
  date = []
  num_count = arr.count(i)
  num = i
  date.append(num_count)
  date.append(num)
  ans_date.append(date)
# print(ans_date)
ans_date.sort()
# print(ans_date)

t = len(ans_date)
x = t - k

ans = 0
for l in range(x):
  ans += ans_date[l][0]
print(ans)

### FIXED CODE ###

from collections import Counter

n, k = map(int, input().split(" "))
As = list(map(int, input().split(" ")))

c = Counter(As)
# print(c)
common = c.most_common(k)
# print(common)

common_sum = sum([item[1] for item in common])
print(n - common_sum)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
for i in range(n+1):
    for j in range(n+1):
        all_sum = n
        all_sum  -= i*r
        all_sum  -= j*g
        if all_sum < 0:
            continue
        if all_sum %b == 0 and i+j+(all_sum//b) != 0:
            count += 1
            #print(i,j,all_sum,b)
print(count) 

### FIXED CODE ###

r,g,b,n = map(int,input().split())
count = 0
for i in range(n+1):
    for j in range(n+1):
        all_sum = n
        all_sum  -= i*r
        all_sum  -= j*g
        if all_sum < 0:
            continue
        if all_sum %b == 0 and i+j+(all_sum//b) != 0:
            count += 1
            #print(i,j,all_sum,b)
print(count)
### BUGGY CODE ###

import copy
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(K):
    # j番目の電球を操作
    B = [0] * N
    for j in range(N):
        maxA = int(j + A[j] + 0.5)
        minA = math.ceil(j - A[j] - 0.5)

        for k in range(max(0, minA), min(N, maxA + 1)):
            B[k] += 1
    A = copy.copy(B)

for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

import numpy as np

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

ans = 0
A = np.array(A)[::-1]
B = np.array(B)[::-1]

for i in range(n):
    if A[i] % B[i] == 0:
        pass
    else:
        temp = B[i]*((A[i]//B[i])+1) - A[i]
        ans += temp
        A += temp
print(ans)

### FIXED CODE ###

n = int(input())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0
for i in range(n-1, -1, -1):
    if (A[i]+ans) % B[i] == 0:
        continue
    else:
        ans += B[i] - (A[i]+ans) % B[i]
print(ans)
### BUGGY CODE ###

h, w, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
quest = [tuple(map(int, input().split())) for _ in range(q)]
enumboard = []
for i in range(h):
    for j in range(w):
        enumboard.append((board[i][j], i, j))
enumboard.sort(key = lambda x: x[0])
for l, r in quest:
    ret = 0
    for x in range(l, r, d):
        ret += abs(enumboard[x+d-1][1] - enumboard[x-1][1]) + abs(enumboard[x+d-1][2] - enumboard[x-1][2])
    print(ret)

### FIXED CODE ###

h, w, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
quest = [tuple(map(int, input().split())) for _ in range(q)]
enumboard = []
for i in range(h):
    for j in range(w):
        enumboard.append((board[i][j], i, j))
enumboard.sort(key = lambda x: x[0])
cumboard = [0 for _ in range(h*w)]
for i in range(d, h*w):
    cumboard[i] = cumboard[i-d] + abs(enumboard[i][1] - enumboard[i-d][1]) + abs(enumboard[i][2] - enumboard[i-d][2])
for l, r in quest:
    print(cumboard[r-1] - cumboard[l-1])
### BUGGY CODE ###

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

### FIXED CODE ###

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

n,c1 = map(int, input().split())
g = []
c = [0]
d = [0]
a = 0
ans=[]
for i in range(n):
  x,v = map(int, input().split())
  g.append([x,v])
  a+=v
  c.append(a-x)
  d.append(a-2*x)
b = 0
e = [0]
f = [0]
for i,j in reversed(g):
  b+=j
  e.append(b-(c1-i))
  f.append(b-2*(c1-i))
for i in range(1,n+2):
  ans.append(max(c[:i])+f[-i])
  ans.append(max(d[:i])+e[-i])
print(max(ans))

### FIXED CODE ###

n,c1 = map(int, input().split())
g = []
c = [0]
d = [0]
a = 0
ans=[]
m1=0
m2=0
for i in range(n):
  x,v = map(int, input().split())
  g.append([x,v])
  a+=v
  m1= max(a-x,m1)
  m2= max(a-2*x,m2)
  c.append(m1)
  d.append(m2)
b = 0
e = [0]
f = [0]
for i,j in reversed(g):
  b+=j
  e.append(b-(c1-i))
  f.append(b-2*(c1-i))
for i in range(n+1):
  ans.append(c[i]+f[-i-1])
  ans.append(d[i]+e[-i-1])
print(max(ans))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
for i in range(n):
    score = 0
    copy = l[:]
    del copy[i]
    for j in range(1,n+1):
        k = copy.count(j)
        score += int(k*(k-1)/2)
    print(score)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
a = []
b = 0
for m in range(n):
    a.append(0)
for m in range(n):
    a[l[m]-1] += 1
for m in range(n):
    b += int(a[m]*(a[m]-1)/2)
for m in range(n):
    print(b-a[l[m]-1]+1)
### BUGGY CODE ###

s=input()
q=int(input())
hanten=0

for i in range(q):
    s1=input()
    if len(s1)==1:
        hanten+=1
    else:
        a,f,c=s1.split()
        f=int(f)
        if (f+hanten)%2==0:
            s = s + c
        else:
            s = c + s     

if hanten%2==0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s=input()
q=int(input())
hanten=0
s_1 = ""
s_2 = ""

for i in range(q):
    s1=input()
    if len(s1)==1:
        hanten+=1
    else:
        a,f,c=s1.split()
        f=int(f)
        if (f+hanten)%2==0:
            s_2 += c
        else:
            s_1 = c + s_1     

if hanten%2==0:
    print(s_1 + s + s_2)
else:
    s_3 = s_1 + s + s_2
    print(s_3[::-1])
### BUGGY CODE ###

import sys, copy
from collections import deque

input = sys.stdin.readline

n = int(input())
a = [deque(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0


def check(p, q):
    if not len(a[p]) == 0:
        o = a[p][0]
        if a[o][0] == p:
            if p < o and not (p, o) in q:
                q.append((p, o))
            elif not (o, p) in q:
                q.append((o, p))

for p in range(n):
    check(p, q)

while len(q) > 0:
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)


for i in range(n):
    if not len(a[i]) == 0:
        print(-1)
        sys.exit()

print(day)


### FIXED CODE ###

from collections import deque
import copy, sys

input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)
### BUGGY CODE ###

from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1, N):
        hash_table[i][j] = hash_table[j][i] = count
        count += 1


graph = [[] for i in range(m)]
is_root = [True] * m
for i in range(1, N+1):
    A = deque(list(map(int, input().split())))
    pre_a = A.popleft()
    pre_pair = hash_table[i-1][pre_a-1]
    for a in A:
        pair = hash_table[i-1][a-1]
        graph[pre_pair].append(pair)
        is_root[pair] = False
        pre_pair = pair


stack = []
is_in_stack = [False] * m
for i in range(m):
    if is_root[i]:
        stack.append(i)
        is_in_stack[i] = True


if not stack:
    ans = -1
else:
  ans = 1
  depth = [1] * m
  while stack:
      pair = stack[-1]
      subseq = graph[pair]
      have_next = False
      for ss in subseq:
          if is_in_stack[ss]:
              ans = -1
              stack = []
              have_next = True
              break

          if have_next or depth[ss] > depth[pair]:
              continue

          have_next = True
          depth[ss] = depth[pair] + 1
          ans = max(ans, depth[ss])
          stack.append(ss)
          is_in_stack[ss] = True

      if not have_next:
          pair = stack.pop()
          is_in_stack[pair] = False

print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
m = N*(N-1) // 2

hash_table = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(i+1, N):
    hash_table[i][j] = hash_table[j][i] = count
    count += 1


graph = [[] for i in range(m)]
before_this = [0] * m
for i in range(1, N+1):
  A = deque(list(map(int, input().split())))
  pre_a = A.popleft()
  pre_pair = hash_table[i-1][pre_a-1]
  for a in A:
    pair = hash_table[i-1][a-1]
    graph[pre_pair].append(pair)
    before_this[pair] += 1
    pre_pair = pair


games = deque([])
for i in range(m):
  if not before_this[i]:
    games.append(i)


if not games:
  ans = -1
else:
  ans = 0
  num_finished = 0
  while games:
    ans += 1
    num_games = len(games)
    num_finished += num_games
    for i in range(num_games):
      pair = games.popleft()
      subseq = graph[pair]
      for ss in subseq:
        before_this[ss] -= 1
        if not before_this[ss]:
          games.append(ss)
    
  if num_finished != m:
    ans = -1

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for _ in range(n)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	b = [0 for _ in range(n)]
	alln = 0
	for i in range(n):
		if a[i] == n:
			alln += 1
		for j in range(max(i-a[i], 0), min(i+a[i]+1, n)):
			b[j] += 1
	if alln == n:
		break
	a = b[:]
print(*b)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0 for _ in range(n+1)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	imos = [0 for _ in range(n+1)]
	for i in range(n):
		imos[max(i-a[i], 0)] += 1
		imos[min(i+a[i]+1, n)] -= 1
	cnt = 0
	alln = 0
	for i in range(n):
		cnt += imos[i]
		a[i] = cnt
		if a[i] == n:
			alln += 1
	if alln == n:
		break
print(*a)
### BUGGY CODE ###

import math

def cf(x1,x2):
    cf=[]
    cf = [i for i in range(1,min(x1,x2)+1) if x1 % i == 0 and x2 % i == 0]
    return cf

def is_prime(n):
    if n == 1: return True
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

A, B = map(int, input().split())
lst = cf(A,B)

res = len([i for i in lst if is_prime(i)])

print(res)

### FIXED CODE ###

import math

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

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

A, B = map(int, input().split())
AY = make_divisors(A)
BY = make_divisors(B)
AB = set(AY) & set(BY)
AB = list(AB)
cnt = [i for i in range(len(AB)) if is_prime(AB[i])]
print(len(cnt))
### BUGGY CODE ###

X ,Y = map(int, input().split())
n = 2 * Y - X
m = 2 * X - Y
r = 1
if n % 3 != 0:
    r = 0
elif m % 3 != 0:
    r = 0
elif m < 0:
    r = 0
elif n < 0:
    r = 0
else:
    nn = min(n,m) // 3
    mm = max(n,m) // 3
    for i in range(nn):
        r = r * (mm + i + 1) // (i+1)
print(r % (10**9+7))

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6     #出力の制限
mod = 10**9+7 
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

X ,Y = map(int, input().split())
n = 2 * Y - X
m = 2 * X - Y
r = 1
if n % 3 != 0:
    r = 0
elif m % 3 != 0:
    r = 0
else:
    r = cmb(n//3+m//3,n//3,mod)
print(r)
### BUGGY CODE ###

N = int(input())
A = [0] + list(map(int, input().split()))
A.sort()
S = sum(A)
count = 0
is_ok = [0] + [1] * N
for i in range(1, N+1):
    if is_ok[i] == 0:
        continue
    for j in range(1, i):
        if A[i] % A[j] == 0:
            is_ok[i] = 0
            if A[i] == A[j]:
                is_ok[j] = 0

print(sum(is_ok))

### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split()))
A.sort()
A_max = A[-1]
dp = [1] * (1 + A_max)
from bisect import bisect_left, bisect_right

for x in A[1:]:
    if dp[x] == 0:
        continue
    y = x * 2
    while y <= A_max:
        dp[y] = 0
        y += x
ans = []
for i in range(1, A_max+1):
    if dp[i] == 1:
        idx_l = bisect_left(A, i)
        idx_r = bisect_right(A, i)
        if idx_r - idx_l > 1:
            continue
        if A[idx_l] == i:
            ans.append(idx_l)
print(len(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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 union(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)

n,k,l = map(int,input().split())
Road = [list(map(int,input().split())) for i in range(k)]
Train = [list(map(int,input().split())) for i in range(l)]

uf_r = UnionFind(n)
uf_t = UnionFind(n)

for i in range(k):
    uf_r.union(Road[i][0]-1,Road[i][1]-1)

for i in range(l):
    uf_t.union(Train[i][0]-1,Train[i][1]-1)

Roots = [[0]*n for i in range(n)]

for i in range(n):
    Roots[uf_r.find(i)][uf_t.find(i)] += 1

ans = [0]*n

for i in range(n):
    ans[i] = Roots[uf_r.find(i)][uf_t.find(i)]

print(*ans)

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

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 union(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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

def main():
    n,k,l = map(int,input().split())
    Road = [list(map(int,input().split())) for i in range(k)]
    Train = [list(map(int,input().split())) for i in range(l)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots_dict = defaultdict(int)
    Roots = []
    for i in range(n):
        Roots.append(str(uf_r.find(i))+' '+str(uf_t.find(i)))
        Roots_dict[Roots[i]] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots_dict[Roots[i]]

    print(*ans)

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

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[N][W])