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

# RRL
# 111
# 021
# 012
# 021 ...
# 1e5 1e5 だけどもしかしたら通るかも...
s = input()
children = [1] * len(s)
for i in range(int(1e5)):
    new_children = [0] * len(s)
    for j in range(len(s)):
        if s[j] == 'R':
            new_children[j+1] += children[j]
        else:
            new_children[j-1] += children[j]
    children = new_children[:]
print(' '.join(map(str, children)))

### FIXED CODE ###

# RL
# 0, 11
# 1, 11
# 2, 11
# 3. 11
# 4, 11 1回で収束して以降は同じ

# RRL
# 0, 111
# 1, 021
# 2, 012
# 3. 021
# 4, 012 1回で収束して以降は振動する


# RRLL
# 0, 1111
# 1, 0220
# 2, 0220
# 3, 0220
# 4, 0220 1回で収束して以降は振動(差分0だけど)

# RRRLL
# 0, 11111
# 1, 01220
# 2, 00320
# 3, 00230
# 4, 0033000 2回で収束して以降は振動

# RRLLL
# 0, 11111
# 1, 02210
# 2, 02300
# 3, 03200
# 4, 02300 2回で収束して以降は振動

# RRRLLL
# 0, 111111
# 1, 012210
# 2, 003300
# 3, 003300
# 4, 0033000 2回で収束して以降は振動

# RRRRRR...RLLL....L の時、max(len(R), len(L)) - 1回で 0, 0, 0,len(R), len(L), 0, 0, 0, に収束してそう

# RR|LLL
# ab|cde

#  a|be
#  c|d

#  b|a
#  d|e
#   |c
# 以降振動

# 境界から距離が奇数のRは左、偶数は右, RRLLL ->   01100
# 境界から距離が奇数のLは右、偶数は左, RRLLL -> + 01200
#                                               = 02300
import math
s = input()
rrr = [0] * len(s)
lll = [0] * len(s)
ct = 0
for i in range(len(s)):
    if s[i] == 'R':
        ct += 1
    elif ct != 0:
        rrr[i-1] = math.ceil(ct/2)
        rrr[i] = math.floor(ct/2)
        ct = 0
s = s[::-1]
for i in range(len(s)):
    if s[i] == 'L':
        ct += 1
    elif ct != 0:
        lll[i-1] = math.ceil(ct/2)
        lll[i] = math.floor(ct/2)
        ct = 0
lll = lll[::-1]
#print(s[::-1])
#print(rrr)
#print(lll)
print(' '.join(map(str, [r+l for (r,l) in zip(rrr, lll)])))
### BUGGY CODE ###

N = int(input())
i = 1
count = 0
while i <= N:
    I = str(i)
    I = list(I)
    if I.count("3")>0 and I.count("5")>0 and I.count("7"):
        if I.count("0")==0 and I.count("1")==0 and I.count("2")==0 and I.count("4")==0 and I.count("6")==0 and I.count("8")==0 and I.count("9")==0:
            count+=1
            i+=1
        else:
            i+=1
    else:
        i+=1
print(count)

### FIXED CODE ###

N = int(input())
def shichi(n):
    if int(n) > N:
        return 0
    ret=1 if all(n.count(c)>0 for c in "753") else 0
    for c in "753":
        ret += shichi(n+c)
    return ret
print(shichi("0"))
### BUGGY CODE ###

from operator import itemgetter

K = int(input().split()[-1])

A = sorted([int(e) for e in input().split()], reverse=True)
B = sorted([int(e) for e in input().split()], reverse=True)
C = sorted([int(e) for e in input().split()], reverse=True)


def get_next_iter(i, _list):
    if i < len(_list) - 1:
        return i + 1
    else:
        return i


values = []

ia = ib = ic = 0


def get_value(ia, ib, ic):
    return A[ia] + B[ib] + C[ic]


def get_next(ia, ib, ic):
    ia_n = get_next_iter(ia, A)
    ib_n = get_next_iter(ib, B)
    ic_n = get_next_iter(ic, C)
    s = set()
    s.add((ia_n, ib, ic, get_value(ia_n, ib, ic)))
    s.add((ia, ib_n, ic, get_value(ia, ib_n, ic)))
    s.add((ia, ib, ic_n, get_value(ia, ib, ic_n)))
    return s


values.append((ia, ib, ic, get_value(ia, ib, ic)))
candidate = get_next(0, 0, 0)

