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

import sys

#+++++
		
def main():
	n,m = map(int, input().split())
	if n == 1:
		return m
	
	ret = 0
	for i in range(1, m):
		a = m // i
		b = m % i
		if b == 0 and n*i <= m:
			ret = i
			
		if n*i > m:
			return ret
			
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import math

#+++++


		
def main():
	n,m = map(int, input().split())
	if m % n ==0:
		return m // n
		
	ll=1
	for i in range(1, int(math.sqrt(m))+1):
		#pa((i,ll))
		if m % i == 0:
			if i >= n:
				ll=max(ll, m // i)
			if m // i >= n:
				ll=max(ll, i)
	return ll
				

#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

def ex():
    n = input()
    dish = []
    for i in range(int(n)):
        tmp = [int(each) for each in input().split()]
        dish.append((tmp[0] - tmp[1], tmp[1] - tmp[0], tmp[0], tmp[1]))

    point = [0, 0]

    player = 0
    while len(dish) > 0:
        # print('player', player)
        sorted(dish, key=lambda v: v[player], reverse=True)
        # print(dish[0])
        point[player] += dish.pop(0)[player + 2]
        player = int(not player)
        # print('point', point)

    print(point[0] - point[1])


ex()


### FIXED CODE ###

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] + tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    dish = dishes.pop(0)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(0,k):
  if a>=1:
    a=a-1
  else:
    if b>=1:
      b=b-1
print("{} {}".format(a,b))

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  a=a-k
else:
  b=b-(k-a)
  a=0
b=max(0,b)
print("{} {}".format(a,b))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
cnt = 1
tmp = A[0]
for i in range(N):
    if A[i] > tmp:
        tmp = A[i]
        cnt += 1
cnt2 = 1
tmp = A[N-1]
for i in range(N):
    if A[N-1-i] > tmp:
        tmp = A[N-1-i]
        cnt += 1
if cnt2 >= cnt:
    A = A[::-1]
ans = 0
while True:
    tmp = -1
    for i in range(N):
        if A[i] > tmp:
            tmp = A[i]
            A[i] = -1
    if tmp == -1:
        break
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)][::-1]
def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
print(LIS(A))
### BUGGY CODE ###

import copy
n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

dist = [[-1 for i in range(n+1)] for j in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
    hist = [i]
    while True:
        hist_tmp = []
        for h in hist:
            for j in range(m):
                if a[j] == h and (dist[i][b[j]] == -1 or dist[i][b[j]] > dist[i][a[j]] + c[j]):
                    dist[i][b[j]] = dist[i][a[j]] + c[j]
                    hist_tmp.append(b[j])
                elif b[j] == h and (dist[i][a[j]] == -1 or dist[i][a[j]] > dist[i][b[j]] + c[j]):
                    dist[i][a[j]] = dist[i][b[j]] + c[j]
                    hist_tmp.append(a[j])
        if hist_tmp == []:
            break
        else:
            hist = copy.copy(hist_tmp)

count = 0
for i in range(m):
    if dist[a[i]][b[i]] < c[i]:
        count += 1
print(count)

### FIXED CODE ###

n, m = map(lambda x: int(x), input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
    a[i], b[i], c[i] = map(lambda x: int(x), input().split())

inf = 100 * 1000
dist = [[inf for i in range(n+1)] for j in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

count = 0
for i in range(m):
    if dist[a[i]][b[i]] < c[i]:
        count += 1
print(count)
### BUGGY CODE ###

def translate(x,y):
    if x == y[0]:
      return y[1]
    if x == y[1]:
      return y[0]
    return x

s1 = list(input())
s2 = list(input())
list = s1

count = 0
for i in range(len(list)):
    if s1[i] != s2[i]:
      x = s1[i]
      y = s2[i]
      for j in range(len(s1)):
        if s1[j] == x:
          s1[j]=y
        elif s1[j] == y:
          s1[j]=x
      #s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
      #s1.replace( s1[i], "X").replace( s2[i], x).replace( 'X' , y)
      #s1 = list(map(translate, s1))
      
      count = count+1
    if s1[0:i] != s2[0:i]:
      break
    if count > 27:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")


### FIXED CODE ###

def translate(x,y):
    if x == y[0]:
      return y[1]
    if x == y[1]:
      return y[0]
    return x

s1 = list(input())
s2 = list(input())
list = s1

count = 0
for i in range(len(list)):
    if s1[i] != s2[i]:
      x = s1[i]
      y = s2[i]
      for j in range(len(s1)):
        if s1[j] == x:
          s1[j]=y
        elif s1[j] == y:
          s1[j]=x
      #s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
      #s1.replace( s1[i], "X").replace( s2[i], x).replace( 'X' , y)
      #s1 = list(map(translate, s1))
      
      count = count+1
    if count > 27:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")
### BUGGY CODE ###

class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)

#print(dp.node)
print(dp.Get(0, n))

### FIXED CODE ###

INF = 10**30

class Rmax():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)

#print(dp.node)
print(dp.Get(0, n))
### BUGGY CODE ###

N = int(input())
A = [int(e) for e in input().split()]
sum = 0
asum = 0
for i in A :
    asum = asum + i*i
    for j in A:
        sum = sum + i*j
sum = ((sum - asum)/2)%1000000007

print(int(sum))

### FIXED CODE ###

N = int(input())
A = [int(e) for e in input().split()]

S = [0]
sum =0
for i in range(0, N):
    S.append(S[i] + A[i])
for i in range(N):
    sum = sum + (S[i+1]-A[i]) * A[i]
print(sum%1000000007)
### BUGGY CODE ###

n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append([p,y])
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_ma = {}
for k,v in ma.items():
    sorted_ma[k] = list(sorted(v))
#print(ma)
for a in all_li:
    count = sorted_ma[a[0]].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))


