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

import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    d = int(read())
    c = [int(i) for i in read().split()]
    s = [[int(i) for i in read().split()] for _ in range(d)]
    t = [int(read()) - 1 for _ in range(d)]
    m = int(read())
    query = [[int(i) - 1 for i in read().split()] for _ in range(m)]
    score = [0] * d
    last = [[0] * 26 for _ in range(d)]
    for i in range(d):
        score[i] = s[i][t[i]]
        if i > 0:
            last[i] = last[i - 1].copy()
        last[i][t[i]] = i + 1
        for j in range(26):
            score[i] -= c[j] * (i + 1 - last[i][j])
    for di, qi in query:
        if di == 0:
            last[di][t[di]] = 0
        else:
            last[di][t[di]] = last[di - 1][t[di]]
        last[di][qi] = di + 1
        t[di] = qi
        for i in range(di, d):
            score[i] = s[i][t[i]]
            if i > 0:
                last[i] = last[i - 1].copy()
            last[i][t[i]] = i + 1
            for j in range(26):
                score[i] -= c[j] * (i + 1 - last[i][j])
        print(sum(score))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    d = int(read())
    c = [int(i) for i in read().split()]
    s = [[int(i) for i in read().split()] for _ in range(d)]
    t = [int(read()) - 1 for _ in range(d)]
    m = int(read())
    query = [[int(i) - 1 for i in read().split()] for _ in range(m)]
    score = 0
    last = [[0] * 26 for _ in range(d)]
    for i in range(d):
        score += s[i][t[i]]
        if i > 0:
            last[i] = last[i - 1].copy()
        last[i][t[i]] = i + 1
        for j in range(26):
            score -= c[j] * (i + 1 - last[i][j])
    for di, qi in query:
        hi = t[di]
        t[di] = qi
        score -= s[di][hi]
        score += s[di][qi]
        if di == 0:
            last[di][hi] = 0
        else:
            last[di][hi] = last[di - 1][hi]
        score -= c[hi] * (di + 1 - last[di][hi])
        score += c[qi] * (di + 1 - last[di][qi])
        last[di][qi] = di + 1
        for i in range(di + 1, d):
            score += c[hi] * (i + 1 - last[i][hi])
            if t[i] != hi:
                last[i][hi] = last[i - 1][hi]
                score -= c[hi] * (i + 1 - last[i][hi])
            else:
                break
        for i in range(di + 1, d):
            score += c[qi] * (i + 1 - last[i][qi])
            if t[i] != qi:
                last[i][qi] = last[i - 1][qi]
                score -= c[qi] * (i + 1 - last[i][qi])
            else:
                break
        print(score)


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

import itertools
import functools

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def gcd(nums):
    return functools.reduce(euclid, nums)

k = int(input())
ans = 0
for v in itertools.combinations_with_replacement([i+1 for i in range(k)], 3):
    if len(set(v)) == 1:
        ans = ans + gcd(v) * 1
    elif len(set(v)) == 2:
        ans = ans + gcd(v) * 3
    elif len(set(v)) == 3 :
        ans = ans + gcd(v) * 6
print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

a,b,n=map(int,input().split())
m=0
d=1
if n>=10**6:
    d=2
for i in range(1,n+1,d):
    c=a*i//b-a*(i//b)
    if c>=m:
        m=c
    # print((a*i)//b,a*(i//b),a*i//b-a*(i//b))
print(m)

### FIXED CODE ###

a,b,n=map(int,input().split())
if b-1<=n:
    i=b-1
else:
    i=n