for k in range(K - 1):
    vs = sorted(candidate, reverse=True, key=itemgetter(3))
    for i, v in enumerate(vs):
        if v not in values:
            values.append(v)
            candidate.remove(v)
            for each in get_next(v[0], v[1], v[2]):
                candidate.add(each)
            break
        else:
            continue

for each in values:
    print(each[3])


### FIXED CODE ###

from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())

A = sorted([int(e) for e in input().split()], reverse=True)
B = sorted([int(e) for e in input().split()], reverse=True)
C = sorted([int(e) for e in input().split()], reverse=True)


def get_value(ai, bi, ci):
    return -(A[ai] + B[bi] + C[ci])


heap = []
heappush(heap, (get_value(0, 0, 0), 0, 0, 0))
used = {(0, 0, 0)}

for k in range(K):
    v, ia, ib, ic = heappop(heap)
    print(-v)

    if ia + 1 < X and (ia + 1, ib, ic) not in used:
        heappush(heap, (get_value(ia + 1, ib, ic), ia + 1, ib, ic))
        used.add((ia + 1, ib, ic))
    if ib + 1 < Y and (ia, ib + 1, ic) not in used:
        heappush(heap, (get_value(ia, ib + 1, ic), ia, ib + 1, ic))
        used.add((ia, ib + 1, ic))
    if ic + 1 < Z and (ia, ib, ic + 1) not in used:
        heappush(heap, (get_value(ia, ib, ic + 1), ia, ib, ic + 1))
        used.add((ia, ib, ic + 1))
### BUGGY CODE ###

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
#if l[i] == l[j]: continue
n = int(input())
a = list(map(int, input().split()))
sumple = a
dummy = a
ans = 0

for i in range(len(a) - 1):
    sumple = a
    dummy = sumple[i+1:len(a)]
    ans += sum(dummy) * a[i]

print(ans % 1000000007)


### FIXED CODE ###

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
#if l[i] == l[j]: continue
n = int(input())
a = list(map(int, input().split()))
ans = 0
min = 0
new_list = list(reversed(a))

for i in range(len(new_list) - 1):
    min += new_list[i]
    ans +=  min * new_list[i+1]


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

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

for _ in range(q):
    li, ri = map(int, input().split())
    print(s[li - 1:ri].count('AC'))

### FIXED CODE ###

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

a = [0, 0]
for i in range(2, n + 1):
    a.append(a[i - 1] + (s[i - 2:i] == 'AC'))


for _ in range(q):
    li, ri = map(int, input().split())
    print(a[ri] - a[li])
### BUGGY CODE ###

import sys
N = int(input())

if N == 1:
    print(1)
    sys.exit(0)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


P = prime_factorize(N)

ans = len(str(N))

for i in range(2 ** (len(P) - 1)):
    a = 1
    b = 1
    for j in range(len(P)):
        if (i >> j) & 1 == 1:
            a *= P[j]
        else:
            b *= P[j]

    ans = min(ans, max(len(str(a)), len(str(b))))

print(ans)


### FIXED CODE ###

import sys
N = int(input())

if N == 1:
    print(1)
    sys.exit(0)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


P = prime_factorize(N)

ans = len(str(N))

for i in range(2 ** (len(P) - 1)):
    a = 1
    b = 1
    for j in range(len(P)):
        if (i >> j) & 1 == 1:
            a *= P[j]
        else:
            b *= P[j]

    ans = min(ans, max(len(str(a)), len(str(b))))

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

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters.sort()

ans = 0
for i in range(N):
    x, h = monsters[i]
    if h <= 0:
        continue
    bomb = (h+A-1) // A
    damage = bomb * A
    right = x + 2*D
    for j in range(i+1, N):
        if monsters[j][0] > right:
            break
        monsters[j][1] -= damage
    ans += bomb
print(ans)


### FIXED CODE ###

from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
monsters = [tuple(map(int, input().split())) for _ in range(N)]
heapify(monsters)

max_H = 10**9
ans = 0
damage = 0
while monsters:
    x, h = heappop(monsters)
    if h <= max_H:
        h -= damage
        if h <= 0:
            continue
        bomb = (h+A-1) // A
        damage += bomb * A
        ans += bomb
        heappush(monsters, (x+2*D, max_H+bomb*A))
    else:
        damage -= h-max_H
print(ans)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
cnt = 0
for i in range(len(S)-3):
    mul3 =0
    num = 0
    for j in range(i,len(S)):
        mul3 = (mul3 + int(S[j]))%3
        num = num*10+int(S[j])
        if mul3 == 0:
            if num%2019 ==0:
                cnt += 1
