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

from collections import deque
import sys
input=sys.stdin.readline
def main():
    n,m,k=map(int,input().split())
    friend=[[] for i in range(n)]
    block=[[] for i in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        friend[a-1].append(b)
        friend[b-1].append(a)
    for _ in range(k):
        c,d=map(int,input().split())
        block[c-1].append(d)
        block[d-1].append(c)

    def DFS(G,v,p):
        log=[False]*n
        log[v-1]=True
        q=deque()
        q.append((v,p))
        ans=0
        while q:
            V,P=q[-1]
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]==True:continue
                log[new_v-1]=True
                if new_v not in friend[v-1] and new_v not in block[v-1]:ans+=1
                q.append((new_v,V))
                break
            else:
                q.pop()

        return ans

    ans=[]
    for i in range(n):
        ans.append(DFS(friend,i+1,-1))
    print(*ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [-1] * n
        # rank
        self.size = [1] * n

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    out[a-1].append(b-1)
    out[b-1].append(a-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c-1,d-1):
        out[c-1].append(d-1)
        out[d-1].append(c-1)

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')
### BUGGY CODE ###

def main():
  
  import itertools
  import heapq
  import sys
  import functools
  import operator
  import numpy as np
  input = sys.stdin.readline
#-------------
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
#-------------
  b = np.abs(a)
  b = sorted(a,reverse = True)
  b_k = b[k-1] 
  a_new = [a[_] for _ in range(len(a)) if np.abs(a)[_] >= b_k]
  a_new.sort()
  D = [[a_new[i+j-k] for j in range(k)] for i in range(len(a_new))]
  A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
  l_max = max(A)
  waru = 10**9 + 7
  print(l_max % waru)
main()  

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

def run(n, a):
    sum_a = [sum(a[0:i+1]) for i in range(n)]
    ret = sum_a[n - 1]
    for i in range(2, n-1):
        j_l = search_j(sum_a[: i], 0)
        j_r = search_j(sum_a[i:], sum_a[i - 1]) + i
        p = sum_a[j_l]
        q = sum_a[i - 1] - p
        r = sum_a[j_r] - q - p
        s = sum_a[n - 1] - r - q - p
        diff = max(p, q, r, s) - min(p, q, r, s)
        if ret > diff:
            ret = diff
    return ret


def search_j(sum_a, before):
    n = len(sum_a)
    sum_l = sum_a[0] - before
    sum_r = sum_a[n - 1] - sum_a[0]
    diff1 = sum_r - sum_l
    ret = 0
    for i in range(n - 1):
        sum_l = sum_a[i] - before
        sum_r = sum_a[n - 1] - sum_a[i]
        diff2 = sum_r - sum_l
        if diff2 < 0:
            if abs(diff1) < abs(diff2):
                return i - 1
            else:
                return i
        else:
            diff1 = diff2
            ret = i
    return ret


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def run(n, a):
    # sum_a = [sum(a[0:i+1]) for i in range(n)]
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    # 真ん中の切れ込みを順に変更
    # 左の切れ込みの位置はiに対して単調増加
    # 左の切れ込みで真ん中の項を移動するかどうかは、
    # 真ん中の項を除いて、小さい方に入れる
    # ただし単調増加なので、左の切れ込みの左側が
    # 小さいときに真ん中を左の切れ込みの左側に入れる
    # 右も同様に考える
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


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

h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			if need>ans:
				f=0
				break
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)


### FIXED CODE ###

h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			if need>ans:
				f=0
				break
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)
### BUGGY CODE ###

def resolve():
    n = int(input())
    s_list = list(input())
    mod = 10 ** 9 + 7

    if s_list[0] == "W" or s_list[-1] == "W":
        print(0)
        return

    from math import factorial

    l_counter = 0
    res = 1

    for i in range(2 * n):
        s = s_list[i]
        if i % 2 == 0:
            s = "W" if s == "B" else "B"

        if s == "W":
            l_counter += 1
        else:
            res *= l_counter
            l_counter -= 1
            if l_counter < 0:
                print(0)
                return

    if l_counter != 0:
        print(0)
    else:
        print(res * factorial(n) % mod)
        