print(a*i//b-a*(i//b))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 30
ans = 0
from bisect import bisect_left as bl, bisect_right as br
def sub(k):
    tmp = pow(2, k)
    tmp2 = tmp*2
    bb = [item%(tmp2) for item in b]
    bb.sort()
    ans = 0
    for item in a:
        aa = item%(tmp2)
        if aa<=tmp:
            num = br(bb, tmp2-1-aa) - bl(bb, tmp-aa)
        else:
            num = br(bb, tmp2-1-aa) + (n - bl(bb, tmp*3-aa))
        ans += num
        ans %= 2
    return ans%2
    
for k in range(l):
    # i桁目を求める
    if sub(k):
        ans += pow(2, k)
print(ans)


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

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

bombw = [0]*w
bombh = [0]*h
bomb = []
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    bomb.append([str(hi-1)+"-"+str(wi-1)])
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if [str(i)+"-"+str(j)] not in bomb:
            print(ans)
            exit()
print(ans-1)

### FIXED CODE ###

from collections import defaultdict

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

bombw = [0]*w
bombh = [0]*h
dd = defaultdict(bool)
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    dd[str(hi-1)+"-"+str(wi-1)] = True
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if not dd[str(i)+"-"+str(j)]:
            print(ans)
            exit()
print(ans-1)
### BUGGY CODE ###

n = int(input())
x = [input() for i in range(n)]
i = 0
count, yo, list_yo = [], [], []

while not(x == []):
  a = x.count(x[i])
  count.append(a)
  yo.append(x[i])
  x.remove(x[i])
  if len(x) < max(count):
    break
  
[list_yo.append(yo[k]) for k, c in enumerate(count) if c == max(count)]
  
list_yo.sort()

[print(list_yo[i]) for i in range(len(list_yo))]
  



### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
s = collections.Counter(s)
m = 0
ans = []

for i in s.values():
  m = max(m,i)

for k, j in s.items():
  if j == m:
    ans.append(k)
ans.sort()

for i in range(len(ans)):
  print(ans[i])
#print(*ans, sep = "\n")
### BUGGY CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A.count(A[i])
    print(Com-y+1)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A_C[A[i]]
    print(Com-y+1)
### BUGGY CODE ###

import math

k = int(input())

res = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            res += math.gcd(math.gcd(i, j), l)

print(res)

### FIXED CODE ###

import math

k = int(input())

res = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            res += math.gcd(x, l)

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

N, K = map(int, input().split())
H = [int(N) for N in input().split()]
for i in range(0, K):
    max_index = H.index(max(H))
    H[max_index] = 0
print(sum(int(i) for i in H))

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(N) for N in input().split()]
H.sort(reverse=True)
if N <= K:
    print(0)
else:
    for i in range(0, K):
        H[i] = 0
    print(sum(H))
### BUGGY CODE ###

n,m = map(int, input().split())
l = list(map(int, input().split()))
d = [0] * (n+1)

for i in range(1,n+1):
    if i in l:
        d[i] = 1
    else:
        min = 50000
        for j in range(i+1):
            if d[i-j]+d[j] < min and d[i-j]+d[j]>0:
                min = d[i-j] + d[j]
        d[i] = min

print(d[n])

### FIXED CODE ###

n = int(input().split()[0])
c = list(map(int,input().split()))
dp = list(range(n+1))

for i in range(2,n+1):
    for j in c:
        if j <= i and dp[i-j] + 1 < dp[i]:
            dp[i] = dp[i-j]+1

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

from collections import deque
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
cnt = h*w
t = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      q.append((i,j))
      a[i][j] = 0
      cnt -= 1
while cnt:
  y,x = q.popleft()
  for dx,dy in d:
    if 0 <= x+dx < w and 0 <= y+dy < h and a[y+dy][x+dx] == ".":
      a[y+dy][x+dx] = a[y][x] + 1
      cnt -= 1
      q.append((y+dy,x+dx)) 
for i in range(h):
  m = max(a[i])
  t = max(t,m)
print(t)

### FIXED CODE ###

from collections import deque
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
cnt = h*w
t = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      q.append((i,j))
      a[i][j] = 0
      cnt -= 1
while cnt:
  y,x = q.popleft()
  for dx,dy in d:
    if 0 <= x+dx < w and 0 <= y+dy < h and a[y+dy][x+dx] == ".":
      a[y+dy][x+dx] = a[y][x] + 1
      cnt -= 1
      q.append((y+dy,x+dx)) 
for i in range(h):
  m = max(a[i])
  t = max(t,m)
print(t)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
bin_a = []
for i in a:
    bin_a.append(bin(i)[2::])
maxlen = 0
for i, j in enumerate(bin_a):
    maxlen = max(maxlen, len(j))

for i, j in enumerate(bin_a):
    while len(bin_a[i]) < maxlen:
        bin_a[i] = "0" + bin_a[i]
bin_a.sort()
ans = 0
mod = 10**9+7
for i in range(maxlen):
    zerocnt = 0
    onecnt = 0
    for j in range(len(bin_a)):
        if bin_a[j][i] == "0":
            zerocnt += 1
        else:
            onecnt += 1
    ans += zerocnt * onecnt * pow(2, (maxlen-i-1), mod)
    ans %= mod
ans %= mod
print(ans)

### FIXED CODE ###

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

for i in a:
    j = 0
    while i > 0:
        if len(onecnts) - 1 < j:
            onecnts.append(0)
        if i % 2 != 0:
            onecnts[j] += 1
        j += 1
        i >>= 1