print(cnt)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
Smod2019=[0]
num = 0
deg = 0
for i in range(len(S)-1,-1,-1):
    num = (num+int(S[i])*pow(10,deg,2019))%2019
    Smod2019.append(num)
    deg += 1
Sc = collections.Counter(Smod2019)

cnt = 0
for val in Sc.values():
    cnt += val*(val-1)//2
print(cnt)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

count = 0
while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)
### BUGGY CODE ###

from fractions import gcd
def gen(x):
    i = 2
    while i * i <= x:
        yield i
        i += 1

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    ans = 1
    for i in gen(g):
        if (g % i) == 0:
            ans += 1
            while(g % i == 0):g // i
    if g != 1:ans += 1

    print(ans)
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
def gen(x):
    i = 1
    while i * i <= x:
        yield i
        i += 1

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    gl = []
    for i in gen(g):
        if (g % i) == 0:
            gl.append(i)
            gl.append(g // i)
    gl =set(gl)
    p = []
    for i in gl:
        b = True
        for j in gen(i):
            if j == 1:continue
            if (i % j) == 0:
                b = False
                break
        if b:
            p.append(i)
    ans = 0
    for i in p:
        if i in p:ans+=1

    
    print(ans)
    

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

N, W = map(int, input().split())
w = [0]
v = [0]

for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for col in range(W+1)] for row in range(N+1)]

#dp[i][j] = i番目までのお菓子の中から，ナップサックの中のお菓子の重さの総和がjを超えないようにいくつかお菓子を選んで詰めるとき，価値の最大値

for i in range(1, N+1):
    for j in range(1, W+1):
        if j - w[i] >= 0: #ex.ナップサックの耐加重がj=100,で, i番目のお菓子の重さが20である場合，ナップサックに追加することができるのは，i-1番目までのお菓子でまだ80以下の重さしかないとき。
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]
v = [0]

for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for col in range(W+1)] for row in range(N+1)]

#dp[i][j] = i番目までのお菓子の中から，ナップサックの中のお菓子の重さの総和がjを超えないようにいくつかお菓子を選んで詰めるとき，価値の最大値

for i in range(1, N+1):
    for j in range(1, W+1):
        if j - w[i] >= 0: #ex.ナップサックの耐加重がj=100,で, i番目のお菓子の重さが20である場合，ナップサックに追加することができるのは，i-1番目までのお菓子でまだ80以下の重さしかないとき。
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

from collections import Counter

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

cnt = Counter(A) 

A = list(set(A))
A.sort()


C = [0]*(10**6+1)
ans = 0

for a in A:
    if cnt[a] == 1 and C[a] == 0:
        ans += 1

    i = 1
    while True:
        if a*i > 10**6:
            break
        C[a*i] = 1
        i += 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(A) 

A = list(set(A))
A.sort()


C = [0]*(10**6+1)
ans = 0

for a in A:
    if C[a] == 0:
        i = 1
        while True:
            if a*i > 10**6:
                break
            C[a*i] = 1
            i += 1
        if cnt[a] == 1:
            ans += 1

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

i = list(map(int,input().split()))
n = i[0]
l = i[1]

alist = []
i = 1

while i <= n:
  x = l + i - 1
  alist.append(x)
  i =+ 1
  
  
j = 0
abslist = []
while j < n:
  abslist[j] = abs(alist[j])
  j =+ 1

  

k = 0
m = 0
while k < n-1:
  if abslist[k] >= abslist[k+1]:
    m = k+1
  
  k =+ 1
  
  
print(sum(alist) - alist[m])



  
  
  

### FIXED CODE ###

i = list(map(int,input().split()))
n = i[0]
l = i[1]
 
alist = []
j = 0
 
for j in range(n):
  x = l + j
  alist.append(x)
  
   
k = 0
m = 0
for k in range(n-1):
  if abs(alist[k]) >= abs(alist[k+1]):
    m = k+1
  
  
print(sum(alist) - alist[m])
### BUGGY CODE ###

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

lst = []
for i in range(1, min(A, B)+1):
    if A % i == 0 and B % i == 0:
        lst.append(i)
        
import math

cnt = 0

for j in lst:    
    flag = 1
    for k in range(2, int(math.sqrt(j))+1):
        if j % k == 0:
            flag = 0
            break
    cnt += flag

print(cnt)

### FIXED CODE ###

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

import math

if A < B:
    A, B = B, A
    
while A % B != 0:
    A, B = B, A%B
    
ans = 1

for i in range(2, int(math.sqrt(B))+1):
    if B % i == 0:
        ans += 1
        
        while B % i == 0:
            B //= i
            
