Harryxun/stf_run huggingface dataset:
nq = input().split()
n, q = int(nq[0]), int(nq[1])
s = list(input())
r_li = []
l_li = []
t_li = []
ac_li = []
for i in range(q):
    rl = input().split()
    l_li.append(int(rl[0]))
    r_li.append(int(rl[1]))
count = 0
i = 0
while True:
    if i == n - 1:
        t_li.append(count)
        break
    else:
        if s[i] == "A":
            if s[i + 1] == "C":
                t_li.append(count)
                count += 1
                t_li.append(count)
                i += 2
            else:
                t_li.append(count)
                i += 1
        else:
                i += 1
                t_li.append(count)
for i in range(q):
    print(t_li[r_li[i] - 1] - t_li[l_li[i] - 1])









### FIXED CODE ###

nq = input().split()
n, q = int(nq[0]), int(nq[1])
s = list(input())
r_li = []
l_li = []
t_li = []
for i in range(q):
    rl = input().split()
    l_li.append(int(rl[0]))
    r_li.append(int(rl[1]))
count = 0
i = 0
while True:
    if i == n:
        break
    else:
        if s[i] == "A":
            if i == n - 1:
                i += 1
                t_li.append(count)
            else:
                if s[i + 1] == "C":
                    t_li.append(count)
                    count += 1
                    t_li.append(count)
                    i += 2
                else:
                    t_li.append(count)
                    i += 1
        else:
            i += 1
            t_li.append(count)
for i in range(q):
    print(t_li[r_li[i] - 1] - t_li[l_li[i] - 1])
def main():
 a,b,c = map(int,input().split())
 rhs = c - a - b
 lhs = 4 * a * b
 if rhs > 0  and lhs ** 2 < rhs:
  print('Yes')
 else:
  print('No')