ans = 0
mod = 10**9+7

for i, onecnt in enumerate(onecnts):
    ans += onecnt * (n-onecnt) * (2**i)
    ans %= mod
print(ans)
### BUGGY CODE ###

import bisect
import itertools
N = int(input())
S = input()

cache = {}
for i in range(N):
    if S[i] in cache:
        cache[S[i]].append(i)
    else:
        cache[S[i]] = [i]

result = 0
route = []
for k,v in cache.items():
    route.append(len(v))
for i in range(1,28):
    xxx = result
    #i種類取り出して掛け算した値を足し込む
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))
            
        
            

### FIXED CODE ###

import collections
N = int(input())
S = input()

result = 1
route = [x+1 for _,x in collections.Counter(S).items()]
for x in route:
    result = result*x
print((result-1)%(10**9+7))
### BUGGY CODE ###

n,k,q = list(map(int, input().strip().split()))
point=[k-q]*n
a=[0]*q
for i in range(q):
    a[i]=int(input())
for i in range(n):
    point[i]+=a.count(i+1)
for i in range(n):
    if point[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())
b = [k - q] * n

for i in range(q):
    ai = int(input())
    b[ai - 1] += 1

for j in range(n):
    if b[j] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

# print(N)
# print(L)

# print(range(N))
# print(range(1, N))
# print(range(2, N))

count = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if not(L[i] < L[j] + L[k]):
                continue
            if not(L[j] < L[i] + L[k]):
                continue
            if not(L[k] < L[i] + L[j]):
                continue
            # print('{}, {}, {}'.format(i, j, k))
            count += 1
            
print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import bisect

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

# print(N)
# print(L)

L_sorted = sorted(L)
# print(L_sorted)

count = 0
for i in range(0, N - 2):
    # print(i)
    for j in range(i + 1, N - 1):
        a = L_sorted[i]
        b = L_sorted[j]
        # print(j)
        # for k in range(j + 1, N):
        #     a = L_sorted[i]
        #     b = L_sorted[j]
        #     c = L_sorted[k]
            
        #     if a + b <= c:
        #         break
        #     # print('{}, {}, {}'.format(a, b, c))
        #     count += 1
        
        # print('{}, {},'.format(a, b))
        index = bisect.bisect_left(L_sorted, a + b, i + 1, N)
        # print(index)
        # print((index - 1) - j)
        count += ((index - 1) - j)
        
print(count)
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(input())
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0
hw = set(range(h*w))
for i in hw:
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < h) and (0 <= dw + j < w) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    if not d:
        break
ans = max([max(e) for e in memo])
print(ans)

### FIXED CODE ###

from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)
### BUGGY CODE ###

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
#print(n,k,a)
mydict={}
mylist=[]
for i in a:
    if i not in mydict:
        mydict[i]=a.count(i)
z=len(mydict)-k

for i in mydict.values():
  mylist.append(i)

#print(mydict)
if z<=0:
    print(0)
else:
    ans=0
    for i in range(z):
        tmp=min(mylist)
        ans+=tmp
        mylist.remove(tmp)
    print(ans)



### FIXED CODE ###

import collections

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]

mydata=collections.Counter(a)
mylist=list(mydata.values())
mylist.sort(reverse=True)
#print(mylist)

if len(mylist)<k:
  print(0)
else:
  val=sum(mylist[:k])
  print(n-val)
### BUGGY CODE ###


import itertools,bisect
N =int(input())
L = list(map(int,input().split()))
L.sort()

def j(a,b,c):
  if a<b+c and c<b+a and b<a+c:
    return True
  else:
    return False

cnt = 0
l = list(itertools.combinations(range(N),2))
for i1,i2 in l:
  a,b = L[i1],L[i2]
  if a == b:
    ib = bisect.bisect_right(L, b)
    ic = bisect.bisect_right(L, a+b)
  else:
    ib = bisect.bisect_left(L, b)
    ic = bisect.bisect_left(L, a+b)
  if ic - ib >=1:
    cnt += ic - ib -1
print(cnt)

### FIXED CODE ###

import bisect
N =int(input())
L = sorted(list(map(int,input().split())))

cnt = 0

for i in range(N):
  for j in range(i+1,N):
    cnt += bisect.bisect_left(L,L[i]+L[j]) - (j+1)
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
K=[]

DP=[0]*1001
for i in P:
    if DP[i]==0:
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