### FIXED CODE ###

from bisect import bisect_right
n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append((p,y))
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_li = [[] for _ in range(n)]
for k,v in ma.items():
    sorted_li[k-1] = list(sorted(v))
#print(ma)
for a in all_li:
    #print(a[1],sorted_li[a[0]-1])
    count = bisect_right(sorted_li[a[0]-1],a[1],)
    #count = sorted_li[a[0]-1].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))
### BUGGY CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
def longest(arr, x):    # legacy
    return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)
nums = list(counter.values())
num_counter = collections.Counter(nums)
lastest_add = np.count_nonzero(nums)
building = [0]
longests = [0]
for i in range(1, n+1):
    appended = building[-1] + lastest_add
    building.append(appended)
    longests.append(appended // i)
    lastest_add -= num_counter[i]

for k in range(1, n+1):
    maxindexes = list(i for i, x in enumerate(longests) if x >= k)
    if maxindexes:
        print(maxindexes[-1])
    else:
        print(0)
    


### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

import copy

def func(n, m, r, adj):
    inf = 10 ** 9
    dis = adj
    for i in range(len(adj)):
        for j in range(len(adj)):
            if i != j and dis[i][j] == 0:
                dis[i][j] = inf

    # 全ての頂点間の最短距離を算出、
    for k in range(len(dis)):
        for i in range(len(dis)):
            for j in range(len(dis)):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = inf
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

# import math
# import fractions
# import numpy as np

MOD = 10 ** 9 + 7

def solve(N, A):
    # for i, a in enumerate(A):
    #     A[i] = bin(a)
    # print(A)
    
    B = []
    for i in range(N - 1):
        for j in range(i+1, N):
          B.append((A[i] ^ A[j]) % MOD)  

    return sum(B) % MOD

# S = input()
N = int(input())
# H, N = map(int, input().split())
A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
# A = []
# B = []
# for _ in range(N):
#     a, b = list(map(int, input().split()))
#     A.append(a)
#     B.append(b)

print(solve(N, A))


### FIXED CODE ###

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

MOD = 10 ** 9 + 7
ans = 0
m = 1
ans = 0
for _ in range(60):
    one_count = sum(a & m for a in aaa)
    one_count //= m
    zero_count = n - one_count
    ans = (ans + one_count * zero_count * m) % MOD
    m *= 2
        
print(ans)
### BUGGY CODE ###

def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    if l < h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < h and a[r] > a[largest]:
        largest = r

    if largest != i:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        print(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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



import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["second"] = set()
	G[i]["third"] = set()
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["second"] = G[i]["second"] | set(G[node]["eda"])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["third"] = G[i]["third"] | G[node]["second"]

node_set = [S]
G[S]["num"] = 0
times = 1
while True:
	node_set2 = []
	for node in node_set:
		if T in G[node]["third"]:
			print(times)
			exit()
		for node2 in G[node]["third"]:
			if G[node2]["num"] == -1:
				G[node2]["num"] = times
				node_set2.append(node2)

	if len(node_set2) == 0:
		print(-1)
		exit()
	node_set = copy.deepcopy(node_set2)
	times += 1

### FIXED CODE ###



import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx))
    dist[sy][sx] = 0
    while Q:
        q = Q.popleft()
        y = q[0]
        x = q[1]
        if y == gy and x == gx:
            continue
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] > dist[y][x]+1:
                        dist[n_y][n_x] = dist[y][x] + 1
                        Q.append((n_y,n_x))
                    else:
                        continue

                else:
                    break

    if dist[gy][gx] == INF:
        print('-1')
    else:
        print(dist[gy][gx])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

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