main(

### FIXED CODE ###


def main():
 a,b,c = map(int,input().split())
 rhs = c - a - b
 lhs = 4 * a * b
 if rhs > 0  and lhs < rhs ** 2:
  print('Yes')
 else:
  print('No')
main()
n = str(input())

length = 4 #nの長さ
spaces = length -1

masterlist = []
opelist = ["+"] * spaces

for i in range(2 ** spaces):
    opelist = ["+"] * spaces

    for j in range(spaces):
        if j >> j & 1:
            opelist[j] = "-"
        else:
            opelist[j] = "+"

    masterlist.append(opelist)

for opes in masterlist:
    nls = list(n)
    for k in range(len(opes)):
        nls.insert(2*k+1,opes[k])
        #print(nls)
    nstr = ''.join(nls)
    if eval(nstr) == 7:
        print(f"{nstr}=7")
        exit()

### FIXED CODE ###

n = str(input())

length = 4 #nの長さ
spaces = length -1

masterlist = []
opelist = ["+"] * spaces

for i in range(2 ** spaces):
    opelist = ["+"] * spaces

    for j in range(spaces):
        if i >> j & 1:
            opelist[j] = "-"
        else:
            opelist[j] = "+"

    masterlist.append(opelist)

for opes in masterlist:
    nls = list(n)
    for k in range(len(opes)):
        nls.insert(2*k+1,opes[k])
        #print(nls)
    nstr = ''.join(nls)
    if eval(nstr) == 7:
        print("{}=7".format(nstr))
        exit()
# coding: utf-8

s = int(input())

i = 0
while n > 0:
    if n % 2 = 0:
        n = n / 2
    else:
        n = 3n+1
    if n == 4:
        break
    else:
        i += 1

print(i+4)

### FIXED CODE ###

# coding: utf-8

n = int(input())

i = 1
while n > 0:
    if n == 4 or n == 2 or n == 1:
        break
    i += 1
    if n % 2 == 0:
        n = n / 2
    else:
        n = n*3+1

print(i+3)
N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
BCs = []
for m in range(M):
  B, C = map(int, input().split())
  BCs.append((B, C))
BCs.sort(key=lambda BC: -BC[1])
#print(BCs)

index = 0
for m in range(M):
  B, C = BCs[m]
  for i in range(B):
    if As[index] < C:
      As[index] = C
      index += 1
    else:
      break
print(sum(As))


### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
BCs = []
for m in range(M):
  B, C = map(int, input().split())
  BCs.append((B, C))
BCs.sort(key=lambda BC: -BC[1])
#print(BCs)

index = 0
for m in range(M):
  B, C = BCs[m]
  for i in range(B):
    if index >= N:
      break
    if As[index] < C:
      As[index] = C
      index += 1
    else:
      break
print(sum(As))
import math
n,m = map(int, input().split())
dat_n = []
dat_m = []
for i in range(n):
    a,b = map(int, input().split())
    dat_n.append((a, b))
for i in range(m):
    a,b = map(int, input().split())
    dat_m.append((a, b))
for i in range(n):
    a, b = dat_n[i]
    index = -1
    distance = math.inf
    for j in range(m):
        c,d = dat_m[j]
        t = abs(a-c) + abs(b-d)
        if t < distance:
            index = j + 1
            distance = t
    print(index)


### FIXED CODE ###

n,m = map(int, input().split())
dat_n = []
dat_m = []
for i in range(n):
    a,b = map(int, input().split())
    dat_n.append((a, b))
for i in range(m):
    a,b = map(int, input().split())
    dat_m.append((a, b))
for i in range(n):
    a, b = dat_n[i]
    index = -1
    distance = 1000000001
    for j in range(m):
        c,d = dat_m[j]
        t = abs(a-c) + abs(b-d)
        if t < distance:
            index = j + 1
            distance = t
    print(index)
import math

[n, x] = map(int, input().split(" "))
xs = list(map(int, input().split(" ")))
xs.append(x)
xs.sort()
gcd =  xs[1] - xs[0]

for i in range(1, n):
    gcd = math.gcd(gcd,  xs[i] - xs[i - 1])

print(gcd)

### FIXED CODE ###

def getGcd(num1, num2):
    while True:
        tmp = num1
        num1 = num2 % num1
        num2 = tmp
        if(num1 == 0):
            return tmp

[n, x] = map(int, input().split(" "))
xs = list(map(int, input().split(" ")))

xs.append(x)
xs.sort()

gc = xs[1] - xs[0]

for i in range(1, n + 1):
    gc = getGcd(gc,  xs[i] - xs[i - 1])

print(gc)
hn_kz = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
kz_hn = {}
n, m, *kzs = map(int, open(0).read().split())
# 本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah = hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah] = max(kz_hn[ah], kz)
    else:
        kz_hn[ah] = kz
# 最小の本数をhmnに格納
hmn = min(kz_hn.keys())
# まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn = {kt * hmn: kt for kt in range(n // hmn + 1)}
# 最小本数以外の数の辞書nkz_hnを作る
nkz_hn = kz_hn.copy()
del nkz_hn[hmn]

inf = 10 ** 9


def keta(hn):
    #    print(hn,kt_hn)
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn < 0:
        return -inf
    else:
        maxketa = -inf
        for hni in nkz_hn.keys():
            newkt = keta(hn - hni) + 1
            if newkt > maxketa:
                maxketa = newkt
        kt_hn[hn] = maxketa
        return maxketa


ans = ""
nokori = n
while nokori > 0:
    for kh in sorted(kz_hn.items(), key=lambda xkh: xkh[1], reverse=True):
        if keta(nokori - kh[0]) == keta(nokori) - 1 and keta(nokori - kh[0]) >= 0:
            ans += str(kh[1])
            nokori -= kh[0]
            break

print(ans)

### FIXED CODE ###

def smax(s1, s2):
    if s1=="N":
        if s2[0]=="N":
            return "N"
        else:
            return s2
    if s2[0] == "N":
        return s1
    l1 = len(s1)
    l2 = len(s2)
    if l1 == l2:
        return max(s1, s2)
    if l1 > l2:
        return s1
    return s2

hon = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))
dp = ["N"] * (n + 1)
dp[0]=""
for i in range(2, n + 1):
    for a in aa:
        if i - hon[a] < 0: continue
        dp[i] = smax(dp[i], dp[i - hon[a]] + str(a))
print(dp[-1])
n=int(input())
l=list(map(int,input().split()))
if l.count(0)!=0:
  print(0)
else:
  num=1
  for i in l:
    if num>10**18:
      break
    else:
      num*=i
if num>=10**18:
  print(-1)
else:
  print(num)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
num=1
if l.count(0)!=0:
    print(0)
else:
    flag=True
    for i in l:
        if num>10**18:
            print(-1)
            flag=False
            break
        else:
            num*=i
    if flag==True:
        if num>10**18:
            print(-1)
        else:
            print(num)
