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

n=int(input())
l=list(map(int,input().split()))
m=float('inf')
for i in range(1,n):
    m=min(m,abs(sum(l[:i])-sum(l[i:])))
print(m)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
a,b=l[0],sum(l[1:])
m=abs(a-b)
for v in l[1:-1]:
    a+=v
    b-=v
    m=min(m,abs(a-b))
print(m)
### BUGGY CODE ###

ans=0
for i in range(int(input())):
 ans+=i
print(ans)

### FIXED CODE ###

n=int(input())
print((n-1)*n//2)
### BUGGY CODE ###

S = input()
C = [int(S[-(i + 1):]) % 2019 for i in range(len(S))]
Cd, C0 = {}, 0
for c in C:
    if c == 0:
        C0 += 1
    else:
        Cd[c] = Cd.get(c, 0) + 1
print(C0 + sum([v * (v - 1) // 2 for v in Cd.values()]))


### FIXED CODE ###

def modpow(d, b, p, mod=2019):
    ret = 1
    while p > 0:
        if p % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        p //= 2
    return (d * ret) % mod


S = input()
C = [0]
for i in range(len(S)):
    C.append((C[-1] + modpow(int(S[-(i + 1)]), 10, i)) % 2019)
Cd, C0 = {}, 0
for c in C[1:]:
    if c == 0:
        C0 += 1
    else:
        Cd[c] = Cd.get(c, 0) + 1
print(C0 + C0 * (max(0, C0 - 1)) // 2
      + sum([v * (v - 1) // 2 for v in Cd.values()]))
### BUGGY CODE ###

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(N)]
X = [XYZ[i][0] for i in range(N)]
Y = [XYZ[i][1] for i in range(N)]
Z = [XYZ[i][2] for i in range(N)]


import itertools

flag_list = [i for i in range(N)]
flag = itertools.combinations(flag_list, M)
ans = 0
for f in flag:
    ans_x = abs(sum([X[i] for i in f]))
    ans_y = abs(sum([Y[i] for i in f]))
    ans_z = abs(sum([Z[i] for i in f]))
    ans = max(ans, (ans_x + ans_y + ans_z))


print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
cakes = []
for i in range(N):
    x, y, z = map(int, input().split())
    cakes.append([x, y, z])


if M == 0:
    print(0)
    quit()
score = [0]*8
s = sorted(map(lambda c: c[0]+c[1]+c[2], cakes))
score[0] = sum(s[-M:])
score[1] = -sum(s[:M])
s = sorted(map(lambda c: c[0]+c[1]-c[2], cakes))
score[2] = sum(s[-M:])
score[3] = -sum(s[:M])
s = sorted(map(lambda c: c[0]-c[1]+c[2], cakes))
score[4] = sum(s[-M:])
score[5] = -sum(s[:M])
s = sorted(map(lambda c: c[0]-c[1]-c[2], cakes))
score[6] = sum(s[-M:])
score[7] = -sum(s[:M])
print(max(score))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import copy
S=list(input())
N=len(S)
point=0
hand=copy.deepcopy(S)
panum=sum([j=="p" for j in hand])
pamax=N//2#ポイントの上限
for i in range(N):
    if S[i]=="g":
        pa=sum([hand[j]=="p" for j in range(i+1)])#今まで出したパーの数
        if pa<(i+1)//2 and point<pamax-panum:
            hand[i]="p"
            point+=1
    if point>=pamax-panum:
        break
print(point)
        

### FIXED CODE ###

# coding: utf-8
# Your code here!
import copy
S=list(input())
N=len(S)
point=0
hand=copy.deepcopy(S)
panum=sum([j=="p" for j in hand])
pamax=N//2#ポイントの上限
pa=0
for i in range(N):
    if S[i]=="g" and pa<(i+1)//2 and point<pamax-panum:
        hand[i]="p"
        point+=1
    if point>=pamax-panum:
        break
    if hand[i]=="p":
        pa+=1
print(point)
### BUGGY CODE ###

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

x,y,z=a.count(1),a.count(2),a.count(3)
n=x+y*2+z*3


dp=[[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=0
def calc(h,i,j):
    global n,N
    if h+i+j==0 or h<0 or h>n or i<0 or i>n or j<0:
        return 0
    if dp[h][i][j]!=-1:
        return dp[h][i][j]
    dp[h][i][j]=(calc(h-1,i,j)*h/N+calc(h+1,i-1,j)*i/N+calc(h,i+1,j-1)*j/N+1)*N/(h+i+j)
    return dp[h][i][j]

a=calc(x,y,z)
print(dp[x][y][z])


### FIXED CODE ###

import numpy as np
from numba import njit

N=int(input())
a=[int(i) for i in input().split()]
x,y,z=0,0,0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    elif i==3:
        z+=1


dp=np.full((N+1,N+1,N+1),-1,dtype=np.float64)

dp[0][0][0]=0

@njit('f8(i8,i8,i8,i8,f8[:,:,:])', cache=True)
def calc(h,i,j,N,dp):
    if h+i+j==0:
        return 0
    if dp[h][i][j]>=0:
        return dp[h][i][j]
    A=1
    if h>=1:
        A+=calc(h-1,i,j,N,dp)*h/N
    if i>=1:
        A+=calc(h+1,i-1,j,N,dp)*i/N
    if j>=1:
        A+=calc(h,i+1,j-1,N,dp)*j/N
    A=A*N/(h+i+j)
    dp[h][i][j]=A
    return A

a=calc(x,y,z,N,dp)

print(dp[x][y][z])
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __file__=="test.py":
    f = open("./in_out/input.txt", "r", encoding="utf-8")
    read = f.read
    readline = f.readline

def main():
    R, C, K = map(int, readline().split())
    
    L_INF = int(1e17)
    dp = [[[-L_INF for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
    cell = [[0 for _ in range(C+1)] for _ in range(R+1)]
    
    for i in range(K):
        x, y, c = map(int, readline().split())
        cell[x-1][y-1] = c
    
    dp[0][1][0] = dp[1][0][0] = 0
    
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])
 
    print(dp[R][C][3])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
from numba import jit, void, i8
input = sys.stdin.readline

def main():
    R, C, K = map(int, input().split())

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = map(int, input().split())
        cell[x-1][y-1] = c

    f(dp, cell, R, C)

    print(dp[R][C][3])

@jit(void(i8[:,:,:],i8[:,:],i8,i8))
def f(dp, cell, R, C):
    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

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

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

#%%
keys = set(A)
keys = sorted(keys, reverse=True)

lengths = []
for k in keys:
    num = A.count(k)
    if num >= 4 and len(lengths) == 0:
        lengths.append(k)
        lengths.append(k)
    elif num >= 2:
        lengths.append(k)

    if len(lengths) == 2:
        break

try:
    ans = lengths[0] * lengths[1]
except:
    ans = 0

print(ans)

### FIXED CODE ###

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

lengths = []
for i in range(len(A) - 1):
    try:
        if A[i] == A[i+3] and len(lengths) == 0:
            lengths.append(A[i])
            lengths.append(A[i])
            break
    except:
        pass

    if (A[i] not in lengths) and (A[i] == A[i+1]):
        lengths.append(A[i])

    if len(lengths) == 2:
        break

try:
    ans = lengths[0] * lengths[1]
except:
    ans = 0

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

n,*a=map(int,open(0).read().split())
a.sort()
b=[0]*(10**6+1)
for i in a:
    b[i]+=1
    for j in range(2*i,10**6+1,i):
        b[j]+=2
print(b.count(1))

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
b=[0]*(10**6+1)
for i in a:
    b[i]+=1
    if b[i]==1:
        for j in range(2*i,10**6+1,i):
            b[j]+=100
print(b.count(1))
### BUGGY CODE ###

import math

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sum_dot = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for y in range(n):
        for x in range(n):
            sum_dot[y + 1][x + 1] = sum_dot[y][x + 1] + inp[y][:x + 1].count(".")
    
    ans = 0
    for i in range(int(math.sqrt(sum_dot[-1][-1])))[::-1]:
        p = [(x, y) for y in range(n - i) for x in range(n - i)]
        for x, y in p:
            s = sum_dot[y + i + 1][x + i + 1] - sum_dot[y][x + i + 1] - sum_dot[y + i + 1][x] + sum_dot[y][x]
            if s == (i + 1)*(i + 1):
                ans = i + 1
                break
        else:
            continue
        break
    print(ans)



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sq_max = [[0 for i in range(n + 1)] for j in range(n + 1)]
    
    for y in range(n):
        for x in range(n):
            if inp[y][x] == ".":
                sq_max[y + 1][x + 1] = min(sq_max[y][x + 1], sq_max[y + 1][x], sq_max[y][x]) + 1
            else:
                sq_max[y + 1][x + 1] = 0
    ans = max(map(max, sq_max))
    print(ans)
### BUGGY CODE ###

import fractions


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

a=A[0]
for b in A:
    a = a /fractions.gcd(a, b)*b

count=0
for i in A:
    count+=a/i

print(int(count)%((10**9)+7))

### FIXED CODE ###

import fractions
n=int(input())
A=list(map(int,input().split()))

a=A[0]
for b in A:
    a = (a * b) // fractions.gcd(a, b)

count=0
for i in A:
    count+=a//i

print((count%((10**9)+7)))
### BUGGY CODE ###

from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mul = 1
    mod = 10 ** 9 + 7
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            for j in range(0, 13):
                    next_dp[(int(s[i])*mul+j)%13] += dp[j]
                    next_dp[(int(s[i])*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mod = 10 ** 9 + 7

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

    #    mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

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

n, m = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()

for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        if A[j] < c:
            A[j] = c
    A.sort()
            
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()

BC = []
for _ in range(m):
    b, c = map(int, input().split())
    BC.append([b, c])

BC.sort(key=lambda x : x[1], reverse=True)
D = []
i = 0
count = 0
while (len(D) < n) and (len(BC) > i) :
    D.append(BC[i][1])
    count += 1
    if count == BC[i][0]:
        count = 0
        i += 1
        
j = 0
while (len(D) > j) and (A[j] <= D[j]) :
    A[j] = D[j]
    j += 1
    
print(sum(A))
### BUGGY CODE ###

def main():
    n = int(input())
    A = input().split()
    B = []
    k = n % 2
    for i in range(n):
        if i % 2 == k:
            B.append(A[i])
        else:
            B.insert(0, A[i])
    print(' '.join(B))


main()


### FIXED CODE ###

def main():
    n = int(input())
    A = input().split()
    B = [0] * n
    k = n % 2
    l = n // 2
    if k == 0:
        l -= 1
    r = l + 1
    for i in range(n):
        if i % 2 != k:
            B[l] = A[i]
            l -= 1
        else:
            B[r] = A[i]
            r += 1
    print(' '.join(B))


main()
### BUGGY CODE ###

import numpy as np
import sys
from operator import itemgetter

input = sys.stdin.readline

tl=200100

ft=np.zeros(tl,dtype=int)

def upd(i):
	global ft
	i+=1
	while(i<tl):
		ft[i]+=1
		i+=i&-i

def get(i):
	global ft
	i+=1
	ret=0
	while(i!=0):
	    ret+=ft[i]
	    i-=i&-i
	return ret

md = 998244353
n = int(input())

xyi = [[0]*3 for _ in range(n)]
for i in range(n):
	xyi[i][0],xyi[i][1] = [int(item) for item in input().split()]
xyi.sort(key=itemgetter(0))

for i in range(n):
	xyi[i][2]=i
xyi.sort(key=itemgetter(1))

cnt=np.zeros(n+1,dtype=int)

cnt[0]=1
for i in range(1,n+1):
	cnt[i]=cnt[i-1]*2%md

def comb(x):
	return cnt[x]-1;

ans=0

for aa in xyi:
	ix=aa[2]
	a=get(ix)
	b=get(n)-get(ix)
	c=ix-a
	d=n-ix-1-b
	exc=(comb(a+b)+comb(a+c)+comb(b+d)+comb(c+d)-comb(a)-comb(b)-comb(c)-comb(d))%md
	cur=(comb(n)-exc)%md
	ans=(ans+cur)%md
	upd(ix)

if(ans<0):ans+=md

print(ans)


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        if jobs[j][0] < M - i:
            break
        if jobs[j][0] == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)


### FIXED CODE ###

import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

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

n, m = map(int, input().split())
h = list(map(int, input().split()))
li = list(range(1,n+1))
ab = [list() for _ in range(m)]

p = []
pi = list(range(1,n+1))

ih = dict(zip(li, h))

for i in range(m):
    a, b = map(int,input().split())
    c = ih[a]
    d = ih[b]
    if c>d:
        p.append(b)
    elif d>c:
        p.append(a)
    else:
        p.append(a)
        p.append(b)

p = set(p)

for i in p:
    pi.remove(i)

print(len(pi))

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
li = list(range(1,n+1))
ab = [list() for _ in range(m)]

p = []

ih = dict(zip(li, h))

for i in range(m):
    a, b = map(int,input().split())
    c = ih[a]
    d = ih[b]
    if c>d:
        p.append(b)
    elif d>c:
        p.append(a)
    else:
        p.append(a)
        p.append(b)

print(n-len(set(p)))
### BUGGY CODE ###

import sys
 
 
N,M = sys.stdin.readline().strip().split()
N = int(N)
M = int(M)

A = []
B = []
for i in range(N):
    a,b = sys.stdin.readline().strip().split()
    A.append(int(a))
    B.append(int(b))
    
#print(A,B)

#print(A.index(min(A)))

num=0
money=0
num_tmp=0
while(num<M):
#    print("A!",A)
#    print("B!",B)
    if(len(A)>1):
        cheap_index = A.index(min(A))
        if(M-num<B[cheap_index]):
            num_tmp = M - num
            num += num_tmp
        else:
#            print("else num_tmp",B[cheap_index])
            num_tmp = B[cheap_index]
            num += num_tmp
        money += min(A) * num_tmp
        A.pop(cheap_index)
        B.pop(cheap_index)
#        print("num_tmp",num_tmp)
#        print("m,num", money,num)
    else:
        num_tmp = M - num
        num += num_tmp
        money += A[0] * num_tmp
#        print(money,num)
        
print(money)

### FIXED CODE ###


import sys
 
 
N,M = sys.stdin.readline().strip().split()
N = int(N)
M = int(M)

A = []
B = []
for i in range(N):
    a,b = sys.stdin.readline().strip().split()
    A.append(int(a))
    B.append(int(b))

#print(A)
#print(B)
comb = zip(A,B)
comb = sorted(comb)
#print(comb)
#print(comb[0][1])


num=0
money=0
num_tmp=0
while(num<M):
    if(len(comb)>1):
        if(M-num<comb[0][1]):
            num_tmp = M - num
            num += num_tmp
        else:
#            print("else num_tmp",B[cheap_index])
            num_tmp = comb[0][1]
            num += num_tmp
        money += comb[0][0] * num_tmp
        comb.pop(0)
#        print("num_tmp",num_tmp)
#        print("m,num", money,num)
    else:
        num_tmp = M - num
        num += num_tmp
        money += comb[0][0] * num_tmp
#        print(money,num)
        
print(money)
### BUGGY CODE ###

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1

for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10

print(ans)



### FIXED CODE ###

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1

for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019

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

[n,m] = [int(i) for i in input().split()]
ls = []
for i in range(n):
    ls.append(i+1)
for i in range(m):
    [l,r] = [int(i) for i in input().split()]
    ls = [0] * (l-1) + ls[l-1:r] + [0] * (n-r)
print(len([i for i in ls if i != 0]))


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
to_acc = [0] * (n+1)
for i in range(m):
  [l,r] = [int(j)-1 for j in input().split()]
  to_acc[l] += 1
  to_acc[r+1] -= 1
acc = [0]
ans = 0
for i in range(n+1):
  acc.append(acc[-1] + to_acc[i])
for i in range(1,n+1):
  if m == acc[i]:
    ans += 1
print(ans)
### BUGGY 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)

### 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)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]
 
for i in range(n):
  a[i] -= i+1
 
a.sort()
 
if n%2:
  s=0
  for i in range(n):
    s += abs(a[i]-a[n//2])
  print(s)
else:
  m=10**14
  for i in range(a[n//2-1],a[n//2]+1):
    s = 0
    for j in range(n):
      s += abs(a[j]-i)
    m = min(m,s)
  print(m)


### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]
 
for i in range(n):
  a[i] -= i+1
 
a.sort()
 
s = 0
for j in range(n):
  s += abs(a[j]-a[n//2])
print(s)
### BUGGY CODE ###

import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = queue.Queue()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.put([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while not q.empty():
        x,y = q.get()
        """
        if [x,y] == [gx,gy]:
            return ans[gy][gx]
        """
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)


### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)
"""))