if B > 1:
    ans += 1
    
print(ans)
### BUGGY CODE ###

from sys import stdin

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

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

A = [0]
B = [0]

for i in range(0, n):
    A.append(A[i]+a[i])
for i in range(0, m):
    B.append(B[i]+b[i])


ans= 0
for i in range(n + 1):
    j = m
    if A[i] > k:
        break
    while A[i]  > k- + B[j]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

### FIXED CODE ###

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

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


a_pre,b_pre=[0],[0]

for i in range(n):
	a_pre.append(a_pre[i]+a[i])

for i in range(m):
	b_pre.append(b_pre[i]+b[i])

ans,j=0,m
for i in range(n+1):
	if a_pre[i]>k:
		break
	while b_pre[j]>k-a_pre[i]:
		j-=1

	ans=max(ans,i+j)

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
nans = 0
for i in range(10**9):
    for j in range(n):
        ans += abs(a[j]-i-j)
    if ans <= nans:
        nans =ans
print(nans)

### FIXED CODE ###

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

box = [0]*n
ans = 0
for i in range(n):
    box[i] = a[i] - (i+1)
box.sort()

idx = n//2

b = box[idx]

for i in range(n):
    ans += abs(a[i]-(i+1+b))
print(ans)
### BUGGY CODE ###

import sys
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if  a[i][-1]-1==vs and a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1] and check[n]:
      print(-1)
      sys.exit()
  jyunban=jyunban_n[:]
        
print(day)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()
    a.sort()

    lcm = lcm_list(a)

    ans = 0
    for ai in a:
        ans += lcm // ai
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()

    lcm = a[0]
    for i in a:
        lcm = lcm // math.gcd(lcm, i) * i
    lcm %= MOD

    ans = 0
    for ai in a:
        ans += lcm * pow(ai, MOD - 2, MOD) % MOD
        ans %= MOD

    print(ans)


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

n=int(input())
S=set()
for i in range(n):
  S=S^set([input()])
print(len(S))

### FIXED CODE ###

n=int(input())
S=set()
for i in range(n):
  S^=set([input()])
print(len(S))
### BUGGY CODE ###

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


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

A.sort()
ans = 1

for i in range(N):
    B = A[:]
    B.pop(i)
    tmp=B[0];
    for j in B:
        if(ans>j):
            break
        tmp=gcd(tmp,j)

    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

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


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

L = [0] * (N + 1)
L[0] = 0
R = [0] * (N + 1)
R[0] = 0

for i in range(N):
    L[i + 1] = gcd(L[i], A[i])
    R[i + 1] = gcd(R[i], A[-i - 1])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i], R[N - i - 1]))
print(ans)
### BUGGY CODE ###

def getlist():
	return list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	for i in range(1, N + 1):
		s3.append(sorted([s1[i], s2[i]]))

	X = [[0] * (N + 1) for i in range(N + 1)]
	for i in range(N):
		X[s3[i][0]][s3[i][1]] += 1

	ans = []
	for i in range(N):
		ans.append(str(X[s3[i][0]][s3[i][1]]))

	print(" ".join(ans))


if __name__ == '__main__':
	main()

### FIXED CODE ###

from collections import defaultdict
con = 300000

def getlist():
	return list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

    def siz(self, x):
        x = self.find(x)
        return self.size[x]

#処理内容
def main():
	#受け取り、処理
	N, K, L = getlist()
	UFp = UnionFind(N)
	UFr = UnionFind(N)
	for i in range(K):
		p, q = getlist()
		UFp.union(p, q)
	for i in range(L):
		r, s = getlist()
		UFr.union(r, s)

	for i in range(1, N):
		UFp.find(i)
		UFr.find(i)

	s1 = UFp.par
	s2 = UFr.par
	s3 = []
	
	for i in range(1, N + 1):
		s3.append([s1[i], s2[i]])

	#前計算
	D = defaultdict(int)
	for i in range(N):
		a = s3[i][0]
		b = s3[i][1]
		D[a * con + b] += 1
	#答え
	ans = []
	for i in range(N):
		ans.append(D[s3[i][0] * con + s3[i][1]])
	print(" ".join(list(map(str, ans))))

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

# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    if v == 1:
        dp[v] = (dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v-1] + dp[v-2])%(1000000007)
print(dp[N])

### FIXED CODE ###

# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
A = set(A)

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

# 初期条件
dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    dp[v] = (dp[v] + dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v] + dp[v-2])%(1000000007)
print(dp[N])