resolve()

### FIXED CODE ###

import math
n = int(input())
s = [0 if i == "W" else 1 for i in list(input())]
cnt = 0
c = 1
for i in range(n * 2):
    if (s[i] + cnt) % 2 != 0:
        cnt += 1
    else:
        c = (c * (cnt if cnt != 0 else 1)) % (10 ** 9 + 7)
        cnt -= 1
    if cnt < 0:
        print(0)
        exit()
if cnt != 0:
    print(0)
else:
    print((c * math.factorial(n)) % (10 ** 9 + 7))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    #import bisect
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    #print(a)

    bc=[]
    for i in range(m):
        B = list(map(int, input().split()))
        bc.append(B)
    bc.sort(key=lambda x: x[1])
    #print(bc)

    clis=[]
    for i in range(m)[::-1]:
        clis+=[bc[i][1]]*bc[i][0]
    #print(clis)
    ans=0
    le=len(clis)
    for i in range(n):
        #print(clis[i],a[i])
        if i<le and clis[i]>a[i]:
            ans+=clis[i]
        else:
            ans+=a[i]
        #print(ans)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)
#print(bc)
cnt=0
for i in range(n):
    if bc[cnt][0]>0:
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    else:
        cnt+=1
        if cnt==len(bc):
            break
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    #print(cnt,bc,a)
print(sum(a))
### BUGGY CODE ###

A,B,K=map(int,input().split())
for i in range(A,B+1):
    if abs(A-i)<K or abs(B-i)<K:
        print(i)


### FIXED CODE ###

A,B,K=map(int,input().split())
cands = set([])
for i in range(A,min(A+K,B+1)):
    cands.add(i)
for i in range(max(A,B-K+1),B+1):
    cands.add(i)
for cand in sorted(list(cands)):
    print(cand)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.buffer.readline().rstrip()
n = int(input())
dp = [None] * (1 << n)
dp[0] = 1
now = [0]
for _ in range(n):
    A = list(map(int, input().split()))
    next = []
    for i in range(n):
        if not A[i]:
            continue
        for U in now:
            if (U >> i) & 1:
                continue
            nU = U | 1 << i
            if dp[nU] is None:
                dp[nU] = dp[U]
                next.append(nU)
            else:
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    now = next

res = dp[-1]
if res is None:
    res = 0
print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    popcount_to_state = [[] for _ in range(n + 1)]
    for U in range(1 << n):
        popcount_to_state[bin(U).count('1')].append(U)

    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        A = tuple(map(int, input().split()))
        for j in range(n):
            if not A[j]:
                continue
            for U in popcount_to_state[i]:
                if (U >> j) & 1:
                    continue
                nU = U | 1 << j
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    print(dp[-1])
resolve()
### BUGGY CODE ###

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

if b < n:
    n = b

ans_lst = []
for x in range(1, n+1):
    y = x / b
    ans = int(a*y) - a*int(y)
    ans_lst.append(ans)
print(max(ans_lst))


### FIXED CODE ###

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

y = n//b
if y == 0:
    x = n
else:
    x = b - 1
print(int(a*x/b) - a*int(x/b))
### BUGGY CODE ###

import math
from functools import reduce


def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n=int(input())
l1=range(1,n+1)
l2=range(1,n+1)
l3=range(1,n+1)

count=0

for i in l1:
    for j in l2:
        for k in l3:
            count+=gcd_list([i,j,k])

print(count)

### FIXED CODE ###

import math
from functools import reduce


def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n=int(input())
l1=range(1,n+1)
l2=range(1,n+1)
l3=range(1,n+1)

count=0

for i in l1:
    for j in l2:
        te=math.gcd(i,j)
        for k in l3:
            count+=math.gcd(te,k)

print(count)
### BUGGY CODE ###

h,w,m=map(int,input().split())
xnum=[[0,i] for i in range(h)]
ynum=[[0,i] for i in range(w)]
hw=[]
xmax=[]
ymax=[]
for i in range(m):
  s,t=map(int,input().split())
  xnum[s-1][0]+=1
  ynum[t-1][0]+=1
  hw.append([s-1,t-1])