n, m = map(int, input().split())
if m%2:
    for i in range(m//n, 0, -2):
    if not m%i:
        print(i)
        break
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break

### FIXED CODE ###

n, m = map(int, input().split())
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
if is_prime(m):
    print(1)
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break
def cost(i):
	if i == 0:
		return 0
	else:
		tmp = float("inf")
		tmp = min(tmp, cost(i - 1) + abs(h[i] - h[i - 1]))
		if i > 1:
			tmp = min(tmp, cost(i - 2) + abs(h[i] - h[i - 2]))
		return tmp
N = int(input())
h = list(map(int, input().split()))
print(cost(N - 1))

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(1, N):
	dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
	if i > 1:
		dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[N - 1])
h,n=map(int,input().split())

ab=[]
dp=[0]*(263)

for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[b]=a

#dp[b]は、自分がダメージをｂ受けた時の、相手に与えたダメージ
i=1
while 1:

    dp[i]=max(dp[i],dp[i-1])
    for k in range((i-1)//2+2):
        dp[i]=max(dp[i],dp[k]+dp[i-k])
    
    #print(dp)
    if dp[i]>=h:
        print(i)
        exit()
    i+=1

    
    



### FIXED CODE ###

h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)
from string import ascii_lowercase
s=set(input())
print(sorted([x for x in ascii_lowercase if not x in s])[0])

### FIXED CODE ###

from string import ascii_lowercase
s=set(input())
l=sorted([x for x in ascii_lowercase if not x in s])
if l:
  print(l[0])
else:
  print("None")
from collections import Counter

class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)
  
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -1
    return s
  
  def add(self, i, x):
    while i <= self.size:
      i += i & -i

n,k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10**9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
  single += bit.sum(a)
  bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a,c in sorted(cnt.items()):
  ans = (ans + c * before * conf) % MOD
  before += c
print(ans)





### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()*2))
base1 = 0
base2 = 0
for i in range(N):
  count1=0
  count2=0
  for j in range(i+1,i+N+1):
    if A[i] > A[j]:
      if j < N:
        count1+=1
      else:
        count2+=1
  base1+=count1
  base2+=count2

ans = (base1*K*(K+1) + base2*K*(K-1))//2
div = 10**9 + 7
print(ans%div)
n , k = list(map(input().split()))
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
min = h[-1]
for i in range(n - k):
    if min > h[i + k] - h[i]:
        min = h[i + k] - h[i]
print(min)

### FIXED CODE ###

n , k = list(map(int, input().split()))
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
min = h[-1]
for i in range(n - k + 1):
    if min > h[i + k - 1] - h[i]:
        min = h[i + k - 1] - h[i]
print(min)
n = int(input())

