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

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

Grin1=[set() for i in range(N+1)]
Grin2=[set() for i in range(N+1)]

for i in range(1,N+1):
    Grin1[Group1[find1(i)]].add(i)
    Grin2[Group2[find2(i)]].add(i)

for i in range(1,N+1):
    print(len(Grin1[find1(i)] & Grin2[find2(i)]),end=" ")


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,K,L=map(int,input().split())
R=[list(map(int,input().split())) for i in range(K)]
T=[list(map(int,input().split())) for i in range(L)]

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

from collections import defaultdict
ANS = defaultdict(int)

for i in range(1,N+1):
    ANS[(find1(i),find2(i))]+=1

for i in range(1,N+1):
    print(ANS[(find1(i),find2(i))])
### BUGGY CODE ###

from collections import Counter

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
A = [int(hoge) for hoge in input().split()]
TF = dict()
C = Counter(A)
A.sort()
yakusu = set()
for q,a in enumerate(A):
    Y = make_divisors(a)[:-1]
    for y in Y:
        if y not in TF:
            TF[y] = []
        TF[y].append(a)
kotae = set()
for a in A:
    if a in TF:
        kotae = kotae | set(TF[a])
    if C[a] >= 2:
        kotae.add(a)

print(N - sum([C[k] for k in kotae]))

### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)
### BUGGY CODE ###

import sys

H, N = list(map(int, input().split()))
AB = []
for n in range(N):
    AB.append(list(map(int, input().split())))

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])


### FIXED CODE ###

import sys

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for n in range(N)]

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])
### BUGGY CODE ###

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

mod=10**9+7

ans=0

for i in range (N-1):
    for j in range(i+1,N):
        ans+=ls[i]*ls[j]%mod
        ans%=mod
print(ans)

### FIXED CODE ###

# AtCoder Beginner Contest 177
# C - Sum of product of pairs

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

mod=10**9+7

ans=0
accumls=[0]

for i in range (N):
    accumls.append(accumls[-1]+ls[i])

for i in range (N-1):
    ans+= ls[i]*(accumls[-1]-accumls[i+1])
    ans%=mod

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

s = input()

result = 0
flag = 1

while flag > 0:
    flag = 0
    count = s.count('ABC')
    if count > 0:
        flag = 1
        result += count
        s = s.replace('ABC', 'BCA')
            
print(result)

### FIXED CODE ###

s = input()

N = len(s)

i = 0
result = 0
count_a = 0
count_bc = 0

while i < N-2:
    if s[i] == 'A':
        while s[i] == 'A' and i < N-2:
            count_a += 1
            i += 1
        
        if i >= N-1:
            break
                        
        while s[i] == 'B' and s[i+1] == 'C':
            count_bc += 1
            i += 2
            if i >= N-1:
                break
        
        result += count_a * count_bc

        if i >= N-1:
            break
        
        if count_bc > 0 and s[i] == 'A':
            count_a = count_a
        else:
            count_a = 0
        
        count_bc = 0
                    
    else:
        i += 1
        
print(result)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
min = 0
M = [0] * N
for i in range(N) :
    for j in range(i):
        if M[i] > A[i]- A[j] :
            M[i] = A[i]- A[j]
    min = min + abs(M[i])
print(min)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
min = 0
for i in range(N):
    if i == 0:
        max = A[i]
    else :
        if max > A[i] :
            min = min + max - A[i]
        else :
            max = A[i]   
print(min)
### BUGGY CODE ###

n = int(raw_input())
S = map(int, raw_input().strip().split(' '))
q = int(raw_input())
T = map(int, raw_input().strip().split(' '))

def binary_search(S,k):
    if len(S) == 1 and S[0] != k: return False
    p = len(S)/2
    if S[p] == k: return True
    elif S[p] > k:
        return binary_search(S[:p],k)
    else:
        return binary_search(S[p:],k)

c = 0
for t in T:
    if binary_search(S,t): c += 1
print c

### FIXED CODE ###

def search(a, x):
    n = len(a)
    hi = n-1
    lo = 0
    while hi >= lo:
        med = (hi+lo)/2
        if a[med] == x:
            return True
        elif a[med] > x:
            hi = med-1
        else:
            lo = med+1
    return False

