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

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []

# cnt_sum = 0
# min_num = BC[0][1]
# for i in range(M):
#     cnt = BC[i][0]
#     for j in range(N):
#         if cnt_sum <= N:
#             L.append(BC[i][1])
#             cnt_sum += 1
#             cnt -= 1
#             if BC[i][1] < min_num:
#                 min_num = BC[i][1]
#         else:
#             if BC[i][1] < min_num:
#                 break
#             if L[j] < BC[i][1]:
#                 L[j] = BC[i][1]
#                 cnt -= 1
#         if cnt <= 0:
#             break
len_L = 0
for i in range(M):
    # for j in range(BC[i][0]):
    #     L.append(BC[i][1])
    L.extend([BC[i][1] for j in range(BC[i][0])])
    len_L += BC[i][0]
L.sort(reverse=True)
A.sort()
# ans = sum(A)
ans = 0
flag = True
for k in range(N):
    if k <= len_L-1:
        if flag and L[k] > A[k]:
            ans += L[k]
        else:
            flag = False
            ans += A[k]
    else:
        ans += A[k]
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

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

import numpy as np
from itertools import permutations
N = int(input())


for n in range(1, N+1):
    count = 0
    for i in range(1, 58):
        for j in range(i, 100):
            t = (i+j)**2 - 4 * (i * j + i**2 + j**2 - n)
            if t < 0:
                continue
            k = 0.5 * (-(i + j) + np.sqrt(t))
            if k < j:
                break
            if i**2 + j**2 + k**2 + i * j + j * k + i * k > n:
                break
            if int(k) == k:
                count += len(set(permutations([i, j, int(k)])))
    print(count)



### FIXED CODE ###

import numpy as np
from itertools import permutations
N = int(input())

counter = np.zeros(N, dtype=int)

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            res = x**2 + y**2 + z**2 + x * y + x * z + y * z
            if res <= N:  
                counter[res - 1] += 1

