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

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

MOD = 10**9+7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

X = [0]*(N+1)
X[0] = 1

for t in T:
    x = 1
    
    for i in range(N):
        prevX = X[i+1]

        if t == S[i]:
            X[i+1] = (X[i+1] + x)%MOD

        x =  (x + prevX)%MOD


print(sum(X)%MOD)


### FIXED CODE ###

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


def f(N, M, S, T):
    W = [1]*(N+1)

    for i, t in enumerate(T):
        W2 = W[:]
        
        k = 0
        for j, s in enumerate(S):
            if t == s:
                k += W[j]

            x = (W2[j+1] + k)%1000000007
            W2[j+1] = x

        W = W2
        
    return W[-1]



def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    print(f(N,M,S,T))



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

N,K = map(int,input().split())
A = [int(x) for x in input().split()]
B = list(set(A))

C = []
for i in B:
  C.append(A.count(i))

print(sum(sorted(C)[:-K:]))  

### FIXED CODE ###

import collections

N,K = map(int,input().split())
A = [int(x) for x in input().split()]

B = sorted(list(collections.Counter(A).values()),reverse=True)

print(sum(B[K::]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
x,k,d=map(int,input().split())
for i in range(k):
    v1 = x-d
    v2 = x+d
    x=min(abs(v1),v2)
print(abs(x))



### FIXED CODE ###

import sys
input = sys.stdin.readline
x,k,d=map(int,input().split())
x=abs(x)
if x<d:
    if k&1==0:
        print(x)
    else:
        print(abs(x-d))
    sys.exit()

val = x//d

if val>k:
    x-=(k*d)
    print(x)
    sys.exit()

x-=(val*d)
k-=val
if k&1==0:
    print(x)

else:
    ans = min(x+d,abs(x-d))
    print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
for i in range(a,b+1):
  if i==a:
    ans=a
  else:
    ans=(ans^i)
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if a%2==0:
  if b%2==1:
    print(((b-a+1)//2)%2)
  else:
    c=((b-a)//2)%2
    print(b^c)
else:
  if b%2 == 1:
    c=((b-a)//2)%2
    print(a^c)
  else:
    c=((b-a-1)//2)%2
    print((c^a)^b)
### BUGGY CODE ###

import bisect

def f(L):
    n = len(L)
    L.sort()
    count = 0
    # a=3 b=4 c=2, c < a + b => 2 < 3+4
    # a < b + c   =>  a - b < c  =>  c > a - b
    # b < c + a   =>  b - a < c  =>  c > b - a
    # c < a + b
    for i in range(n):
        for j in range(i + 1, n):
            a, b = L[i], L[j]
            start = bisect.bisect_left(L, max(a-b, b-a))
            end = bisect.bisect_left(L, a + b)
            for k in range(start, end):
                assert L[k] < a + b
                assert L[k] > a - b
#                assert L[k] > b - a
                if k != i and k != j and L[k] < a + b:
                    # other two checks
                    if L[k] < a + b and a < b + L[k] and b < L[k] + a:
                        count += 1
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)


### FIXED CODE ###

import bisect

def f(L):
    n = len(L)
    L.sort()

    count = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = L[i]
            b = L[j]
            start = max(a - b, b - a)
            end = a + b
            si = bisect.bisect_right(L, start)
            ei = bisect.bisect_left(L, end)
            zx = ei - si
            if i >= si and i < ei:
                zx -= 1
            if j >= si and j < ei:
                zx -= 1
            count += zx
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)
### BUGGY CODE ###

import sys

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

dp = [None] * N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        l = min(n, K)
        min_num = 10 ** 10
        dp[n] = min(min(abs(A[n] - A[n - k]) + dp[n - k], min_num) for k in range(1, l + 1))

print(dp[-1])


### FIXED CODE ###

import sys

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

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

print(dp[-1])
### BUGGY CODE ###

import itertools
x = int(input())
l = [0,1,2,3,4,5]
k = x%100
n = x//100
ans = '0'
c = list(itertools.combinations_with_replacement(l,n))
for i in c:
    if sum(i)==k:
        ans = '1'
        break
print(ans)

### FIXED CODE ###

import itertools
x = int(input())
k = x%100
n = x//100
ans = 0
if n*5>=k and n!=0:
    ans = 1
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = [a+i for i, a in enumerate(A)]
C = [j-a for j, a in enumerate(A)]
b_min = min(B)
b_max = max(B)
B, C = Counter(B), Counter(C)
ans = 0
for k in range(b_min, b_max):
    ans += B[k]*C[k]
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = [a+i for i, a in enumerate(A)]
C = [j-a for j, a in enumerate(A)]
B, C = Counter(B), Counter(C)
ans = 0
for k in B.keys():
    ans += B[k]*C[k]
print(ans)
### BUGGY CODE ###

import numpy as np

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

sum=0
while 1:
    max_A=max(A)
    max_index=np.argmax(A)
    A_new=A[max_index:]
    for a in A_new:
        sum+=max_A-a
    A=A[:max_index]
    if max_index==0:
        break

print(sum)

### FIXED CODE ###

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

sum=0
MaxNum=0
for i in range(N):
    MaxNum=max(MaxNum,A[i])
    B=MaxNum
    sum+=MaxNum-A[i]
    
print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t = map(int, input().split())
    G[s].append(t)

ans = []
V = set()

def dfs(n):
    for e in G[n]:
        dfs(e)
    if n not in V:
        ans.append(n)
        V.add(n)


for i in range(N):
    if i not in V:
        if i not in V:
            dfs(i)

print(*ans[::-1], sep="\n")



### FIXED CODE ###

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t = map(int, input().split())
    G[s].append(t)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


print(*topological_sort(G), sep="\n")
### BUGGY CODE ###

s = list(input())
len_queries = int(input())
queries = [input().split() for _ in range(len_queries)]

is_forward = True
for query in queries:
    if "1" == query[0]:
        is_forward = not is_forward
    else:
        if is_forward:
            insert_index = 0 if "1" == query[1] else len(s)
            s.insert(insert_index, query[2])
        else:
            insert_index = len(s) if "1" == query[1] else 0
            s.insert(insert_index, query[2])
if not is_forward:
    s.reverse()
print("".join(s))


### FIXED CODE ###

from collections import deque

s = deque(input())
len_queries = int(input())
queries = [input().split() for _ in range(len_queries)]

is_forward = True
for query in queries:
    if "1" == query[0]:
        is_forward = not is_forward
    else:
        if is_forward:
            if "1" == query[1]:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if "1" == query[1]:
                s.append(query[2])
            else:
                s.appendleft(query[2])
if not is_forward:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  for j in sorted(a):
    if a[i] % j == 0:
      if a[i] != j:
        ans += 1
        break
      else:
        if a.count(j) > 1:
          ans += 1
          break
    
print(n - ans)

### FIXED CODE ###

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

m = max(A)+1
dp = [1]*m
for a in A:
  if dp[a-1] == 1:
    dp[a-1] = 2
    for i in range(a*2, m, a):
      dp[i-1] = 0
  elif dp[a-1] == 2:
    dp[a-1] = 0
print(sum([1 for a in A if dp[a-1]]))
### BUGGY CODE ###

from itertools import product
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(len(s)):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    elif s[i] == 'B':
        b.append(i)

lst = list(product(r,g,b))
ans = len(lst)
for i in range(len(lst)):
    tmp = sorted(lst[i])
    if tmp[1]-tmp[0] == tmp[2]-tmp[1]:
        ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = 0
g = 0
b = 0
for x in s:
    if x == 'R':
        r += 1
    elif x == 'G':
        g += 1
    elif x == 'B':
        b += 1

ng_cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            continue
        else:
            k = 2 * j - i
            if k < n and s[i] != s[k] and s[j] != s[k]:
                ng_cnt += 1

print(r * g * b - ng_cnt)
### BUGGY CODE ###

A,B,K = map(int, input().split())
print(*[k for k in range(A,B+1) if k < A+K or B-K < k], sep="\n")

### FIXED CODE ###

A,B,K = map(int, input().split())
if B - A + 1> 2*K:
    a = list(range(A, A+K))
    b = list(range(B-K+1,B+1))
    c = sorted(set(a+b))
    print(*c, sep="\n")
else:
    print(*range(A,B+1), sep="\n")
### BUGGY CODE ###

N = int(input())
list = []
for i in range(N):
    number = int(input())
    if number in list:
        list.remove(number)
    else:
        list.append(number)
print(len(list))


### FIXED CODE ###

N = int(input())
Result = set()
for i in range(N):
    number = int(input())
    if  number in Result:
        Result.remove(number)
    else:
        Result.add(number)
print(len(Result))
### BUGGY CODE ###

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

l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n >= 2:
        r = m
    else:
        l = m

ansl = r
l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n <= 2:
        l = m
    else:
        r = m

ansr = l

if ansl <= ansr:
    print(ansl, ansr)
else:
    print(-1)


### FIXED CODE ###

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

l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n >= 2:
        r = m
    else:
        l = m

ansl = r
l = -1
r = 10**18
while r - l > 1:
    m = l + (r-l)//2
    n = m
    for i in range(k):
        n = n//a[i] * a[i]
    if n <= 2:
        l = m
    else:
        r = m

ansr = l

if ansl <= ansr:
    print(ansl, ansr)
else:
    print(-1)
### BUGGY CODE ###

S = input()
n = len(S)

cnt = [0] * 2019
a = int(S[n-1])
cnt[a%2019] += 1

for i in S[n-1::-1]:
  a = int(i+str(a))
  mod = a%2019
  cnt[mod] += 1

ans=cnt[0]
for i in cnt:
  ans += int(i*(i-1)/2)

print(ans)

### FIXED CODE ###

S = input()[::-1]
n = len(S)

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

ans=0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())

if M%N==0:
  print(M//N)
else:
  ans= (M//N)
  while ans > 1:
    if M%ans==0:
      break
    else:
      ans-=1
  print(ans)

### FIXED CODE ###

N,M=map(int,input().split())

if M%N==0:
  print(M//N)
else:
  ans= (M//N)
  cnt=[]
  for i in range(1,M):
    if i*i > M:
      break
    if M%i==0:
      cnt.append(i)
      cnt.append(M//i)
      
  cnt.sort(reverse=True)
  for j in range(len(cnt)):
    if cnt[j] < ans:
      ans=cnt[j]
      break
  
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print(dpt[W])

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

N = int(input())
S = input()
l, r = 0, N-1


def can(m):
    for j in range(N - 2*m + 1):
        for k in range(j + m, N - m + 1):
            if S[j:j+m] == S[k:k+m]:
                return True
    return False


for i in range(13):
    m = (l + r + 1) // 2
    if can(m):
        l = m
    else:
        r = m
print(l)

### FIXED CODE ###

N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)
### BUGGY CODE ###

import math

line1 = int(input())
line2 = str(input()).split(" ")
for index in range(len(line2)):
    line2[index] = int(line2[index])

keepTrack = dict()
keys = []
keys = list(set(line2))
for element in keys:
    keepTrack[element] = line2.count(element)

sum = 0
for key in keys:
    ##sum += abs()
    if (key < keepTrack[key]):
        sum += -key + keepTrack[key]
    elif (key > keepTrack[key]):
        sum += keepTrack[key]
print(sum)


### FIXED CODE ###

from collections import Counter
a = int(input())
l = list(map(int, input().split()))
#i = 1

c=Counter(l)
d = dict(c)
kv = []
for k,v in d.items():
    if k>v:
        kv.append(v)
    elif k<v:
        t = v-k
        kv.append(t)
s = sum(kv)
print(s)
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
S = input()
def main():
  dp = [[0]*(n+1) for _ in range(n+1)]
  for j in range(n):
    dp[1][j] = 1
  for i, s in enumerate(S, 1):
    if s == "<":
      dp[i+1][n-(i+1)] = dp[i][n-i]
      for j in range(n-i-2, -1, -1):
        dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
        dp[i+1][j] %= MOD
    else:
      dp[i+1][0] = dp[i][0]
      for j in range(1, n-i):
        dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
        dp[i+1][j] %= MOD
  ans = dp[n][0]
  print(ans)
if __name__ == "__main__":
  main()


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(60):
        flag1 = sum([1 for x in a if x & (1 << i)])
        flag0 = n - flag1
        ans += (1 << i) * (flag1 * flag0)
        ans %= MOD
    print(ans)


### FIXED CODE ###

if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    res = 0
    two_factor = 1

    for d in range(60):
        even, odd = 0, 0
        for i in range(n):
            if a[i] & (1 << d):
                odd += 1
            else:
                even += 1
        add = (odd * even) % MOD * two_factor % MOD
        res = (res + add) % MOD
        two_factor = two_factor * 2 % MOD

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

n=int(input())
t=tuple(map(int,input().split()))
while True:
  if t[0]!=0:
    print(0)
    break
  m=max(t)
  a=tuple(t.count(i) for i in range(m+1))
  if a[0]!=1:
    print(0)
    break
  s=1
  for i in range(m):
    s=(s*(a[i]**a[i+1]))%998244353
  print(s)
  break

### FIXED CODE ###

n=int(input())
t=tuple(map(int,input().split()))
while True:
  if t[0]!=0:
    print(0)
    break
  m=max(t)
  a=[0]*(m+1)
  for i in range(n):
    a[t[i]]+=1
  a=tuple(a)
  if a[0]!=1:
    print(0)
    break
  s=1
  for i in range(m):
    s=(s*(a[i]**a[i+1]))%998244353
  print(s)
  break
### BUGGY CODE ###

def cmb2(n):
	result = n * (n - 1) / 2

	return result

if __name__ == "__main__":

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

	A_set = set(A)

	ans_d = {}
	for a_s in A_set:
		#print(A.count(a))
		ans_d[str(a_s)] = A.count(a_s)



	for a in A:
		A_new = ans_d.copy()
		A_new[str(a)] -= 1
		ans = 0
		#print(A_new)
		#print("="*10)
		for a_n in A_new.values():
			if a_n <= 1:
				continue
			else:
				ans += cmb2(a_n)
		print(int(ans))
		#ans_d[str(a)] += 1

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]
	# A = list(map(int, input().split()))

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY CODE ###

r,c,k = list(map(int, input().split()))

dp=[[[0]*4 for _ in range(c)] for _ in range(r)]

F = {}

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[(x,y)] = v
  
for i in range(r):
  for j in range(c):
    if (i,j) in F:
      val = F[(i,j)]
    else:
      val = 0
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv
    #print(dp[i])
    
best = 0

for j in range(c-1,c):
  for k in range(4):
    best = max(best, dp[-1][j][k])
    
print(best)

### FIXED CODE ###

r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)
### BUGGY CODE ###

import sys
x = int(input())


number = int(x/100)
xn = x-number*100
number = number+1

for i in range(0,number):
    for j in range(0,number):
        for k in  range (0,number):
            for l in range(0,number):
                for m in range(0,number):
                    for n in range(0,number):
                        if j*1+k*2+l*3+m*4+n*5==xn:
                            if i*100+j*101+k*102+l*103+m*104+n*105==x:
                                print(1)
                                sys.exit()
print(0)

### FIXED CODE ###

import sys
x = int(input())


number = int(x/100)
number = number+1

for i in range(0,number):
    for j in range(0,number-i):
        for k in  range (0,number-i-j):
            for l in range(0,number-i-j-k):
                for m in range(0,number-i-j-k-l):
                    for n in range(0,number-i-j-k-l-m):
                        if i*100+j*101+k*102+l*103+m*104+n*105==x:
                            print(1)
                            sys.exit()
print(0)
### BUGGY CODE ###

import itertools

N,MA,MB = map(int,input().split())
arr = []

for i in range(N):
  l = list(map(int,input().split()))
  arr.append(l)
  
dp = [ [ [50000 for k in range(401)] for j in range(401)] for i in range(N+1) ]
dp[0][0][0] = 0

for i,a,b in itertools.product(range(1,N+1),range(401),range(401)):
  A = arr[i-1][0]
  B = arr[i-1][1]
  C = arr[i-1][2]
  
  if A <= a and B <= b:
    dp[i][a][b] = min(dp[i][a][b],dp[i-1][a-A][b-B] + C)
  else:
    dp[i][a][b] = dp[i-1][a][b]

ans = 50000
for i,a,b in itertools.product(range(N+1),range(401),range(401)):
  if a * MB == b ** MA and a != 0 and b != 0:
    ans = min(ans,dp[i][a][b])
if ans == 50000:
  print(-1)
else:
  print(int(ans))

### FIXED CODE ###

import itertools

N,MA,MB = map(int,input().split())
arr = []

for i in range(N):
  l = list(map(int,input().split()))
  arr.append(l)
  
dp = [ [ [50000 for k in range(401)] for j in range(401)] for i in range(N+1) ]
dp[0][0][0] = 0
ans = 50000

for i,a,b in itertools.product(range(1,N+1),range(401),range(401)):
  A = arr[i-1][0]
  B = arr[i-1][1]
  C = arr[i-1][2]
  
  if A <= a and B <= b and dp[i-1][a-A][b-B] != 50000:
    dp[i][a][b] = min(dp[i-1][a][b],dp[i-1][a-A][b-B] + C)
  else:
    dp[i][a][b] = dp[i-1][a][b]

for a,b in itertools.product(range(401),range(401)):
    if a * MB == b * MA and a != 0 and b != 0:
      ans = min(ans,dp[-1][a][b])
    
if ans == 50000:
  print(-1)
else:
  print(int(ans))
### BUGGY CODE ###

N, K, L = map(int, input().split())
city = [{"path":{i},"train":{i}} for i in range(N)]
for i in range(K):
    p, q = map(int, input().split())
    join = city[p-1]["path"] | city[q-1]["path"]
    for j in join:
        city[j]["path"] = join
for i in range(L):
    r, s = map(int, input().split())
    join = city[r-1]["train"] | city[s-1]["train"]
    for j in join:
        city[j]["train"] = join
else:
    del join
for k in range(N):
    print(len(city[k]["path"]&city[k]["train"]), end=" ")


### FIXED CODE ###

N, K, L = map(int, input().split())

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")