n = int(raw_input())
S = map(int, raw_input().split(' '))
q = int(raw_input())
T = map(int, raw_input().split(' '))

found = 0
for x in T:
    if search(S, x):
        found += 1

print found
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    d, g = map(int, args[0].split())
    g //= 100
    pc = [tuple(map(int, a.split())) for a in args[1:]]
    inf = 10**12
    dp = {}

    for i, (p, c) in enumerate(pc):
        c //= 100
        if i == 0:
            for k in range(p):
                s = min(g, (i+1)*(k+1) + (c if k+1 == p else 0))
                dp[s] = k+1
        else:
            items = tuple(dp.items())
            for t, m in items:
                for k in range(p):
                    s = min(g, (i+1)*(k+1) + (c if k+1 == p else 0))
                    s_t = min(g, s+t)
                    dp[s] = min(dp.get(s, inf), k+1)
                    dp[s_t] = min(dp.get(s_t, inf), k+1+m)
    return str(dp[g])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    d, g = map(int, args[0].split())
    pc = [tuple(map(int, a.split())) for a in args[1:]]
    inf = 10**5

    count = inf
    for b in range(2**d):
        score, cnt = 0, 0

        for i in range(d):
            p, c = pc[i]
            if b >> i & 1:
                score += p*100*(i+1)+c
                cnt += p

        if score < g:
            for i in reversed(range(d)):
                if b >> i & 1:
                    continue
                else:
                    p, c = pc[i]
                    j = 0
                    while score < g and j < p:
                        score += 100*(i+1)
                        cnt += 1
                        j += 1

                    if j == p:
                        score += c

        count = min(count, cnt)

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

N, M = map(int, input().split())
ken = [[] for _ in range(N)]
shi = []
for _ in range(M):
    P, Y = map(int, input().split())
    ken[P-1].append(Y)
    shi.append((P, Y))
for k in ken:
    k.sort()
for s in shi:
    print("{:06}{:06}".format(s[0], ken[s[0]-1].index(s[1])+1))

### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
iPY = [0]*M
res = [0]*M
for i in range(M):
    P, Y = map(int, input().split())
    iPY[i] = (i, P, Y)
iPY.sort(key=itemgetter(2))
iPY.sort(key=itemgetter(1))
j = 1
p = iPY[0][1]
for i, P, Y in iPY:
    if P != p:
        j = 1
        p = P
    res[i] = "{:06}{:06}".format(P, j)
    j += 1
for s in res:
    print(s)
### BUGGY CODE ###

X = int(input())

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 f(a, b):
  return a**5 - b**5

divs = make_divisors(X)
ans = 0
for div in divs:
  a = -div-100
  b = -100
  while f(a, b) < X and a < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
  a = -100
  b = -div-100
  while f(a, b) > X and b < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
    
print(ans[0], ans[1])

### FIXED CODE ###

X = int(input())

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()
    save = -1
    for i in range(len(divisors)):
        if divisors[i] >= 200:
            save = i
            break
    if save > 0:
        divisors = divisors[:save]
    return divisors

def f(a, b):
  return a**5 - b**5

divs = make_divisors(X)
ans = 0
for div in divs:
  a = -div-120
  b = -120
  while f(a, b) < X and a < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
  a = -120
  b = -div-120
  while f(a, b) > X and b < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
    
print(ans[0], ans[1])
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]
for i in range(1,n):
  lcm=lcm*A[i]//gcd(lcm,A[i])

ans=0
for i in range(n):
  ans=(ans+lcm//A[i])%mod
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]

chk=True

for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])
  if lcm>10**50000:
    chk=False
    break