for c in counter:
    print(c)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.append((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()


### FIXED CODE ###

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


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()
### BUGGY CODE ###

X,Y,Z,K = (int(i) for i in input().split())  
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans = []
for a in A:
	for b in B:
		for c in C:
			ans.append(a+b+c)

ans.sort(reverse=True)
for i in range(K):
	print(ans[i])

### FIXED CODE ###

X,Y,Z,K = (int(i) for i in input().split())  
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans = []
b=0
c=0
for a in range(len(A)):
	for b in range(len(B)):
		for c in range(len(C)):
			if (a+1)*(b+1)*(c+1)<=K:
				ans.append(A[a]+B[b]+C[c])
			else:
				break

ans.sort(reverse=True)
for i in range(K):
	print(ans[i])
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
m=1/k
ans=0
l=[]
for i in range(k):
  tmp=0
  for j in range(1,p[i]+1):
    tmp+=1/p[i]*j
  l.append(tmp)
ans=sum(l)
s=ans
for i in range(k,n):
  tmp=0
  for j in range(1,p[i]+1):
    tmp+=1/p[i]*j
  l.append(tmp)
  s+=tmp
  s-=l[i-k]
  if ans<=s:
    ans=s
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[0]*(n+1)
l[1]=(p[0]+1)/2
for i in range(2,n+1):
  l[i]=l[i-1]+(p[i-1]+1)/2
ans=0
for i in range(n-k+1):
  if ans<l[i+k]-l[i]:
    ans=l[i+k]-l[i]
print(ans)
### BUGGY CODE ###

N , K = map(int,input().split())
hn = list(map(int,input().split()))
dp = [10 ** 10] * (N)
dp[0] = 0
#dp[1] = abs(hn[0]-hn[1])
for i in range(N):
    for j in range(1,K+1):
        if i + j < N:
            dp[i+j] = min(dp[i] + abs(hn[i+j]-hn[i]) ,dp[i+j])

print(dp[-1])

### FIXED CODE ###

N, K  = map(int, input().split())
hn = list(map(int,input().split() ) )
# カエルがi番目からi+j番目に到着するには
# dp[i+j] = min(dp[i]+abs(hn[i+j] - hn[i]) + , dp[i+j])
dp = [10**10] * (N)
dp[0] = 0
dp[1] = abs(hn[0]-hn[1])
for i in range(N):
    for j in range(1,K+1):
        if i + j < N:
            dp[i+j] = min(dp[i] + abs(hn[i+j] - hn[i]), dp[i+j])

print(dp[N-1])
### 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())
if B-A>=2*K:
    for i in range(A,A+K-1+1):
        print(i)
    for i in range(B-K+1,B+1):
        print(i)
    exit()
else:
    for i in range(A,B+1):
        print(i)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
res=0
for d in range(60,-2,-1):
    if(d!=-1 and K&(1<<d)==0):
        continue
    tmp=0
    for e in range(60,-1,-1):
        mask=1<<e
        num=0
        for i in range(N):
            if(mask&A[i]):
                num+=1
        #numというのはd桁目の1が立ってる数
        if(e>d):
            #このときは
            if(K&mask):
                tmp+=mask*(N-num)
            else:
                tmp+=mask*num
        elif(e==d):
            tmp+=mask*num      
        else:
            tmp+=mask*max(num,N-num)
    res=max(res,tmp)
print(res)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
res=0
for d in range(40,-2,-1):
    if(d!=-1 and K&(1<<d)==0):
        continue
    tmp=0
    for e in range(40,-1,-1):
        mask=1<<e
        num=0
        for i in range(N):
            if(mask&A[i]):
                num+=1
        #numというのはd桁目の1が立ってる数
        #e>dというのはxとkは上からみてd桁目で0と1が変わるってことでfor文まわしてるから
        #つまりe>dというのはd桁目より大きい所を見てる感じ、だからその部分はkとxは同じ数字にになってるよね、そう考えると
        if(e>d):
            #ここではKのe桁目が1のときnumというのは1がたってる数だからそれらがeが1で反転しちゃうから足し合わせるのは0になってる法(つまりN-num)
            if(K&mask):
                tmp+=mask*(N-num)
            #上と全く逆
            else:
                tmp+=mask*num
        #e==dというのはちょうどKとXの桁が変わるところK>=XだからK=1,X=0になるよね、だから足すのはnumの方
        elif(e==d):
            tmp+=mask*num      
        #e<dではxは01好きな方を使っていいよね、、ということは足し合わせるのはnumでもN-numでもどっちでもOK!
        else:
            tmp+=mask*max(num,N-num)
    #この処理をdが大きいところから順にやってあげて一番大きくなったのが答え!
    res=max(res,tmp)
print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(len(A)):
    ans *= A[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    if ans <= 10**18:
        ans *= A[i]
    else:
        ans = -1
        break
if ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
flg = True
while(flg):
    for a in range(0,N//4 + 1):
        for b in range(0,N//7 + 1):
            total = 4*a + 7*b
            if total == N:
                flg = False
                break
if(flg):
    print('No')
else:
    print('Yes')

### FIXED CODE ###

N = int(input())
res = 0
for a in range (0,N//4 + 1):
    for b in range(0,N//7 + 1):
        total = 4 * a + 7 * b
        if total == N:
            res += 1
if res > 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
h = input().split()
h_lis = []
for i in range(n):
    h_lis.append(int(h[i]))


cnt_lis = []
for i in range(n):
    tmp_cnt = -1
    last = float('inf')
    for j in range(i, n):
#         print(h_lis[i], h_lis[j])
        if h_lis[j] <= last:
            tmp_cnt += 1
            last = h_lis[j]
        else:
            cnt_lis.append(tmp_cnt)
            break
        cnt_lis.append(tmp_cnt)
print(max(cnt_lis))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
last = 0
cnt_lis = []
for i in range(n):
    if h[i] <= last:
        cnt_lis.append(cnt_lis[i - 1] + 1)
    else:
        cnt_lis.append(0)
    last = h[i]
print(max(cnt_lis))
### BUGGY CODE ###

#B問題
import bisect

N = int(input())
S = list(str(input()))
mod = 998244353
N_factorial = 1
for i in range(N):
    N_factorial*=(i+1)
    N_factorial%=mod

r,g,b = [],[],[]
for i in range(3*N):
    if S[i] == "R":
        r.append(i)
    if S[i] == "G":
        g.append(i)
    if S[i] == "B":
        b.append(i)
        
m,M = [],[]
for i in range(N):
    m.append(min(r[i],g[i],b[i]))
    M.append(max(r[i],g[i],b[i]))
    
A,B,C = [],[],[]
    
for i in range(N):
    A.append(m[i])
    C.append(M[i])
    
for i in range(3*N):
    if i not in A and i not in C:
        B.append(i)
        
count = 1
for i,B_ind in enumerate(B):
    x = bisect.bisect_left(A,B_ind)-i
    y = i+1-bisect.bisect_right(C,B_ind)
    count*=(x*y)%mod
        
ans = (count*N_factorial)%mod
print(ans)

### FIXED CODE ###

#B問題
import bisect

N = int(input())
S = list(str(input()))
mod = 998244353
N_factorial = 1
for i in range(N):
    N_factorial*=(i+1)
    N_factorial%=mod

r,g,b = [],[],[]
for i,s in enumerate(S):
    if s == "R":
        r.append(i)
    if s == "G":
        g.append(i)
    if s == "B":
        b.append(i)
        
A,B,C = [],[],[]
for i in range(N):
    rgb = [r[i],g[i],b[i]]
    rgb.sort()
    A.append(rgb[0])
    B.append(rgb[1])
    C.append(rgb[2])

ans = N_factorial
for i,B_ind in enumerate(B):
    x = bisect.bisect_left(A,B_ind)-i
    y = i+1-bisect.bisect_left(C,B_ind)
    ans*=(x*y)
    ans%=mod

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

import sys
from itertools import accumulate

import numpy as np

h, w = list(map(int, input().split()))
field = [[int(c == '.') for c in line.rstrip()] for line in sys.stdin]
func = lambda x, a: (x + a) * a
ans = np.zeros([h, w], dtype=np.int)

for i, row in enumerate(field):
    ans[i] += list(accumulate(row, func=func))
    ans[i] += list(reversed(list(accumulate(reversed(row), func=func))))

ans = ans.T
field = np.array(field).T.tolist()
for i, row in enumerate(field):
    ans[i] += list(accumulate(row, func=func))
    ans[i] += list(reversed(list(accumulate(reversed(row), func=func))))

print(ans.max() - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

S=input()
T=input()
setT=set(T)
flg=True
for t in setT:
    if not t in S:
        flg=False
if flg:
    i=0
    j=0
    while 1:
        if S[i%len(S)]==T[j]:
            j+=1
        if j==len(T):
            break
        i+=1
    print(i+1)
else:
    print(-1)

### FIXED CODE ###

from bisect import bisect_right as br
S=input()
T=input()

def s2n(s):
    return ord(s)-97

ALF=[[] for _ in [0]*26]
for i in range(len(S)):
    ALF[s2n(S[i])].append(i)

ALF_T=[0]*26
seqT=[]
res=0
for t in T:
    i=s2n(t)
    if ALF[i]:
        if seqT:
            a=seqT[-1]
        else:
            a=-1
        j=br(ALF[i],a)
        seqT.append(ALF[i][j%len(ALF[i])])
    else:
        res=-1
if res>=0:
    tmp=[]
    m=-1
    for n in seqT:
        if m<n:
            tmp.append(n)
        else:
            res+=1
            tmp=[n]
        m=n
    res=res*len(S)+tmp[-1]+1
print(res)
### BUGGY CODE ###

import sys
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def bfs():
  que=deque([])
  que.append(0)
  while que:
    p=que.popleft()
    for i in root[p]:
       if(d[i]==0):
         ans_val[i]=ans_val[p]+N_val[i]
         que.append(i)
         d[i]=1
      
def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
#dfs(0,d,N_val[0])
bfs()
print(*ans_val)

### FIXED CODE ###

import sys
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def bfs():
  que=deque([])
  que.append(0)
  while que:
    p=que.popleft()
    for i in root[p]:
       if(d[i]==0):
         ans_val[i]=ans_val[p]+N_val[i]
         que.append(i)
         d[i]=1
      
def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
#dfs(0,d,N_val[0])
bfs()
print(*ans_val)
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7
u=1
d=1
ans=0

for i in range(1, n+1):
  u *= n+1-i
  d *= i
  if i != a and i != b:
    ans += u//d
    ans %= mod
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7
def c(x):
  out = 1
  for i in range(min(x, n-x)):
    out *= n-i
    out *= pow(i+1, mod-2, mod)
    out %= mod
  return out
ans = pow(2, n, mod) -1 -c(a)-c(b)
ans %= mod
print(ans)
### BUGGY CODE ###

n=int(input())
print(0)
A={}
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.append({0,0})
else:
  A.append({0,1})
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.append({n-1,0})
else:
  A.append({n-1,1})
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A.append({mid,0})
  else:
    A.append({mid,1})
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

### FIXED CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid
### BUGGY CODE ###

R = []
G = []
B = []
sum = 0

N = int(input())

S = input()

for i in range(len(S)):
   if S[i] == "R":
      R.append(i)
   elif S[i] == "G":
      G.append(i)
   else:
      B.append(i)

for i in R:
   for j in G:
      for k in B:
         l = [i,j,k]
         l.sort()
         if l[1]-l[0] != l[2]-l[1]:
            sum += 1
print(sum)




### FIXED CODE ###

N = int(input())
S = input()

sum = S.count("R")*S.count("G")*S.count("B")

for i in range(N):
   for j in range(i+1,N-1):
      k = 2*j-i
      if(k<N):
         if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            sum-=1
print(sum)
### BUGGY CODE ###

def solve():
    n = int(input())
    i = n
    while True:
        if i % 2 == 0 and i % n == 0:
            print(i)
            exit()


if __name__ == "__main__":
    solve()


### FIXED CODE ###

def solve():
    n = int(input())
    i = n
    while True:
        if i % 2 == 0:
            print(i)
            exit()
        i += n



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

N = int(input())
A = list(map(int,input().split()))
B = [A.index(i)+1 for i in range(1,N+1)]
print(*B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [[i+1,A[i]] for i in range(N)]
B.sort(key=lambda x: x[1])
for j in range(N):
  if j == N-1:
    print(B[j][0])
  else:
    print(B[j][0] ,end=" ")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

a = []

for i in range(N):
    a.append(int(input()))

ans = 0
b_now = 1
loop = []

for i in range(1, N + 1):
    loop.append(b_now)
    b_now = a[b_now - 1]
    ans += 1
    if b_now == 2:
        print(ans)
        exit()
    elif b_now in loop:
        print(-1)
        exit()

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

a = []

for i in range(N):
    a.append(int(input()))

ans = 0
b_now = 1
loop = []

for i in range(N):
    b_now = a[b_now - 1]
    ans += 1
    if b_now == 2:
        print(ans)
        exit()

print(-1)
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]

y = [[x[i], i] for i in range(n)]
y.sort()

z = [0 for i in range(n)]
for i in range(n):
    z[y[i][1]] = (y[:i]+y[i+1:])[(n+1)//2-1][0]

for i in range(n):
    print(z[i])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]

y = sorted(x)
med1 = y[n//2-1]
med2 = y[n//2]

for i in range(n):
    if x[i] <= med1:
        print(med2)
    else:
        print(med1)
### BUGGY CODE ###

n = int(input())
x = y = 1
for i in range(n):
    t, a = map(int, input().split())
    k = 1
    while True:
        if t*k >= x and a*k >= y:
            x, y = t*k, a*k
            break
        k += 1
print(x+y)

### FIXED CODE ###

n = int(input())
x = y = 1
for i in range(n):
    t, a = map(int, input().split())
    bx = 1 if x % t else 0
    by = 1 if y % a else 0
    k = max(x//t + bx, y//a + by)
    x, y = t*k, a*k
print(x+y)
### BUGGY CODE ###

from collections import deque
A =input()
S = deque(A)
H = 1
Q = int(input())
Qlist = []
for i in range(Q):
    op = list((map(str,input().split())))
    if len(op) ==1:
        H *= -1
    else:
        if op[1] =='1':
            if H == 1:
                S.appendleft(op[2])
            else:
                S.append(op[2]) 
        else:
            if H == 1:
                S.append(op[2])
            else:
                S.appendleft(op[2])
if H == -1:
    A = S[-1]
    for i in range(1,len(S)):
        A += S[-i-1]
else:
    A = S[0]
    for i in range(1,len(S)):
        A += S[i]
print(A)

### FIXED CODE ###

from collections import deque
S= deque(input())
Q = int(input())
ba = 1
for i in range(Q):
    Query =list(map(str,input().split()))
    Query0 = Query[0]
    if Query[0] == '1':
        ba *= -1
    else:
        if Query[1] == '1' and ba ==1:
            S.appendleft(Query[2])
        elif Query[1] == '1' and ba ==-1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==-1:
            S.appendleft(Query[2])
if ba == -1:
    S.reverse()
mojieru = ''.join(S)
print(mojieru)
### BUGGY CODE ###

N = int(input())
As = []

for _ in range(N):
  A = int(input())
  if A in As:
    As.remove(A)
  else:
    As.append(A)

print(len(As))

### FIXED CODE ###

N = int(input())
A = []
count = 1
ans = 0

for _ in range(N):
  A.append(int(input()))

A.sort()

for i in range(N-1):
  if A[i] == A[i+1]:
    count += 1
  else:
    if count%2 == 1:
      ans += 1
    count = 1
else:
  if count%2 == 1:
    ans += 1
  else:
    count = 1

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

N = int(input())
X = int(input(),2)
from collections import Counter


def pop_count(n):
    return n%Counter(bin(n))['1']
ans = 0
for i in range(N-1,-1,-1):
    n = X^pow(2,i)
    while n != 0:
        n = pop_count(n)
        ans += 1
    print(ans)
    ans = 0

### FIXED CODE ###

N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)
### BUGGY CODE ###

S=input()
N=len(S)


T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
for i in range(N):
    s=S[N-1-i]
    tmp=s+tmp
    val=int(tmp)%2019
    d[val]+=1

ans=0
for i in d:
    ans+=((i*(i-1))//2)


print(ans)

### FIXED CODE ###

S=input()
N=len(S)
#「連続する区間」についての問題では、”累積和的なもの”をとるのが定石である。
#Sの連続する区間が、右からa文字分から、右からb文字分を取り除いたものであるとき
#その区間の整数が2019の倍数になるということは、s[a]とs[b]を2019で割ったあまりが等しい
#十分条件であることは分かったが、必要条件であるのか
#結論として必要条件でもある
#なぜなら2019と10は互いに素であるからである。

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

print(sum(i*(i-1)//2 for i in d))