num_list = [ int(v) for v in input().split() ]
num_list = [ num_list[i] - (i+1) for i in range(n) ]
median_u = num_list[(n//2)+1]
median_d = num_list[n//2]

d_list = [i-median_u for i in num_list]
u_list = [i-median_d for i in num_list]

print(min(sum(map(abs,d_list)),sum(map(abs,u_list))))

### FIXED CODE ###

def total(inlist,k):
    print(sum([ abs(i-k) for i in inlist ]))
    return
n = int(input())
a_list = [ int(v) for v in input().split() ]
a_list = [ v-i for i, v in enumerate(a_list,1) ]
a_list.sort()

total(a_list,a_list[n//2])
a,b,c,d=map(int,input().split())
alice=[x for x in range(a,b+1)]
bob=[x for x in range(c,d+1)]
kaburi=list(set(alice) & set(bob))
if len(kaburi)<=1:
    print(0)
else:
    ans=kaburi[-1]-kaburi[0]
    print(ans)

### FIXED CODE ###

num=list(str(input()))
num_new=num[::-1]
if num==num_new:
    print("Yes")
else:
    print("No")
s=input()
print('A{}C'.format(s[8])

### FIXED CODE ###

s=input()
print('A' + s[8] + 'C')
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+1)

    for i in A:
        for j in range(1,10**6//i):
            l[j*i+1]+=1
    
    cnt=0
    for i in A:
        if l[i+1]<=1:
            cnt+=1
    print(cnt)




    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+5)

    for i in A:
        if l[i]!=0:
            l[i]+=1
            continue
        for j in range(i,10**6+5,i):
            l[j]+=1
    
    cnt=0
    for i in A:
        if l[i]==1:
            cnt+=1
    print(cnt)




    
resolve()
c=-1
d=0
f=0
g=0
N, M = map(int, input().split())
list = []
for i in range(M):
    a,b=input().split()
    list.append((int(a), int(b)))

for i in range(M):
	if list[i][0]>N and list[i][0]+list[i][1]==1:
		print(c)
		f=1
		break
	for j in range(i+1,M):
		if list[i][0]==list[j][0]:
			g=1
			if list[i][0]!=list[j][0]:
				print(c)
				f=1
				break
	if f==1:
		break
	if g==0:
		d+=list[i][1]*(10**(M-list[i][0]))
	g=0
if f==0:
	print(d)

### FIXED CODE ###

i= int(input())
i= int((i+1)/2)
print(i)
class UnionFind:
    def __init__(self, size):
        """
        リストの添字を集合の値として利用し
        リストの要素を根, 節の管理に用いる
        要素が負の添字は素集合の根であり、集合の要素数
        要素が0以上の添字は節であり
        要素は節の親の添字を指す
        """
        self.table = [-1] * size
        self.size = [1] * size
        
    def find(self, x):
        """
        xを持つ素集合の根を返す
        """
        if self.table[x] < 0:
            # 根の場合
            return x
        else:
            # 節の場合: 経路圧縮(path compression)
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        """
        x, yを持つ素集合を併合(Union)する
        """
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:  # x,yが異なる素集合に含まれている場合のみ併合
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

if __name__=="__main__":
    N, M = map(int, input().split())
    Q = [list(map(int, input().split())) for _ in range(M)]
    u = UnionFind(N)
    unconv = N*(N-1)//2
    ans = []
    for q in reversed(Q):
        ans.append(unconv)
        a = u.find(q[0]-1)
        b = u.find(q[1]-1)
        if a!=b:
            unconv -= u.table[a]*u.table[b]
        u.union(q[0]-1, q[1]-1)
    for a in reversed(ans):
        print(a)

### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        import sys
        sys.setrecursionlimit(10**5)
        """
        リストの添字を集合の値として利用し
        リストの要素を根, 節の管理に用いる
        要素が負の添字は素集合の根であり、集合の要素数
        要素が0以上の添字は節であり
        要素は節の親の添字を指す
        """
        self.table = [-1] * size
        self.size = [1] * size
        
    def find(self, x):
        """
        xを持つ素集合の根を返す
        """
        if self.table[x] < 0:
            # 根の場合
            return x
        else:
            # 節の場合: 経路圧縮(path compression)
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        """
        x, yを持つ素集合を併合(Union)する
        """
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:  # x,yが異なる素集合に含まれている場合のみ併合
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
if __name__=="__main__":
    N, M = map(int, input().split())
    Q = [list(map(int, input().split())) for _ in range(M)]
    u = UnionFind(N)
    unconv = N*(N-1)//2
    ans = []
    for q in reversed(Q):
        ans.append(unconv)
        a = u.find(q[0]-1)
        b = u.find(q[1]-1)
        if a!=b:
            unconv -= u.table[a]*u.table[b]
        u.union(q[0]-1, q[1]-1)
    for a in reversed(ans):
        print(a)
n = int(input())
a = [int(input()) for i in range(n)]

minv = R[0]
maxv = R[1] - R[0]
for j in range(1, n):
	if (maxv < R[j] - minv):
		maxv = R[j] - minv
	if (R[j] < minv):
		minv = R[j]
    
print(maxv)


### FIXED CODE ###

n = int(input())
R = [int(input()) for i in range(n)]

minv = R[0]
maxv = R[1] - R[0]
for j in range(1, n):
	if (maxv < R[j] - minv):
		maxv = R[j] - minv
	if (R[j] < minv):
		minv = R[j]
    
print(maxv)
from collections import Counter
H, W, M = map(int, input().split())

h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = map(int, input().split())


S = Counter(h)
T = Counter(w)

if (M == 1):
    print(1)

else:
    if (S.most_common()[0][1] > T.most_common()[0][1]):
        smc = S.most_common()[0][0]
        for i in range(M):
            if (h[i] == smc):
                w[i] = 'boom'

        w1 = [s for s in w if s != 'boom']
        T = Counter(w1)
        tmc = T.most_common()[0][0]
        for i in range(len(w1)):
            if (w1[i] == tmc):
                w1[i] = 'boom' 

        w2 = [s for s in w1 if s != 'boom']
        print(M-len(w2))

    else:
        tmc = T.most_common()[0][0]
        for i in range(M):
            if (w[i] == tmc):
                h[i] = 'boom'

        h1 = [s for s in h if s != 'boom']
        S = Counter(h1)
        smc = S.most_common()[0][0]
        for i in range(len(h1)):
            if (h1[i] == smc):
                h1[i] = 'boom' 

        h2 = [s for s in h1 if s != 'boom']
        print(M-len(h2))

### FIXED CODE ###

from collections import Counter
import sys
H, W, M = map(int, input().split())

h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = map(int, input().split())


S = Counter(h)
T = Counter(w)

if (M == 1):
    print(1)

else:
    if (S.most_common()[0][1] > T.most_common()[0][1]):
        smc = S.most_common()[0][0]
        for i in range(M):
            if (h[i] == smc):
                w[i] = 'boom'

        w1 = [s for s in w if s != 'boom']
        T = Counter(w1)
        if (len(w1) == 0):
            print(M)
            sys.exit()
        tmc = T.most_common()[0][0]
        for i in range(len(w1)):
            if (w1[i] == tmc):
                w1[i] = 'boom' 

        w2 = [s for s in w1 if s != 'boom']
        print(M-len(w2))

    else:
        tmc = T.most_common()[0][0]
        for i in range(M):
            if (w[i] == tmc):
                h[i] = 'boom'

        h1 = [s for s in h if s != 'boom']
        S = Counter(h1)
        if (len(h1) == 0):
            print(M)
            sys.exit()
        smc = S.most_common()[0][0]
        for i in range(len(h1)):
            if (h1[i] == smc):
                h1[i] = 'boom' 

        h2 = [s for s in h1 if s != 'boom']
        print(M-len(h2))
import numpy as np
L = int(input())
N = int(input())
xs = []
ws = []
for i in range(N):
    x, w = map(int, input().split())
    xs.append(x)
    ws.append(w)
xs = np.array(xs)
ws = np.array(ws)
s = sum(xs * ws)
if(s == 0):
    print(0)
elif(s < 0):
    print(1)
    print(-s, 1)
else:
    print(1)
    print(s, -1)

### FIXED CODE ###

L = int(input())
N = int(input())
s = 0
for i in range(N):
    x, w = map(int, input().split())
    s += x * w
if(s == 0):
    print(0)
elif(s < 0):
    print(1)
    print(1, -s)
else:
    print(1)
    print(-1, s)
# -*- coding: utf-8 -*-

import math

def lcm(a,b):
    return (a * b) // math.gcd(a, b)

def main(N,T):
    ans = 1
    for t in T:
        ans = lcm(ans, t)
        
    print(ans)

if __name__ == '__main__':
    N = int(input())
    T = []
    for i in range(N):
        T.append(int(input()))
    main(N,T)

### FIXED CODE ###

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

def gcd(a,b):
    if(b==0):
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return (a * b)//gcd(a, b)

def main(N,T):
    ans = 1
    for t in T:
        ans = lcm(ans, t)
        
    print(ans)

if __name__ == '__main__':
    N = int(input())
    T = []
    for i in range(N):
        T.append(int(input()))
    main(N,T)
x=int(input())
l=[1]
for i in range(2,32):
  k=2
  while i**k<1000:
    l.append(i**k)
    k+=1
l=sorted(l)
for i in range(len(l)):
  if l[i]<=x<l[i+1]:
    print(l[i])
    exit()
print(961)

### FIXED CODE ###

x=int(input())
if x==1000:
  print(1000)
  exit()
l=[1]
for i in range(2,32):
  k=2
  while i**k<=1000:
    l.append(i**k)
    k+=1
l=sorted(l)
for i in range(len(l)-1):
  if l[i]<=x<l[i+1]:
    print(l[i])
    exit()
print(961)
import heapq
n,m = map(int,input().split())
L = [  -i for i in map(int, input().split())]
heapify(L)
for _ in range(m):
    heapreplace(L,L[0]//2 + L[0]%2)
print(-sum(L))

### FIXED CODE ###

from heapq import heapify, heapreplace
n,m = map(int,input().split())
L = [  -i for i in map(int, input().split())]
heapify(L)
for _ in range(m):
    heapreplace(L,L[0]//2 + L[0]%2)
print(-sum(L))