if chk:
  ans=0
  for i in range(n):
    ans=(ans+lcm//A[i])%mod
  print(ans)
else:
  ans=0
  mult=1
  for a in A:
    mult=(mult*a)%mod
  for a in A:
    ans=(ans+mult*pow(a,mod-2,mod))%mod
  print(ans)
### BUGGY CODE ###

N = int(input())
nums = list(map(int, input().split()))
ans = [0] * N

for i in reversed(range(1,N+1)):
    count = 0
    total = 0
    for j in range(i,N+1):
        if j % i == 0:
            count += 1
            # 既にfixされた数を加算
            total += ans[j-1]
    # 倍数が一つのとき
    if count == 1:
        if nums[i-1] == 0:
            ans[i-1] = 0
        else:
            ans[i-1] = 1
    # 倍数が複数ある
    else:
        # 指定が偶数
        if nums[i-1] == 0:
            if total % 2 != 0:
                ans[i-1] = 1
        else:
            if total % 2 == 0:
                ans[i-1] = 1


result = [i+1 for i in range(len(ans)) if ans[i] == 1]
result = [str(i) for i in result]
print(len(result))
print(" ".join(result))

### FIXED CODE ###

N = int(input())
nums = list(map(int, input().split()))
ans = [0] * N

for i in reversed(range(1,N+1)):
    count = 0
    total = 0
    # 倍数
    for j in range(i, N+1, i):
        count += 1
        total += ans[j-1]
    # 倍数が一つのとき
    if count == 1:
        if nums[i-1] == 0:
            ans[i-1] = 0
        else:
            ans[i-1] = 1
    # 倍数が複数ある
    else:
        # 指定が偶数
        if nums[i-1] == 0:
            if total % 2 != 0:
                ans[i-1] = 1
        else:
            if total % 2 == 0:
                ans[i-1] = 1


# 出力フォーマット処理
result = [i+1 for i in range(len(ans)) if ans[i] == 1]
result = [str(i) for i in result]
print(len(result))
print(" ".join(result))
### BUGGY CODE ###

import itertools
n = int(input())
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
l = float("inf")
for it in itertools.combinations_with_replacement(divisor(n),2):
    if it[0] * it[1] == n:
        l = min(it[0] -1 + it[1] -1,l)
print(l)

### FIXED CODE ###

import itertools
n = int(input())
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
d = divisor(n)
l = float('inf')
for i in range(len(d)):
    l = min(n // d[i] + d[i] - 2,l)
print(l)
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

def lcm(m, n):
    g = gcd(m, n)
    return m * n // g


lcm_num = A[0]
for i in range(1, N):
    lcm_num = lcm(lcm_num, A[i])
#print(lcm_num)

ans = 0
for i in range(N):
    ans += lcm_num // A[i]
    ans %= mod
print(ans)


### FIXED CODE ###

from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))
B = deepcopy(A)
mod = 10**9+7

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**3)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかと、割り尽くした残りを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num, a

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。

ただし素数テーブルは1000までしか用意してないので、それ以上の素数はリストAの中に吐き出させ、
あとでそれをLに組み込む。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        cand, A[i] = div(A[i], p)
        e = max(e, cand)
    L *= pow(p, e, mod)
    L %= mod
for a in set(A):
    L *= a
    L %= mod

