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

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N = []
for i in range(H+W):
    b = power(M[i],e-2)
    N.append(b)
def c(a,b):
    return M[a+b-2]*N[a-1]*N[b-1]%e

T = 0
for i in range(B+1,W+1):
    P = c(H-A,i)
    Q = c(A,W-i+1)
    T = (T + P*Q)
print(T%e)

### FIXED CODE ###

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N= [0]*(H+W)
N[H+W-1] = power(M[H+W-1], e-2)
for i in range(H+W-2, -1, -1):
    N[i] = N[i+1] * (i+1) % e

def c(a,b):
    return M[a]*N[b]*N[a-b]%e

T = 0
for i in range(W-B):
    P = c(H+W-A-i-2,H-A-1)
    Q = c(A+i-1,i)
    T = (T + P*Q)
print(T%e)
### BUGGY CODE ###

def p(x):
  return bin(x).count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + 2**(N-i-1) % (cnt + 1)) % (cnt + 1)
  if X[i] == '1':
    if cnt == 1:
      print(0)
      continue
    k = (b - 2**(N-i-1) % (cnt - 1)) % (cnt - 1)  
  print(f(k)+1)

### FIXED CODE ###

def p(x):
  return bin(x).count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = a
    k += pow(2,N-i-1,cnt+1)
    k %= cnt+1
  else:
    if cnt == 1:
      print(0)
      continue
    k = b
    k -= pow(2,N-i-1,cnt-1) 
    k %= cnt-1  
  print(f(k)+1)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
# return -A[0]-...-A[k-1]+A[k]+...+A[N-1]
def partial_sum(k):
    return -sum(B[:k]) + sum(B[k:])

