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

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {10 ** 10}
    for t, x in events:
        if x == INF: # query
            y = min(dst)
            if y == 10 ** 10:
                y = -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

def main():
  s = input()
  q = int(input())
  for i in range(q):
    que = input().split()
    if que[0] == '1':
      s = s[::-1]
    else:
      if que[1] == '1':
        s = que[2] + s
      else:
        s = s + que[2]
  print(s)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  s = list(input())
  s = s[:-1]
  s = deque(s)
  q = int(input())
  c = [[i for i in input().split()] for j in range(q)]
  cnt = 1
  for i in c:
    if i[0] == '1':
      cnt *= -1
    else:
      if (i[1] == '1' and cnt == 1) or (i[1] == '2' and cnt == -1):
        s.appendleft(i[2])
      else:
        s.append(i[2])
  if cnt == 1:
    print(''.join(s))
  else:
    print(''.join(s)[::-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect
n = int(input())
As = list(map(int, input().split()))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = 0
for a in As:
    cntB = bisect.bisect_right(Bs, a)
    for b in Bs[cntB:]:
        cnt += len(Cs) - bisect.bisect_right(Cs, b)
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
As = list(map(int, input().split()))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = [0]*(n+1)
v = 0
for idx, b in enumerate(Bs[::-1]):
    v += len(Cs) - bisect.bisect_right(Cs, b)
    cnt[n-1-idx] = v

print(sum([cnt[bisect.bisect_right(Bs, a)] for a in As]))
### BUGGY CODE ###

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

output=min(S[1:].count("E"),S[:N-1].count("W"))

for i in range(1,N-1):
    cnt=S[:i].count("W")+S[i+1:].count("E")
    output=min(output,cnt)
print(output)

### FIXED CODE ###

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

output=S[1:].count("E")
a=output

for i in range(N-1):
    if(S[i]=="W"):
        a+=1
    if(S[i+1]=="E"):
        a-=1
    if(a<output):
        output=a
print(output)
### BUGGY CODE ###

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for i in range(n)]
ans=0

x=sorted(ab, key=lambda x :x[1])
x.reverse()

v=[i for i in range(1,m+1)]


for i in range(n):
    if len(v)==0:
        break
    for j in range(m):
        if v[-1]>=x[i][0]:
            if v[j]>=x[i][0]:
                ans+=x[i][1]
                del v[j]
                break
        
print(ans)

### FIXED CODE ###

import heapq
def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)
 
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)
 
print(ans)
### BUGGY CODE ###

import sys
import itertools

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))
mod = 10**9 + 7

n = ri()
a = rl()
ans = 0
for li in itertools.combinations(a, 2):
    a, b = li
    ans = (ans + a*b)%mod
print(ans)

### FIXED CODE ###

import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))
mod = 10**9 + 7

n = ri()
a = rl()
s = sum(a)
ans = 0
for i in a:
    s -= i
    ans = (ans + s*i)%mod
print(ans)
### BUGGY CODE ###

import math
import numpy as np

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n,k = NextInts()
da = np.array(NextIntList(), np.int64)
for i in range(n):
    da[i]-=1

dp = np.zeros((61, n), dtype=np.int64)

dp[0] = da

for i in range(60):
    for j in range(n):
        dp[i+1][j] = dp[i][dp[i][j]]

ans = 0
for i in range(61):
    if k&1:
        ans = dp[i][ans]
    k >>= 1
print(ans+1)

### FIXED CODE ###

import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n,k = NextInts()
da = NextIntList()
for i in range(n):
    da[i]-=1

dp = [[0 for i in range(n)] for i in range(61)]

dp[0] = da

for i in range(60):
    for j in range(n):
        dp[i+1][j] = dp[i][dp[i][j]]

ans = 0
for i in range(61):
    if k&1:
        ans = dp[i][ans]
    k >>= 1
print(ans+1)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

a = [0 if i % C == 0 or i % D == 0 else 1 for i in range(A, B+1)]

print(sum(a))

### FIXED CODE ###

from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
lcm_num = lcm
A, B, C, D = map(int, input().split())

lcm_num = lcm(C, D)

if A%C == 0:
    cnt_c = A//C - 1
else:
    cnt_c = A//C

if A%D == 0:
    cnt_d = A//D - 1
else:
    cnt_d = A//D

if A%(lcm_num) == 0:
    cnt_cd = A//(lcm_num) - 1
else:
    cnt_cd = A//(lcm_num)