ans=0
for i in range(n-k+1):
    ans=max(ans,sum(K[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
K=[]

DP=[0]*1001
for i in P:
    if DP[i]==0:
        DP[i]=(i*(i+1)//2)/i
    K.append(DP[i])

K.append(0)
ans=sum(K[:k])
score=sum(K[:k])
for i in range(n-k+1):
    score -=K[i]
    score +=K[i+k]
    ans=max(ans,score)
print(ans)
### BUGGY CODE ###

N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    # cnt = min(K, i-1)
    if K >= i+1:
        cnt = i
    else:
        cnt = K
    for j in range(cnt):
        compare.append(dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = min(compare)

print(dp[-1])


### FIXED CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

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

import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

# MAX = 1200000    # 80*80*80=512000

H, W = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
B = [[int(x) for x in input().split()] for _ in range(H)]
C = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(C[0][0])
for i in range(H):
    for j in range(W):
        if i:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+C[i][j]))
                dp[i][j].add(abs(k-C[i][j]))
        if j:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+C[i][j]))
                dp[i][j].add(abs(k-C[i][j]))
print(min(dp[H-1][W-1]))


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
center = 80 * (H+W)
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

dp = [[0] * W for i in range(H)]
dp[0][0] = (1 << (center + C[0][0])) | (1 >> (center - C[0][0]))

for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]

ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))

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

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import sys
inf = 10**9+7
mod = 10**9+7

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

### FIXED CODE ###

# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import sys
inf = 10**9+7
mod = 10**9+7
V = 10**5
n,W = map(int, input().split())
dp = [[inf for j in range(V+1)] for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    dp[i+1][0] = 0
    w,v = map(int, input().split())
    for j in range(V):
        if j+1-v >= 0:
            dp[i+1][j+1] = min(dp[i][j+1-v]+w, dp[i][j+1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], w)
for j in range(V+1):
    if dp[n][j] > W:
        print(j-1)
        sys.exit()
        break
print(V)
### BUGGY CODE ###

#import numpy as np
import itertools
N = int(input().strip())
A = list(map(int,input().strip().split(' ')))
#Z = np.zeros((N+1,N))
Z = [[0]*int(N+1) for i in range(N) ]
#Z[0,:] = np.array(A)
result = 0

for k in range(N):
        Z[0][k] = A[k]
        if A[k] == 0:
                result = result+1

for i,j in itertools.combinations_with_replacement(range(1,N),2):
        tmp = Z[i-1][j-1]+Z[0][j]
        if tmp ==0:
                result = result+1
        Z[i][j] = tmp
print(result)

### FIXED CODE ###

import collections
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
C = [0 for j in range(N)]
C[0] = A[0]
for i in range(1,N):
        C[i] = C[i-1] + A[i]
C.sort()

CC = collections.Counter(C)

result = CC[0]
for k in CC.values():
    if k > 1:
        result = result + k*(k-1)/2

print(int(result))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
dp = [INF] * (1<<N)
dp[0] = 0

for i in range(M):
    a, b = MAP()
    c = LIST()
    d = 0
    # 1を立てる
    for x in c:
        # 1が存在するなら，dの一番最後，右から0番目，0シフト目に必要
        d += 1<<(x-1)
    for j in range(1<<N): # 2 ** N 列見る
#         # テーブルは一列ずつ見て更新しよう
        tmp = j|d
        dp[tmp] = min(dp[tmp], dp[j] + a)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])



### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def main():
    N, M = MAP()
    dp = [INF] * (1<<N)
    dp[0] = 0

    for i in range(M):
        a, b = MAP()
        c = LIST()
        d = 0
        # 1を立てる
        for x in c:
            # 1が存在するなら，dの一番最後，右から0番目，0シフト目に必要
            d += 1<<(x-1)
        for j in range(1<<N): # 2 ** N 列見る
    #         # テーブルは一列ずつ見て更新しよう
            tmp = j|d
            dp[tmp] = min(dp[tmp], dp[j] + a)
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])

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

# 1.input
n = int(input())
x = list(map(int, input().split()))

# 2.delete i-th component
for i in range(n):
    xi_res = x[:i] + x[i+1:]

    # 3.print median
    half = int(n/2)
    print(sorted(xi_res)[half-1])

### FIXED CODE ###

# 1.input
n = int(input())
x = list(map(int, input().split()))

# 2.check half- and half+
x_copy = sorted(x, reverse=False)
half = int(n/2)
half_minus = x_copy[half-1]
half_plus = x_copy[half]


# 3. judge
#    if removed number is smaller than or equal to half- -> half+
#    else -> half-
for xi in x:
    if xi <= half_minus:
        print(half_plus)
    else:
        print(half_minus)