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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
    
h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
aque = []
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    aque.append([y, x])
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in aque:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)


### FIXED CODE ###

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

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in que:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)
### BUGGY CODE ###

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

gokei = 0
ans1 = 0

for i in range(N):
    gokei = sum(A[:i+1])
    # 偶数番目を負に
    if i % 2 == 0:
        if gokei >= 0:
            ans1 += abs(-1 - gokei)
            A[i] -= abs(-1 - gokei)
    if i % 2 == 1:
        if gokei <= 0:
            ans1 += 1 - gokei
            A[i] += (1 - gokei)


gokei = 0
ans2 = 0
for i in range(N):
    gokei = sum(B[:i+1])
    # 偶数番目を正に
    if i % 2 == 0:
        if gokei <= 0:
            ans2 += 1 - gokei
            B[i] += (1 - gokei)
    else:
        if gokei >= 0:
            ans2 += abs(-1 - gokei)
            B[i] -= abs(-1 - gokei)

print(min(ans1, ans2))

### FIXED CODE ###

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

gokei = 0
ans1 = 0

for i in range(N):
    gokei += A[i]
    # 偶数番目を負に
    if i % 2 == 0:
        if gokei >= 0:
            ans1 += abs(-1 - gokei)
            gokei -= abs(-1 - gokei)
    if i % 2 == 1:
        if gokei <= 0:
            ans1 += 1 - gokei
            gokei += (1 - gokei)


gokei = 0
ans2 = 0
for i in range(N):
    gokei += A[i]
    # 偶数番目を正に
    if i % 2 == 0:
        if gokei <= 0:
            ans2 += 1 - gokei
            gokei += (1 - gokei)
    else:
        if gokei >= 0:
            ans2 += abs(-1 - gokei)
            gokei -= abs(-1 - gokei)

print(min(ans1, ans2))
### BUGGY CODE ###

import sys
from math import log2,floor
N = int(sys.stdin.readline().rstrip())
A = list(map(int,sys.stdin.readline().split()))
mod = 10**9+7
ans = 0
for i in range(61):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    ans += ((bits*(N-bits))* 2**i) %mod
ans %= mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split()))
cnt=0
for i in range(min(D),max(D)+1):
    c=[]
    for d in D:
        if d>=i:
            c.append(d)
    if len(c)==N//2:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
D=list(map(int,input().split()))
D=sorted(D,reverse=True)
print(D[n//2-1]-D[n//2])
### BUGGY CODE ###

N = int(input())
ratio = []
for _ in range(N):
    ratio.append(tuple(map(int, input().split())))
ans = 0; total_t = 0; total_a = 0;
for t, a in ratio:
    i = 1
    while total_t > t*i or total_a > a*i:
        i += 1
    total_t = t*i
    total_a = a*i
    ans = total_t + total_a
print(ans)

### FIXED CODE ###

N = int(input())
ratio = []
for _ in range(N):
    ratio.append(tuple(map(int, input().split())))
total_t = 1; total_a = 1;
for t, a in ratio:
    q = max((total_t + t - 1) // t, (total_a + a - 1) // a)
    total_t = t*q
    total_a = a*q
ans = total_t + total_a
print(ans)
### BUGGY CODE ###

import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, input().split()))
XY = np.array([list(map(int, input().split())) for _ in range(N)])
X = XY[:, 0]
Y = XY[:, 1]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    for yi, yj in itertools.combinations(range(N), r=2):
        L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum((L <= X) & (X <= r) & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
print(ans)


### FIXED CODE ###

import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)
### BUGGY CODE ###

n=int(input())
arr=[]
ans=0
for i in range(n):
    s=input()
    if s not in arr:
        ans+=1
    arr.append(s)
print(ans)

### FIXED CODE ###

import collections 
n=int(input())
s_list=list(input() for _ in range(n))
c=collections.Counter(s_list)
print(len(c.keys()))
### BUGGY CODE ###

isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
l=[0]*m
r=[0]*m
for i in range(m):
    l[i],r[i]=[int(i)-1 for i in input().split(' ')]
a=[set() for i in range(n)]
for i in range(m):
    for j in range(l[i],r[i]+1):
        a[j].add(i)
a=[(index,i) for index,i in enumerate(a)]
a.sort(key=lambda i:len(i[1]),reverse=True)
s={i for i in range(m)}
c=0
for k,v in a:
    t=s-v
    if len(t)==0:
        c+=1
print(c)

### FIXED CODE ###

isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
l=[0]*m
r=[0]*m
for i in range(m):
    l[i],r[i]=[int(i)-1 for i in input().split(' ')]
x=min(r)-max(l)+1
x=x if x>0 else 0
print(x)
### BUGGY CODE ###

import numpy as np

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

dp = [np.inf] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    for j in range(0,K+1):
        if i - j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[N-1])