num = (B//C)+(B//D)-(B//(lcm_num)) - (cnt_c + cnt_d - cnt_cd)
print(B-A+1-num)
### BUGGY CODE ###

n = int(input())
l = [0]*100000000

for i in range(n):
  x = int(input())
  if l[x-1] == 0:
    l[x-1] = 1
  else:
    l[x-1] = 0

print(l.count(1))

### FIXED CODE ###

import collections

n = int(input())
li = [int(input()) for i in range(n)]
c = collections.Counter(li)
ans = 0

for item in c.items():
    if item[1]%2 == 1:
        ans += 1

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

import sys

s = sys.stdin.readline().replace('\n','')
q = sys.stdin.readline().replace('\n','')
q = int(q)

flag = 0
for i in range(0,q):
	str = sys.stdin.readline().replace('\n','')
        if( str[0] == '1'):
          flag += 1
        if( str[0] == '2'):
          if( str[2] == '1'):
	    if( flag % 2 == 0):
	      s = str[4] + s
	    else:
	      s = s+ str[4]
          if( str[2] == '2'):
	    if( flag % 2 == 0):
	      s = s+ str[4]
	    else:
	      s = str[4] + s

if( flag % 2 == 1):
  s = s[::-1]

print s
sys.stdout.flush()


### FIXED CODE ###

import sys

s = sys.stdin.readline().replace('\n','')
q = sys.stdin.readline().replace('\n','')
q = int(q)

flag = 0
prev=""
end=""
for i in range(0,q):
	str = sys.stdin.readline().replace('\n','')
        if( str[0] == '1'):
          flag += 1
        if( str[0] == '2'):
          if( str[2] == '1'):
	    if( flag % 2 == 0):
	      prev = str[4] + prev
	    else:
	      end = end + str[4]
          if( str[2] == '2'):
	    if( flag % 2 == 0):
	      end = end + str[4]
	    else:
	      prev = str[4] + prev

ss = prev + s + end
if( flag % 2 == 1):
  ss = ss[::-1]

print ss
sys.stdout.flush()
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(0,1000):
  if i >= 100:
    t = str(i)
  elif i >= 10:
    t = "0"+str(i)
  else:
    t = "00"+str(i)
  ti = 0
  for j in range(N):
    if S[j] == t[ti]:
      ti += 1
      if ti == 3:
        count += 1
        break
print(count)

### FIXED CODE ###

N = int(input())
S = input()
count = 0
for i in range(0,1000):
  if i >= 100:
    t = str(i)
  elif i >= 10:
    t = "0"+str(i)
  else:
    t = "00"+str(i)
  ti = 0
  for j in range(N):
    if S[j] == t[ti]:
      ti += 1
      if ti == 3:
        count += 1
        break
print(count)
### BUGGY CODE ###

#!/usr/bin/env python

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

inip = 1 
for i in range(k):
    inip *= a[i]

p = [inip]
tmp = inip

for i in range(k, n): 
    s = tmp//a[i-k]*a[i]
    p.append(s)
    tmp = s 

for i in range(len(p)-1):
    if p[i+1] > p[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

#!/usr/bin/env python

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

for i in range(n-k):
    if a[i] < a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
r = []
t = n*(n-1)//2
ds = Unionfind(n)
for i in range(m):
  q, p = b[-i-1]
  r.insert(0, t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size[pp] * ds.size[qq]
  ds.union(p, q)
for x in r:
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
b.sort()
c.sort()
cnt = 0

for i in range(n):
    insert_index_b = bisect.bisect_right(b, a[i])  # 昇順
    for j in range(insert_index_b, n):
        insert_index_c = bisect.bisect_right(c, b[j])
        cnt += n - insert_index_c

print(cnt)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
cnt = 0
ans = 0
memo = [0] * n

for i in range(n):
    insert_index_c = bisect.bisect_right(c, b[i])
    cnt += n - insert_index_c
    memo[i] += cnt

for i in range(n):
    if a[i] > b[n - 1]:
        break
    insert_index_b = bisect.bisect_right(b, a[i])  # 昇順
    if insert_index_b >= 1:
        ans += memo[n - 1] - memo[insert_index_b - 1]
    else:
        ans += memo[n - insert_index_b - 1]

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

import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(['#'] + list(input()) + ['#'])
grid.append(['#'] * (w+2))

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

#for i in range(h+2):
#    print(grid[i])



for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == '#':
            continue
        else:
            l[i][j] = l[i][j-1]+1

for i in range(1,h+1):
    for j in range(w+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            r[i][j] = r[i][j+1]+1

for j in range(1,w+1):
    for i in range(1,h+1):
        if grid[i][j] == '#':
            continue
        else:
            u[i][j] = u[i-1][j]+1

for j in range(1,w+1):
    for i in range(h+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            d[i][j] = d[i+1][j]+1

print((l+r+u+d).max()-3)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,N = map(int,input().split())
spells = [list(map(int,input().split())) for i in range(N)]
INF = 10**10
dp = [INF]*(H+1)
dp[0] = 0
for use in spells:
    damage = use[0]
    mp = use[1]
    for i in range(1,H+1):
        dp[i] = min(dp[max(0,i-damage)] + mp, dp[i])
print(dp[-1])


### FIXED CODE ###

h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+1)#そのHPを与えるのに必要な最小MP
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    dp[hp]=min(dp[max(0,hp-use[0])]+use[1],dp[hp])
print(dp[h])
### BUGGY CODE ###

N, K = map(int, input().split())
k = 2*N // K
ans = 0
for a in range(1, N+1):
    b = 0
    if 2*a %K != 0:
        continue
    kmin = a//K +1
    for i in range(kmin, k+1):
        if i*K - a > N:
            break
        b += 1
    ans += b*b
print(ans)
        
    

### FIXED CODE ###

N, K = map(int, input().split())
if K % 2 == 1:
    a = N // K
    print(a**3)
else:
    a = N//K
    a2 = N//(K//2) -a
    print(a**3 +a2**3)
### BUGGY CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
x = [list(map(int,input().split())) for nesya in range(m)]
s = list(range(1,n+1))
for hoge in x:
  if h[hoge[0]-1] > h[hoge[1]-1]:
    try:
      s.remove(hoge[1])
    except ValueError:
      pass
  elif h[hoge[0]-1] < h[hoge[1]-1]:
    try:
      s.remove(hoge[0])
    except ValueError:
      pass
  else:
    try:
      s.remove(hoge[0])
    except ValueError:
      pass
    try:
      s.remove(hoge[1])
    except ValueError:
      pass
print(len(s))


### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
x = [list(map(int,input().split())) for nesya in range(m)]
k = [1]*n
for route in x:
  h1 = route[0]-1
  h2 = route[1]-1
  if h[h1] < h[h2]:
    k[h1] = 0
  elif h[h1] > h[h2]:
    k[h2] = 0
  else:
    k[h1] = 0
    k[h2] = 0
print(sum(k))
### BUGGY CODE ###

def binary_search_list(beSearched,wanted) :
    l = 0
    r = len(beSearched)

    #print("condition = {}".format(r-l))

    while r - l >= 1 :
        s = (l + r) // 2
        #print("l={} r={} s={}".format(l,r,s))
        if beSearched[s] == wanted :
            return True
        if beSearched[s] > wanted :
            r = s
        else :
            l = s + 1

    return False

K,S = (int(_) for _ in input().split())
num = [_ for _ in range(K+1)]
out = 0
for i in range(K+1):
    for j in range(i+1):
        #print(num[:j+1])
        b = binary_search_list(num[:j+1],S - i - j)
        #print("b={} i={} j={} k = {}".format(b,i,j, S- i -j))
        if b :
            if i == j and j == S - i - j:
                out += 1
            elif i == j or j == S - i - j or S -i - j == i:
                out += 3
            else :
                out += 6

print(out)


### FIXED CODE ###

def binary_search_list(beSearched,wanted) :
    l = 0
    r = len(beSearched)

    #print("condition = {}".format(r-l))

    while r - l >= 1 :
        s = (l + r) // 2
        #print("l={} r={} s={}".format(l,r,s))
        if beSearched[s] == wanted :
            return True
        if beSearched[s] > wanted :
            r = s
        else :
            l = s + 1

    return False

K,S = (int(_) for _ in input().split())
num = [_ for _ in range(K+1)]
out = 0
for i in range(K+1):
    for j in range(i+1):
        if 0 <= S - i - j <= j :
            if i == j and j == S - i - j:
                out += 1
            elif i == j or j == S - i - j or S -i - j == i:
                out += 3
            else :
                out += 6
        #print(num[:j+1])
        #b = binary_search_list(num[:j+1],S - i - j)
        #print("b={} i={} j={} k = {}".format(b,i,j, S- i -j))
        #if b :
            #if i == j and j == S - i - j:
                #out += 1
            #elif i == j or j == S - i - j or S -i - j == i:
                #out += 3
            #else :
                #out += 6

print(out)
### BUGGY CODE ###

from collections import Counter
N = int(input())
src = list(map(int,input().split()))

ctr1 = Counter()
ctr2 = Counter()

ans = []
for i in range(N):
    ctr1.update([src[i]])
    ctr2.update([src[-i-1]])
    if ctr1 == ctr2:
        ans.append(i+1)

print(*sorted(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from bisect import bisect_left, insort

N = int(input())
src = list(map(int,input().split()))
ans = []
A, B = [], []

for i in range(N):
    a, b = src[i], src[-i-1]
    addA = False
    addB = False

    if a != b:
        j = bisect_left(B, a)
        if j != len(B) and B[j] == a:
            del B[j]
        else:
            addA = True

        j = bisect_left(A, b)
        if j != len(A) and A[j] == b:
            del A[j]
        else:
            insort(B, b)

        if addA:
            insort(A, a)

    if len(A) == len(B) == 0:
        ans.append(i+1)

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

n = int(input())
s = input()
ans = n

for i in range(n):
    w_to_e = s[0:i].count('W')
    e_to_w = s[i+1:n].count('E')
    if w_to_e + e_to_w < ans:
        ans = w_to_e + e_to_w
print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
s = input()
reverse_list_1 = [0]
reverse_list_2 = [0]
ans = n

for i in range(1,n):
    if s[i-1] == 'W':
        reverse_list_1.append(reverse_list_1[i-1]+1)
    else:
        reverse_list_1.append(reverse_list_1[i-1])

for i in range(1,n):
    if s[n-i] == 'E':
        reverse_list_2.append(reverse_list_2[i-1]+1)
    else:
        reverse_list_2.append(reverse_list_2[i-1])

reverse_list_2 = list(reversed(reverse_list_2))

for i in range(n):
    if reverse_list_1[i]+reverse_list_2[i] < ans:
        ans = reverse_list_1[i]+reverse_list_2[i]
print(ans)
### BUGGY CODE ###

n, q = (int(x) for x in input().split())
s = input()
s = [s[i] for i in range(n)]
lr = []
for i in range(q):
    lr.append([int(x) for x in input().split()])
ac = [0 for _ in range(n)]
i = 0
while i < n:
    if s[i] == "A":
        i += 1
        if s[i] == "C":
            ac[i-1] = 1
            ac[i] = 1
            i += 1
        else: i += 1
    else: i += 1
for p in lr:
    l, r = p[0] - 1, p[1] - 1
    a = sum(ac[l:r]) + ac[r]
    if s[l] == "C" and ac[l] == 1: a -= 1
    if s[r] == "A" and ac[r] == 1: a -= 1
    print(int(a/2))

### FIXED CODE ###

n, q = (int(x) for x in input().split())
s = input()
s = [s[i] for i in range(n)]
lr = []
for i in range(q):
    lr.append([int(x) for x in input().split()])
ac = [0 for _ in range(n)]
i, c = 0, 0
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        ac[i+1] = ac[i] + 1
    else:
        ac[i+1] = ac[i]
for p in lr:
    l, r = p[0] - 1, p[1] - 1
    print(int(ac[r] - ac[l]))
### BUGGY CODE ###

n,m=map(int,input().split())
lista = [int(i) for i in input().split()]

lista.sort(reverse=True)
#print(lista)

if n==1:
    ans=int(sum(lista)/(2**m))

else:
    for i in range(m):
        lista[0]=lista[0]/2
        lista.sort(reverse=True)
    #print(lista)    

    for i in range(n):
        lista[i]=int(lista[i])

    ans=sum(lista)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
lista = [int(i) for i in input().split()]


for i in range(len(lista)):
    lista[i]=lista[i]*-1

import heapq

heapq.heapify(lista)

for i in range(m):
        b=heapq.heappop(lista)
        b=b/2
        heapq.heappush(lista,b)
        
for i in range(n):
        lista[i]=int(lista[i]*-1)

ans=sum(lista)
print(ans)
### BUGGY CODE ###

import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
v = math.factorial(n - 1)


for i in range(1, n):
    w = (v//i)%mod
    ans += (x[n - 1] - x[i - 1]) * w
    ans %= mod

print(int(ans))

### FIXED CODE ###

import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
f = 1
for i in range(1,n):
  f *= i
  f %= mod

for i in range(n-1):
    ans+=(x[n-1]-x[i])*pow(i+1,mod-2,mod)

ans*=f
ans%=mod


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

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

sorted_x = sorted(x_ls)
bigger = sorted_x[n//2]
smaller = sorted_x[n//2 - 1]
for i in range(n):
    target_ind = sorted_x.index(x_ls[i])
    if target_ind <= n // 2 - 1:
        ans = bigger
    else:
        ans = smaller
    print(ans)


### FIXED CODE ###

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

sorted_x = sorted(x_ls)
bigger = sorted_x[n//2]
smaller = sorted_x[n//2 - 1]

# 含まれてるならそのインデックス 、含まれてないなら-1を返す
def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return mid
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return -1

for i in range(n):
    target_ind = binary_search(sorted_x, x_ls[i])
    if target_ind <= n // 2 - 1:
        ans = bigger
    else:
        ans = smaller
    print(ans)