hw.sort()
xnum.sort()
ynum.sort()
xmax.append(xnum[-1][1])
ymax.append(ynum[-1][1])
for i in range(2,len(xnum)+1):
  if xnum[-1*i][0]==xnum[-1][0]:
    xmax.append(xnum[-1*i][1])
  else:
    break
for i in range(2,len(ynum)+1):
  if ynum[-1*i][0]==ynum[-1][0]:
    ymax.append(ynum[-1*i][1])
  else:
    break
flag=True
for i in xmax:
  for j in ymax:
    if [i,j] in hw:
      continue
    else:
      flag=False

if flag:
  ans=xnum[-1][0]+ynum[-1][0]-1
else:
  ans=xnum[-1][0]+ynum[-1][0]
print(ans)

### FIXED CODE ###

import bisect
h,w,m=map(int,input().split())
xnum=[[0,i] for i in range(h)]
ynum=[[0,i] for i in range(w)]
hw=[]
xmax=[]
ymax=[]
for i in range(m):
  s,t=map(int,input().split())
  xnum[s-1][0]+=1
  ynum[t-1][0]+=1
  hw.append([s-1,t-1])
hw.sort()
xnum.sort()
ynum.sort()
xmax.append(xnum[-1][1])
ymax.append(ynum[-1][1])
for i in range(2,len(xnum)+1):
  if xnum[-1*i][0]==xnum[-1][0]:
    xmax.append(xnum[-1*i][1])
  else:
    break
for i in range(2,len(ynum)+1):
  if ynum[-1*i][0]==ynum[-1][0]:
    ymax.append(ynum[-1*i][1])
  else:
    break
flag=True
for i in xmax:
  for j in ymax:
    l=bisect.bisect_left(hw,[i,j])
    r=bisect.bisect_right(hw,[i,j])
    if [i,j] in hw[l:r]:
      continue
    else:
      flag=False
      break

if flag:
  ans=xnum[-1][0]+ynum[-1][0]-1
else:
  ans=xnum[-1][0]+ynum[-1][0]
print(ans)
### BUGGY CODE ###

def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1]:
                for c in range(b,len(S)):
                    if S[c] <= a[i][2]:
                        print(S[c])
                    else:
                        break
                break


### FIXED CODE ###

from bisect import bisect_left, bisect_right, insort_left

q = int(input())
S = []
D = {}
a = []
c = 0
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in D:
            insort_left(S,a[i][1])
            D[a[i][1]] = 1
            c += 1
        else:
            if not D[a[i][1]] == 1:
                D[a[i][1]] = 1
                c += 1
        print(c)
    elif a[i][0] == 1:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                print(1)
            else:
                print(0)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                D[a[i][1]] = 0
                c -= 1
    else:
        L = bisect_left(S,a[i][1])
        R = bisect_right(S,a[i][2])
        for j in range(L,R):
            if D[S[j]] == 1:
                print(S[j])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())))
    N=len(A)
    d={}
    for i in range(2019):
        d[i]=(i*10)%MOD
    dp=[[0]*2019 for _ in range(N+1)]
    ans=0
    for i,x in enumerate(A):
        for j in range(2019):
            dp[i+1][(d[j]+x)%MOD]+=dp[i][j]
        dp[i+1][x]+=1
        ans+=dp[i+1][0]
    print(ans)

    

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())[::-1]))
    N=len(A)
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i]*pow(10,i,MOD))%MOD
    l=[0]*2019
    ans=0
    for i in range(N+1):
        ans+=l[S[i]]
        l[S[i]]+=1
    print(ans)


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

n = int(input())
li = list(map(int, input().split()))
res = 0
m = 10**9 + 7
x = 1
for i in range(0, len(li)-1):
    for j in range(i+1, len(li)):
            res += ((li[i]%m)*(li[j]%m))%m
    res %= m
print(res)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
res = 0
sum1 = sum(li)
sum2 = 0
m = 10**9 + 7
for i in range(0, len(li)-1):
    sum2 += li[i]
    res = (res + li[i]*(sum1-sum2))%m
print(res)
### BUGGY CODE ###

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

for i in range(1,N+1):
  AA.append(A.index(i)+1)