"""
あとは答えを求めるのみ。
ただしLをmodで算出しているので、単純にL/A[i]を加算すると答えが狂う。
そこでA[i]^{-1}をmodで求めてLに乗算する。
"""
ans = 0
for i in range(N):
    inv = pow(B[i], mod - 2, mod)
    ans += L * inv
    ans %= mod
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    n = int(input())
    p = list(map(int, input().split()))

    distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
    check = [[1] * n for i in range(n)]
    p = [((i - 1) // n, (i - 1) % n) for i in p]

    def move(x, y, nx, ny):
        if distance[nx][ny] > distance[x][y] + check[x][y]:
            distance[nx][ny] = distance[x][y] + check[x][y]
            d.append((nx, ny))

    ans = 0
    for i, j in p:
        ans += distance[j][i]
        d = deque()
        d.append((j, i))
        check[j][i] = 0
        while len(d):
            x, y = d.popleft()
            if x != 0:
                move(x, y, x - 1, y)
            if x != n - 1:
                move(x, y, x + 1, y)
            if y != 0:
                move(x, y, x, y - 1)
            if y != n - 1:
                move(x, y, x, y + 1)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

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

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans = 0
for a in A:
    flag = True
    da = make_divisors(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    if flag:
        ans += 1

print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

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

#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, P: int, S: str):
    S = list(map(int, list(S)))
    DP = [defaultdict(int) for _ in range(N)]
    for i in range(N):
        c = S[i]
        for key in DP[i-1]:
            DP[i][(key*10+c) % P] += DP[i-1][key]
        DP[i][c % P] += 1
    print(sum([DP[i][0] for i in range(N)]))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*int(S[i])
        a %= P
        U[i] = a
        beki = (beki * 10) % P
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


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

import sys
input = sys.stdin.readline

L,N=map(int,input().split())
X=[0]+[int(input()) for i in range(N)]

def LENG(a,b,start):
    if b==0:
        if start>a:
            return a
        else:
            return L-a

    if a>b:
        a,b=b,a

    return a+L-b


#CANDI=[(N+1)//2,(N+1)//2-1,(N+1)//2+1]
#(i+2)//2*(-1)**i

ANS=0
for start in range(1,N+1):
    if start==0:
        continue

    s=start
    t=(s+(-1)**0)%(N+1)
    ANS1=0


    
    for i in range(2,N+3):
        ANS1+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS1)
        
        s,t=t,(t-i*((-1)**i))%(N+1)

        

        if s==0:
            break
    #print(ANS1)

    s=start
    t=(s-(-1)**0)%(N+1)
    ANS2=0
    for i in range(2,N+3):
        ANS2+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS2)
        s,t=t,(t+i*((-1)**i))%(N+1)

        if s==0:
            break
    #print(ANS2)

    ANS=max(ANS,ANS1,ANS2)

print(ANS)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

L,N=map(int,input().split())
X=[0]+[int(input()) for i in range(N)]

S=[]

for i in range(N):
    S.append(X[i+1]-X[i])
S.append(L-X[-1])

#print(S)

DIS=L-S[-1]
ANS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

S=S[::-1]

DIS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

print(ANS)
### BUGGY CODE ###

cnt = 0
coefficients = [1]
n = 1

_list = []
length = int(input())
for i in range(length):
    try:
        _list.append(int(input()))
    except EOFError:
        continue


for i in range(1,length):
    if i <= n:
        continue
    coefficients.append(i)
    n = i*3 + 1

for c in coefficients[::-1]:
    for i in range(length):
        val = _list[i]
        j = i - c
        while j >= 0 and _list[j] > val:
            _list[j + c] = _list[j]
            j -= c
            cnt += 1
        _list[j+c] = val

print(len(coefficients))
print(*coefficients[::-1])
print(cnt)
print(*_list, sep='\n')

### FIXED CODE ###

cnt = 0
coefficients = [1]
n = 1

_list = []
length = int(input())
for i in range(length):
    try:
        _list.append(int(input()))
    except EOFError:
        continue


for i in range(1,length):
    if i < n:
        continue
    coefficients.append(i)
    n = i*2.25 + 1

for c in coefficients[::-1]:
    for i in range(length):
        val = _list[i]
        j = i - c
        while j >= 0 and _list[j] > val:
            _list[j + c] = _list[j]
            j -= c
            cnt += 1
        _list[j+c] = val

print(len(coefficients))
print(*coefficients[::-1])
print(cnt)
print(*_list, sep='\n')
### BUGGY CODE ###

from heapq import nlargest
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split())) + [0]
aaa_get = aaa.__getitem__
n2 = 1 << n

dp = [[i, -1] for i in range(n2)]
for j in range(n):
    b = 1 << j
    for i in range(n2):
        if (i & b) == 0:
            dp[i | b] = nlargest(2, set(dp[i] + dp[i | b]), key=aaa_get)
ans = list(accumulate(map(lambda x: sum(map(aaa_get, x)), dp[1:]), func=max))
print(*ans)


### FIXED CODE ###

n = int(input())
aaa = list(map(int, input().split()))
n2 = 1 << n
dp = [[a, 0] for a in aaa]

for j in range(n):
    b = 1 << j
    for i in range(n2):
        if not i & b:
            dpi, dpk = dp[i], dp[i | b]
            if dpk[0] < dpi[0]:
                dpk[1] = max(dpk[0], dpi[1])
                dpk[0] = dpi[0]
            elif dpk[1] < dpi[0]:
                dpk[1] = dpi[0]

ans = []
tmp = 0
for a in dp[1:]:
    tmp = max(tmp, a[0] + a[1])
    ans.append(tmp)
print(*ans)