def f(s,K):
 if len(s)==1:
  K%=26
  if ord(s[0])+K<123:
   return chr(ord(s[0])+K)
  else:
   return chr(ord(s[0])+K-26)
 res=0
 for i in range(len(s)):
  if s[i]=="a":
   continue
  if K>=123-ord(s[i]):
   res+=1
   K-=123-ord(s[i])
  else:
   break
 str=""
 for i in range(res):
  str+="a"
 if res==0:
  return s[0]+f(s[1:],K)
 return str+f(s[res:],K)
ss=input()
KK=int(input())
print(f(ss,KK))

### FIXED CODE ###

def f(s,K):
 if K==0:
  return s,"",0
 res=0
 str=""
 for i in range(len(s)-1):
  if s[i]=="a":
   str+="a"
   res+=1
   continue
  if K>=123-ord(s[i]):
   str+="a"
   res+=1
   K-=123-ord(s[i])
  else:
   break
 if res==0:
  skip=0
  for skip in range(len(s)):
   if K>=123-ord(s[skip]):
    break
  return s[:skip],s[skip:],K
 return str,s[res:],K

ss=input()
KK=int(input())
sol=""
while len(ss)>1:
 x,ss,KK=f(ss,KK)
 sol+=x
if len(ss)==1:
 KK%=26
 if ord(ss[0])+KK<123:
  sol+=chr(ord(ss[0])+KK)
 else:
  sol+=chr(ord(ss[0])+KK-26)
print(sol)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 998244353

s_list = []
for _ in range(k):
    l, r = map(int, input().split())
    s_list += list(range(l, r + 1))
S = set(sorted(s_list))

ans_array = [0] * (n + 1)
ans_array[1] = 1
for i in range(1, n):
    for d in S:
        if d + i > n:
            break
        ans_array[d + i] = (ans_array[d + i] + ans_array[i]) % mod


print(ans_array[n])

### FIXED CODE ###

# 累積和を用いたdpの高速か

n, k = map(int, input().split())
mod = 998244353

lr_list = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1
sdp = [0] * (n + 1)
sdp[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        right = max(0, i - lr_list[j][0])
        left = max(0, i - lr_list[j][1] - 1)
        dp[i] = (dp[i] + sdp[right] - sdp[left]) % mod
    sdp[i] = sdp[i - 1] + dp[i]

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

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

argsort = [[x, i] for i, x in enumerate(X)]
argsort.sort()
argsort = [[i, j] for j, [_, i], in enumerate(argsort)]
argsort.sort()
ranks = [j + 1 for _, j in argsort]

indices = [[x, i] for i, x in enumerate(X)]
indices.sort()
indices = {(i + 1): x for i, (x, _) in enumerate(indices)}


median = N // 2
for i in range(0, N):
    r = ranks[i]
    if r <= median:
        print(indices[median + 1])
    else:
        print(indices[median])


### FIXED CODE ###

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

argsort = [[x, i] for i, x in enumerate(X)]
argsort.sort()

indices = {(i + 1): x for i, (x, _) in enumerate(argsort)}

argsort = [[i, j] for j, [_, i], in enumerate(argsort)]
argsort.sort()

ranks = [j + 1 for _, j in argsort]

median = N // 2
for i in range(0, N):
    r = ranks[i]
    if r <= median:
        print(indices[median + 1])
    else:
        print(indices[median])