l = [partial_sum(i) -(N-2*i)*B[i] for i in range(N)]
print(min(l))


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
b = B[(N-1)//2] if N % 2 != 0 else (B[N//2-1]+B[N//2])//2
print(sum(abs(B[i]-b) for i in range(N)))
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


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

mod = 10**9 + 7
A = pow_by_binary_exponentiation(2, n, mod) - 1

A -= cmb(n, a) % mod
A -= cmb(n, b) % mod
print(A % mod)


### FIXED CODE ###


def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


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

mod = 10**9+7
fact = [1]
fact_inv = [1]
for i in range(max(a, b)):
    new_fact = fact[-1]*(i+1) % mod
    fact.append(new_fact)


def mod_comb_k(n, k, mod):
    ret = 1
    for i in range(k):
        ret *= (n-i)
        ret %= mod
    return ret * pow(fact[k], mod-2, mod) % mod


A = pow_by_binary_exponentiation(2, N, mod) - 1

A -= mod_comb_k(N, a, mod)
A -= mod_comb_k(N, b, mod)
print(A % mod)
### BUGGY CODE ###

N, K =map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Aset = list(set(A))
Aset.sort()
NumA =[0]*len(Aset)
for i in range(len(Aset)):
    NumA[i]=A.count(Aset[i])
NumA.sort()
ans = 0
for i in range(len(Aset)-K):
    ans += NumA[i]
print(ans)

### FIXED CODE ###

#ABC081C
import collections
N, K =map(int,input().split())
A = list(map(int,input().split()))
c = collections.Counter(A)
NumA = list(c.values())
NumA.sort()
ans = 0
#print(NumA)
for i in range(len(set(A))-K):
    ans += NumA[i]
print(ans)
### BUGGY CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k]+abs(H[i] - H[i - k]))
        else:
            break
print(dp[-1])

### FIXED CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k]+abs(H[i] - H[i - k]))
        else:
            break
print(dp[-1])
### BUGGY CODE ###

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

n_prev = n

while True:
    n = abs(n - k)
    if n > n_prev:
        print(n_prev)
        exit()
    else:
        n_prev = n


### FIXED CODE ###

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

print(min(n%k, abs(k- n%k)))
### BUGGY CODE ###

X = int(input())
for i in range(10**5):
    s = sum(range(i))
    if s < X <= s + i:
        break
print(i)

### FIXED CODE ###

X = int(input())
s = 0
for i in range(10**5):
    if s < X <= s + i:
        break
    s += i
print(i)
### BUGGY CODE ###

N,K = list(map(int,input().split(' ')))
pi = list(map(int,input().split(' ')))
value = max(sum([(n+1)/2 for n in pi[i:K+i]]) for i in range(N-K+1))
print(value)

### FIXED CODE ###

N,K = list(map(int,input().split(' ')))
pi = list(map(int,input().split(' ')))
value = sum(pi[:K])
max_value = value
for i in range(N-K):
  value -= pi[i]
  value += pi[i+K]
  max_value = max(value, max_value)
print((max_value+K)/2)
### BUGGY CODE ###

MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

DP = [[0]*13 for i in range(N)]
K = 1
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            if i==0:
                DP[0][(j*K)%13] = 1
            else:
                for k in range(13):
                    DP[i][(j*K+k)%13] += DP[i-1][k]%MOD
    else:
        j = int(S[i])*K
        if i==0:
            DP[0][(j*K)%13] = 1
        else:
            for k in range(13):
                DP[i][(j+k)%13] += DP[i-1][k]%MOD
    K = (K*10)%13
print(DP[N-1][5]%MOD)

### FIXED CODE ###

MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

DP = [[0]*13 for i in range(N)]
K = 1
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            if i==0:
                DP[0][(j*K)%13] = 1
            else:
                for k in range(13):
                    DP[i][(j*K+k)%13] += DP[i-1][k]
    else:
        j = int(S[i])*K
        if i==0:
            DP[0][(j*K)%13] = 1
        else:
            for k in range(13):
                DP[i][(j+k)%13] += DP[i-1][k]
    K = (K*10)%13
    for j in range(13):
        DP[i][j] = DP[i][j]%MOD
print(DP[N-1][5]%MOD)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
  if i in a:dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
  if i in a:dp[i]=0
print(dp[n])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
for j in range(n):
    excp = a.pop(j)
    print(max(a))
    a.insert(j, excp)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_copy = a.copy()
biggest = max(a)
a_copy.remove(biggest)
second_biggest = max(a_copy)

for j in range(n):
    if a[j] == biggest:
        print(second_biggest)
    else:
        print(biggest)
### BUGGY CODE ###

def main():
  s=input()
  k=int(input())
  substr=set()
  l=len(s)
  for i in range(l):
    substring=''
    for j in range(i,l):
      substring+=s[j]
      substr.add(substring)
  substr=list(substr)
  substr.sort()
  print(substr[k-1])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  s=input()
  k=int(input())
  l=len(s)
  
  substr=set()
  for alpha in 'abcdefghijklmnopqrstuvwxyz':
    for i in range(l):
      if s[i]==alpha:
        sub=s[i]
        substr.add(sub)
        j=i+1
        cnt=0
        while j<l and cnt<6:
          sub+=s[j]
          substr.add(sub)
          j+=1
          cnt+=1
    if len(substr)>k:
      break
      
  substr=list(substr)
  substr.sort()
  print(substr[k-1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

# X1の拘束条件
# A1 * 2 && last
X1_up = min(A[0], A[-1]) * 2
Xlast_up = min(A[-1], A[-2]) * 2

def chk(x1, xlast):
    prev = x1
    for index in range(len(A)-1):
        d = 2 * (A[index] - int(prev //2))
        prev = d
    return prev == xlast


ansx1 = -1
ansxlast = -1
is_found = False
for x1 in range(0,X1_up + 1, 2):
    for xlast in range(0, Xlast_up + 1, 2):
        if x1 == 2 * A[-1] - xlast and chk(x1, xlast): 
            ansx1 = x1
            ansxlast = xlast
            is_found = True
            break
    if is_found:
        break


ans = []
ans.append(ansx1)
prev = ansx1
for index in range(len(A)-1):
    d = 2 * (A[index] - int(prev //2))
    ans.append(d)
    prev = d

print(' '.join(map(str, ans)))



### FIXED CODE ###

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

# X1の拘束条件
# A1 * 2 && last

ansx1 = 0
is_m = False
for a in reversed(A):
    if is_m:
        ansx1 -= a
    else:
        ansx1 += a
    is_m = not is_m


ans = []
ans.append(ansx1)
prev = ansx1
for index in range(len(A)-1):
    d = 2 * (A[index] - int(prev //2))
    ans.append(d)
    prev = d

print(' '.join(map(str, ans)))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
count = []
for i in range(Q):
    l,r = map(int,input().split())
    count.append(S[l-1:r].count('AC'))

for i in count:
    print(i)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for i in range(Q)]
rui_count = []
AC_k = S.find('AC')
if AC_k == -1:
    for i in range(Q):
        print(0)
    exit()
for i in range(N):
    if AC_k+1 > i:
        if i == 0:
            rui_count.append(0)
        else:
            rui_count.append(rui_count[i-1])
        continue
    AC_k = S[i:N].find('AC')
    if AC_k == -1:
        rui_count += [rui_count[i-1]+1 for j in range(i,N)]
        break
    AC_k += i
    rui_count.append(rui_count[i-1]+1)
count = []
for i in lr:
    count.append(rui_count[i[1]-1]-rui_count[i[0]-1])
for i in count:
    print(i)
### BUGGY CODE ###

text = input()
lst = list(text)
result=[0]*len(lst)
letter=[]
for i in range(1,len(lst)):
  if(lst[i]!=lst[i-1]):
    letter=letter+[i]
letter=letter+[len(lst)]

##端の処理
i=0
while(lst[i]=="L"):
  i=i+1
result[0]=i
i=0
while(lst[-i-1]=="R"):
  i=i+1
result[-1]=i


####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

#はじめの文字がLのとき
if(lst[0]=="L"):
  i=1
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
else:
  n=letter[0]
  m=letter[1]-letter[0]
  if((n+m)%2==0):
    result[letter[0]-1]=(n+m)//2
    result[letter[0]]=(n+m)//2
  elif(n%2==1):
    result[letter[0]-1]=(n+m+1)//2
    result[letter[0]]=(n+m-1)//2   
  else:
    result[letter[0]-1]=(n+m-1)//2
    result[letter[0]]=(n+m+1)//2 
  i=2
  while(i+1<len(letter)):
    n=letter[i]-letter[i-1]
    m=letter[i+1]-letter[i]
    if((n+m)%2==0):
      result[letter[i]-1]=(n+m)//2
      result[letter[i]]=(n+m)//2
    elif(n%2==1):
      result[letter[i]-1]=(n+m+1)//2
      result[letter[i]]=(n+m-1)//2   
    else:
      result[letter[i]-1]=(n+m-1)//2
      result[letter[i]]=(n+m+1)//2
    i=i+2
print(' '.join(map(str, result)))



### FIXED CODE ###

text = input()
result=[0]*len(text)
N=len(text)

####RRR...(n個)...RL...(m個)...Lのとき
####n+mが偶数なら(n+m)/2個ずつ
####奇数ならnが奇数のときRに(n+m+1)/2,Lに(n+m-1)/2
####nが偶数のときRに(n+m-1)/2,Lに(n+m+1)/2たまる

s=0
i=0
j=0
while j<N :
  while text[i]=="R" :
    i+=1
  j=i+1
  while (j<N and text[j]=="L") :
    j+=1
  if (j-s)%2==0:
    result[i-1]=(j-s)//2
    result[i]=(j-s)//2
  else:
    result[i-1]=(j-s-1)//2
    result[i]=(j-s-1)//2
    result[i-(s-i)%2]+=1
  s=j
  i=s+1

print(' '.join(map(str, result)))
### BUGGY CODE ###

h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())


for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
  y0,x0=p[s]
  
  while s!=g:
    s = a[y0][x0]+d
    y,x = p[s]
    z +=abs(x-x0)+abs(y-y0)
    x0 = x
    y0 = y

  print(z)

### FIXED CODE ###

I=lambda:map(int,input().split())
h,w,d=I()
H={}
W={}
for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
x=1+h*w
s=[0 for _ in range(x)]
for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

for _ in range(int(input())):
  a,b=I()
  print(s[b]-s[a])
### BUGGY CODE ###

n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)]
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[-1][-1])


### FIXED CODE ###

n,w=map(int,input().split())
cost=[[0 for i in range(w+1)] for j in range(n+1)]
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(1,n+1):
  for j in range(w+1):
    weight_=value[i-1][0]
    value_=value[i-1][1]
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(cost[-1][-1])
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n = ni()
s = ns()

ans = s.count('R') * s.count('G') * s.count('B')

for i in range(10000):
    if 2 + 2 * i >= n: break
    for j in range(10000):
        if 2 + 2 * i + j >= n: break
        if not(s[j] == s[i+1+j] or s[i+1+j] == s[2*i+2+j] or s[2*i+2+j] == s[j]):
            ans -= 1

print(ans)

### FIXED CODE ###

import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n = ni()
s = ns()

ans = s.count('R') * s.count('G') * s.count('B')

for i in range(10000):
    if 2 + 2 * i >= n: break
    for j in range(10000):
        if 2 + 2 * i + j >= n: break
        if not(s[j] == s[i+1+j] or s[i+1+j] == s[2*i+2+j] or s[2*i+2+j] == s[j]):
            ans -= 1

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

s=input()
t=input()
dp=[[""]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]="".join([dp[i][j],s[i]])
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                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)])

### FIXED CODE ###

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

res=""
i=len(s); j=len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        res="".join([s[i-1],res])
        i-=1
        j-=1
print(res)
### BUGGY CODE ###

# 時間がかかりすぎる

import numpy as np

K = int(input())

def runrun(n):
    if n < 10:
        return True
    
    ns = str(n)

    for i in range(len(ns)-1):
        if abs(int(ns[i]) - int(ns[i+1])) > 1:
            return False

    return True

R = 0
while K > 0:
    R += 1
    if runrun(R):
        K -= 1

print(R)

### FIXED CODE ###

from collections import deque
k = int(input())
q = deque(list(range(1, 10)))

for _ in range(k-1):
    d = q.popleft()

    if d%10 > 0:
        q.append(d*10 + d%10 - 1)

    q.append(d*10 + d%10)
    
    if d%10 < 9:
        q.append(d*10 + d%10 + 1)

print(q.popleft())
### BUGGY CODE ###

s = input()
a = int(s)
mods = [0]*2019
mods[a%2019] += 1
d = 10**(len(s)-1)
for i in s:
  a = a-int(i)*d
  d = d//10
  mods[a%2019] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import bisect
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
b, c = [], []
heapq.heapify(a)

for i in range(m):
    v1, v2 = map(int, input().split())
    b.append(v1)
    c.append(v2)

for i in range(m):
    cnt = 0
    while True:
        if cnt == b[i]:
            break
        minV = heapq.heappop(a)
        #print('# minV: ' + str(minV))
        if minV >= c[i]:
            heapq.heappush(a, minV)
            break
        else:
            heapq.heappush(a, c[i])
        cnt += 1

#print(a)
print(sum(a))




### FIXED CODE ###

import bisect
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
#b, c = [], []
bc = []
heapq.heapify(a)

for i in range(m):
    bc.append(list(map(int, input().split())))
    # v1, v2 = map(int, input().split())
    # b.append(v1)
    # c.append(v2)
bc.sort(key = lambda x: x[1], reverse=True)

for i in range(m):
    cnt = 0
    while True:
        if cnt == bc[i][0]:
            break
        minV = heapq.heappop(a)
        #print('# minV: ' + str(minV))
        if minV >= bc[i][1]:
            heapq.heappush(a, minV)
            break
        else:
            heapq.heappush(a, bc[i][1])
        cnt += 1

#print(a)
print(sum(a))
### BUGGY CODE ###

N=int(input())
numbers=[]
for _ in range(N):
    X,L=map(int,input().split())
    left=X-L
    right=X+L
    numbers.append([right,left])
numbers=sorted(numbers)
answer=1
large=numbers[0][0]
for  _ in range(len(numbers)-1):
    if numbers[answer][0]>large and numbers[answer][1]>=large:
        large=numbers[answer][0]
        answer+=1
    else:
        del numbers[answer]
print(answer)


### FIXED CODE ###

N=int(input())
numbers=[]
for _ in range(N):
    X,L=map(int,input().split())
    left=X-L
    right=X+L
    numbers.append([right,left])
numbers=sorted(numbers)
answer=1
large=numbers[0][0]
for  _ in range(len(numbers)-1):
    if numbers[answer][0]>large and numbers[answer][1]>=large:
        large=numbers[answer][0]
        answer+=1
    else:
        del numbers[answer]
print(answer)
### BUGGY CODE ###

def bellman_ford(s, n, G, st):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if y in st:
                    update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        G.append([a-1, b-1, -c+p])
        U[b-1].append(a-1)
    st = set()
    st.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st:
                q.append(v)
                st.add(v)
    ans = bellman_ford(0, n, G, st)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def bellman_ford(s, n, G):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    V = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
        V[v[0]].append(v[1])
    st1 = set()
    st1.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st1:
                q.append(v)
                st1.add(v)
    st2 = set()
    st2.add(0)
    q = [0]
    while len(q) > 0:
        t = q.pop(-1)
        for v in V[t]:
            if not v in st2:
                q.append(v)
                st2.add(v)
    st = st1 & st2
    eg = []
    for v in G:
        if v[0] in st and v[1] in st:
            eg.append(v)
    ans = bellman_ford(0, n, eg)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

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

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
for i in x:
    print((y[n // 2 - 1], y[n // 2])[i in y[: n // 2]])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n // 2 - 1]
b = y[n // 2]
for i in x:
    print((a, b)[i <= a])