L=[str(a) for a in AA]
L=" ".join(L)
print(L)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
AA = [0 for i in range(N)]
 
for i in range(N):
  AA[A[i]-1] = i + 1
  
L=[str(a) for a in AA]
L=" ".join(L)
print(L)
### BUGGY CODE ###

N,M = map(int,input().split())
ab = []
dp = [0 for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    ab.append([a-1,b-1])
ab.sort(key = lambda ab:ab[1])
count = 0
while ab:
    a,b = ab.pop(0)
    for i in range(len(ab)-1,-1,-1):
        if ab[i][0] < b:
            ab.remove(ab[i])
    count += 1
print(count)

### FIXED CODE ###

N,M = map(int,input().split())
ab = []
for i in range(M):
    ab.append(list(map(int,input().split())))
ab.sort(key = lambda ab:ab[1])
count = 0
now = 0
for a,b in ab:
    if a >= now:
        count += 1
        now = b
print(count)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

cnt = 0
for i, a in enu(A):
    if i+a+1<=N-1:
        for j, b in enu(A[i+a+1:]):
            if abs(j+a+1) == a + b:
                cnt += 1
                # print(i, i+a+1+j)
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

cnt = 0
d = defaultdict(int)
for i, a in enu(A):
    l = (i+1) + a
    r = (i+1) - a
    cnt += d[r]
    d[l] += 1
print(cnt)
### BUGGY CODE ###

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

mod = 10**9+7
ans = 0
for i in range(N-1):
    ans += A[i] * sum(A[i+1:]) % mod
    ans = ans%mod
    
print(ans)

### FIXED CODE ###


from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
B = list(accumulate(A))
mod = 10**9+7
ans = 0
sumA = sum(A)

for i in range(N-1):
    ans += A[i] * (sumA-B[i]) % mod
    ans = ans%mod
    
print(ans)
### BUGGY CODE ###


n = int(input())
x = list(map(int, input().split()))
a = []
for i, xi in enumerate(x):
    a.append([i, xi])

for i in range(n):
    memo = a.pop(i)
    b = sorted(a, key=lambda t: t[1])
    print(b[int(n/2) - 1][1])
    b.append(memo)
    a = sorted(b, key=lambda t: t[0])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
b = sorted(x)
m_left = b[int(n//2) -1]
m_right = b[int(n//2)]

for i in range(n):
    if x[i] <= m_left:
        print(m_right)
    elif x[i] >= m_right:
        print(m_left)
### BUGGY CODE ###

# EDP F-LCS
def main():
    s = input()
    t = input()

    dp = [[[0, ""] for j in range(len(t)+1)] for i in range(len(s)+1)]

    for i in range(0, len(s)):
        for j in range(0, len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = [dp[i][j][0]+1, dp[i][j][1]+s[i]]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    print(dp[len(s)][len(t)][1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# EDP F-LCS
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""


def main():
    S = input()
    T = input()
    LS = len(S)
    LT = len(T)
    dp = [[0 for j in range(LT+1)] for i in range(LS+1)]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                if dp[i+1][j] >= dp[i][j+1]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    def rec(i, j):
        if i == 0 or j == 0:
            return

        if S[i-1] == T[j-1]:
            global ans
            ans += S[i-1]
            rec(i-1, j-1)
        elif dp[i-1][j] > dp[i][j-1]:
            rec(i-1, j)
        else:
            rec(i, j-1)

    rec(LS, LT)
    print(ans[::-1])


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

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

p = [((1+int(i))*int(i)/2)/int(i) for i in input().split()]

res = 0
for j in range(N-K+1):
  ans = 0
  for i in range(K):
    ans += p[j+i]
  res = max(res,ans)
  
print(res)  

### FIXED CODE ###

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

p = [((1+int(i))*int(i)/2)/int(i) for i in input().split()]

m = check = sum(p[0:K])
for i in range(K,N):
  check = check+p[i]-p[i-K]
  m = max(m,check)
print(m)
### BUGGY CODE ###

N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)

### FIXED CODE ###

N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
flag=False
while len(check)>0:
    if flag:
        break
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
            break
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)