### FIXED CODE ###

import numpy as np

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

dp = np.array([np.inf] * N)
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
        if i - K >= 0:
            dp[i] = min(dp[i-K:i]+abs(h[i]-h[i-K:i]))
        else:
            dp[i] = min(dp[0:i]+abs(h[i]-h[0:i]))
print(int(dp[N-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = list(map(int, [input() for _ in range(m)]))
dp = [0] * (n+1)

#`dp[i] = i段目にいる通り数`
if not 0 in a:
    dp[0] = 1
if not 1 in a:
    dp[1] = 1
    
for i in range(2,n+1):
    if i in a:
        dp[i] = 0
    else: 
        dp[i] += (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)

print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = set(map(int, [input() for _ in range(m)]))
dp = [0] * (n+1)

#`dp[i] = i段目にいる通り数`
if not 0 in a:
    dp[0] = 1
if not 1 in a:
    dp[1] = 1
    
for i in range(2,n+1):
    if i in a:
        dp[i] = 0
    else: 
        dp[i] += (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)

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

def D():
    n = int(input())
    S = [i for i in range(1, n+1)]
    ans = 0
    # for i in range(1, n+1):
    #     m = 0
    #     s = [i for i in range(1, n+1)]
    #     for j in range(len(s)):
    #         m = max(m, s[0]%i)
    #         del s[0]

    #     print(i, m)
    #     ans += m
    ans = n*(n-1)//2
    print(ans)
D()

### FIXED CODE ###

def D():
    n = int(input())
    ans = 0
    # for i in range(1, n+1):
    #     m = 0
    #     s = [i for i in range(1, n+1)]
    #     for j in range(len(s)):
    #         m = max(m, s[0]%i)
    #         del s[0]

    #     print(i, m)
    #     ans += m
    ans = n*(n-1)//2
    print(ans)
D()
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


K = int(input())

L = [[[0] * K for _ in range(K)] for _ in range(K)]
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        d = gcd(a, b)
        for c in range(1, K+1):
            x, y, z = sorted([a, b, c])
            x -= 1
            y -= 1
            z -= 1
            if L[x][y][z] != 0:
                ans += L[x][y][z]
            else:
                t = gcd(d, c)
                ans += t
                L[x][y][z] = t

print(ans)

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


K = int(input())

L = [[0] * (K+1) for _ in range(K+1)]
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        x, y = sorted([a, b])
        if L[x][y] == 0:
            d = gcd(a, b)
            L[x][y] = d
        else:
            d = L[x][y]
        for c in range(1, K+1):
            x, y = sorted([d, c])
            if L[x][y] == 0:
                t = gcd(d, c)
                L[x][y] = t
                ans += t
            else:
                ans += L[x][y]


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

from collections import defaultdict
N = int(input())
s = [tuple(sorted(list(input()))) for _ in  range(N)]

d = defaultdict(int)
ans = 0
for i in range(N):
  if s[i] in d.keys():
    ans += d[s[i]]
    d[s[i]] += 1
  else:
    d[s[i]] += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
s = ["".join(sorted(list(input()))) for _ in  range(N)]

d = defaultdict(int)
ans = 0
for i in range(N):
  if s[i] in d.keys():
    ans += d[s[i]]
    d[s[i]] += 1
  else:
    d[s[i]] += 1

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

H, W, A, B = [int(i) for i in input().split(" ")]

from collections import deque

field = [[0 if w <= B-1 and h >= H - A else 1 for w in range(W)] for h in range(H)]

goal_cnt = 0
que = deque([])
que.append((0, 0))

while que:
    p = que.popleft()
    if p[0] == H-1 and p[1] == W-1:
        goal_cnt += 1
        goal_cnt %= 10**9 + 7
    else:
        for vh, vw in [[1, 0], [0, 1]]:
            pos_h = p[0] + vh
            pos_w = p[1] + vw
            
            if 0 <= pos_h <= H-1 and 0 <= pos_w <= W-1 and field[pos_h][pos_w] == 1:
                que.append((pos_h, pos_w))
print(goal_cnt)

### FIXED CODE ###

U = 2*10**5
MOD = 10**9+7
 
fact = [1] * (U+1)
fact_inv = [1] * (U+1)

# 階乗のテーブル作成
for i in range(1, U+1):
    fact[i] = (fact[i-1] * i) % MOD

# 階乗の逆元のテーブル作成
fact_inv[U] = pow(fact[U], MOD-2, MOD)
for i in range(U, 0, -1):
    fact_inv[i-1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n-k]
    x %= MOD
    return x

H, W, A, B = [int(i) for i in input().split(" ")]

ans = 0
# 経路の足し上げ C(縦+横, 縦(or横)) (重複のある組み合わせ)
for i in range(B, W):
    ans += comb((H-A-1) + i, i) * comb((A - 1) + (W-1-i), W-1- i) % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

A.sort()
if A[0] == 0:
  print(0)
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
  if ans > 10**18:
    print(-1)
  else:
    print(ans)

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

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

mod = 10**9+7

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


l = lcm(*A)
B = 0
for i in range(N):
  B += l//A[i]
  B %= mod
print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

import itertools
##print(ord("A"))
#n = int(input())
n,k,q = map(int,input().split())
#h = list(map(int,input().split()))	
ans_list=[input() for i in range(q)]
pnt_list = [k]*n
#print(pnt_list)
for i in range(q):
    #print(pnt_list)
    for j in range(n):
    
        if ans_list[i]==str(j+1):
            pass
        else:
            pnt_list[j]=pnt_list[j]-1
for i in range(len(pnt_list)):
    if pnt_list[i]>0:
        print("Yes")
    else:
        print("No")
#print(pnt_list)

### FIXED CODE ###

import itertools
##print(ord("A"))
#n = int(input())
n,k,q = map(int,input().split())
#h = list(map(int,input().split()))	
ans_list=[input() for i in range(q)]
pnt_list = [k-q]*n
#print(pnt_list)
for i in range(q):

    pnt_list[int(ans_list[i])-1]+=1
#print(pnt_list)
for i in range(len(pnt_list)):
    if pnt_list[i]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

for i in range(N):
  A *= L[i]
  
if A > 10**18:
  print("-1")
else:
  print(A)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
A = []
ans = 1
L.sort()

for i in range (N):
  ans*= L[i]
  if ans == 0 or ans > 10**18:
    break
if ans > 10**18:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import sys
from collections import deque

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

def main():
    H,W = map(int,input().split())
    A = [list(input()) for _ in range(H)]

    def bfs(x,y,A):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
 
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '#':
                    continue
                cnt = 1 if A[y][x] == '#' else A[y][x] + 1
                if A[sy][sx] == '.':
                    que.append((sx,sy))
                    A[sy][sx] = cnt
                elif A[sy][sx] > cnt:
                    que.append((sx,sy))
                    A[sy][sx] = cnt

    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                bfs(x,y,A)
    ans = 0
    for a in A:
        a = [i if i != '#' else 0 for i in a]
        ans = max(ans,max(a))
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque

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

def main():
    H,W = map(int,input().split())
    A = [list(input()) for _ in range(H)]

    que = deque()
    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                que.append((x,y,0))        
    ans = 0
    while que:
        x,y,c = que.popleft()
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '#':
                continue
            if A[sy][sx] == '.':
                que.append((sx,sy,c+1))
                A[sy][sx] = c + 1
                ans = max(ans,c+1)
    print(ans)

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

N,M = map(int, input().split())
a = []
b = []
ans = 0

for i in range(N):
    store = input().split()
    a.append(int(store[0]))
    b.append(int(store[1]))

nokori = M
for i in range(M):
    if nokori >= 1:
        index = a.index(min(a))
        if nokori - (b[index]) >= 0:
            ans += a[index] * b[index]
            nokori -= b[index]
            a.pop(index)
            b.pop(index)
        else:
            ans += a[index] * nokori
            break
    else:
        break
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
ab = []
ans = 0

for i in range(N):
    ab.append(list(map(int, input().split())))
ab = sorted(ab)
nokori = M
for i in ab:
    if nokori - i[1] >= 0:
        ans += i[0] * i[1]
        nokori -= i[1]
    else:
        ans += i[0] * nokori
        break

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

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    num = 1000000000000000000
    ans = 1
    for i in range(n):
        ans *= a_list[i]

    if ans <= num:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = tuple(map(int, input().split()))
    num = 1e18
    ans = 1
    if (0 in a_list):
        print(0)
        sys.exit()
    for i in range(n):
        ans *= a_list[i]
        if ans > num:
            print(-1)
            sys.exit()

    
    if ans <= num:
        print(ans)
    else:
        print(-1)

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

n = int(input())
a = input().split()
b = []
for i in range(n):
    b.append(a[i])
    b.reverse()

print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = input().split()

a_odd = a[0::2]
a_even = a[1::2]

if n % 2 == 1:
    print(" ".join(a_odd[::-1] + a_even))
else:
    print(" ".join(a_even[::-1] + a_odd))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])
### BUGGY CODE ###

S = input()

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

c = {}
for i in range(len(S)):
    if S[len(S) - i - 1] != "?":
        continue
    tc = {i: 0 for i in range(13)}
    iii = 10 ** i
    for j in range(0, 10):
        t = j * iii
        tc[t % 13] += 1
    c[i] = tc

dp = []
tdp = {i: 0 for i in range(13)}
tdp[SS] += 1
dp.append(tdp)
for k, v in c.items():
    tdp = {i: 0 for i in range(13)}
    for r, _ in v.items():
        if _ > 0:
            for _r, _v in dp[-1].items():
                tdp[(_r + r) % 13] += _v
    dp.append(tdp)

ans = dp[-1][5]
print(ans % (10**9 + 7))

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

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

def main():
    N = int(input())
    x_list = list(map(int, input().split()))
    x_sort = x_list[:]
    x_sort.sort()
    med = (N // 2) -1
    threshold = x_sort[med]
    med_dict = {}

    for i in range(N):
        if x_list[i] in med_dict:
            print(med_dict[x_list[i]])
        elif x_list[i] > threshold:
            print(threshold)
        else:
            removed_x_list = x_list[:]
            removed_x_list.remove(x_list[i])
            removed_x_list.sort()
            median = removed_x_list[med]
            med_dict[x_list[i]] = median
            print(median)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    N = int(input())
    x_list = list(map(int, input().split()))
    x_list_sort = x_list[:]
    x_list_sort.sort()
    med1 = x_list_sort[(N//2)-1]
    med2 = x_list_sort[N//2]
    for i in x_list:
        if i <= med1:
            print(med2)
        elif i >= med2:
            print(med1)
            
if __name__ == '__main__':
    main()