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

from operator import itemgetter


def f(idx):
    ret = []
    for i in range(1 << n):
        lines = [0]
        for j in range(n):
            if i & 1:
                lines.append(xyp[j][idx])
            i >>= 1

        costs = []
        for e, p in map(itemgetter(idx, 2), xyp):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))
            costs.append(dist * p)

        ret.append(costs)

    return ret


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
for i in range(3 ** n):
    now = i
    vi = 0
    hi = 0
    power = 1
    cnt = n
    for j in range(n):
        q, r = divmod(now, 3)
        if r == 1:
            vi += power
        elif r == 2:
            hi += power
        else:
            cnt -= 1
        now = q
        power *= 2

    score = 0
    for ev, eh in zip(ver[vi], hor[hi]):
        score += min(ev, eh)

    ans[cnt] = min(ans[cnt], score)

print(*ans, sep="\n")


### FIXED CODE ###

import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")
### BUGGY CODE ###

from collections import defaultdict, deque

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                flag1 = False
                flag2 = False
                for n in range(N):
                    if S[n] == str(i) and not flag1 and not flag2:
                        flag1 = True
                        continue
                    if S[n] == str(j) and flag1 and not flag2:
                        flag2 = True
                        continue
                    if S[n] == str(k) and flag1 and flag2:
                        ans += 1
                        break


    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict, deque

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1000):
        password = str(i).zfill(3)
        j = 0
        for s in S:
            if s == password[j]:
                j += 1
            if j == 3:
                ans += 1
                break

    print(ans)


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

N=int(input())

for i in range(1,N+1):
    count=0
    for x in range(1,i+1):
        if x**2>i:break
        for y in range(1,N-(x**2)+1):
            if x**2+y**2>i:break
            for z in range(1,N-(x**2+y**2)+1):
                if x**2+y**2+z**2+x*y+y*z+x*z==i:count+=1
    print(count)

### FIXED CODE ###

N=int(input())
dic={}
for i in range(1,N+1):
    dic[i]=0
for x in range(1,int(N**0.5)):
    for y in range(1,N-x**2):
        for z in range(1,N-(x**2+y**2+x*y)):
            if x**2+y**2+z**2+x*y+x*z+y*z>N:break
            if x**2+y**2+z**2+x*y+x*z+y*z in dic:
                dic[x**2+y**2+z**2+x*y+x*z+y*z]+=1


for i in range(1,N+1):
    print(dic[i])
### BUGGY CODE ###

import math
a=int(input())
b=[]
ans=0
for i in range(2,a,1):
  cnt=0
  if a%i==0:
    while a%i==0:
      cnt+=1
      a=a/i
    ans+=(math.sqrt(2*cnt+0.25)-0.5)//1
print(int(ans))

### FIXED CODE ###

import math
a=int(input())
ans=0
for i in range(1,int(math.sqrt(a)),1):
  if a%i==0 and not i==1:
    cnt=0
    while a%i==0:
      cnt+=1
      a=a/i
    ans+=(math.sqrt(2*cnt+0.25)-0.5)//1
if not a==1:
  print(int(ans+1))
else:
  print(int(ans))
### BUGGY CODE ###

N, X = map(int, input().split())
cities = [int(i) for i in input().split()]
cities.sort()
dist = [int(abs(i-X)) for i in cities]
dist.sort()

if N==1:
    print(max(dist))
else:
    m = min(dist)
    dist.remove(m)
    dist_2 = [int(i%m) for i in dist]
    dist_2.sort()
    while len(dist_2)>0 and dist_2[0]==0:
        dist_2.remove(0)
    dist_2.append(m)
    D = max(dist_2)
    for i in reversed(range(1, D+1)): #最大公約数を1から順に考える
        for j in range(len(dist_2)): #全ての数を割ってみる
            if dist_2[j]%i != 0:
                flag = False
                break
            else:
                flag = True
        if flag:
            D = i
            break
    print(D)

### FIXED CODE ###

N, X = map(int, input().split())
cities = [int(i) for i in input().split()]
cities.sort()
dist = [int(abs(i-X)) for i in cities]
dist.sort()
 
if N==1:
    print(max(dist))
else:
    while len(dist)>0:
        m = min(dist)
        dist = [int(i%m) for i in dist]
        dist.sort()
        while len(dist)>0 and dist[0]==0:
            dist.remove(0)
        if len(dist)==0:
            break
        else:
            dist.append(m)
    print(m)
### BUGGY CODE ###

import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque([])
q.append([h,w])
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft([hwalk,wwalk])
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append([hwalk,wwalk])
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

n, k = map(int, input().split())
p = map(int, input().split())
p_e = list(map(lambda x: (x + 1)* 0.5, p))

e_sum = [sum(p_e[i:i+k]) for i in range(n - k + 1)]
print(max(e_sum))

### FIXED CODE ###

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

p_e = [0] + [ (x + 1) * 0.5 for x in p]
p_p = [0]

for i in range(1, n+1):
    p_p.append(p_p[i-1] + p_e[i])

e_sum = [p_p[i] - p_p[i - k] for i in range(k, n+1)]
print(max(e_sum))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
#print(tree)

answer=1
visited=[False]*(N+1)
def dfs(node,depth,cind):
  #print(node,depth,cind)
  global answer
  visited[node]=True
  
  if depth==0:
    answer*=K
    answer%=mod
  elif depth==1:
    answer*=K-1-cind
    answer%=mod
  else:
    answer*=K-2-cind
    answer%=mod
  
  next_nodes=tree[node]
  i=0
  for nn in next_nodes:
    if not visited[nn]:
      dfs(nn,depth+1,i)
      i+=1

node=1
dfs(node,0,0)
print(answer)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
#print(tree)

answer=1
visited=[False]*(N+1)
def dfs(node,depth,cind):
  #print(node,depth,cind)
  global answer
  visited[node]=True
  
  if depth==0:
    answer*=K
    answer%=mod
  elif depth==1:
    answer*=K-1-cind
    answer%=mod
  else:
    answer*=K-2-cind
    answer%=mod
  
  next_nodes=tree[node]
  i=0
  for nn in next_nodes:
    if not visited[nn]:
      dfs(nn,depth+1,i)
      i+=1

node=N//2
dfs(node,0,0)
print(answer)
### BUGGY CODE ###

# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
s = input()
n = len(s)
dp = [0] * n
mod = 2019
for i in range(n):
    m = int(s[i]) * pow(10, n - i - 1, mod) % mod
    dp[i] = m

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

ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        total = dp[j] - dp[i]
        if total % mod == 0:
            ans += 1
print(ans)

### FIXED CODE ###

# int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

def nC2(n):
    return n * (n - 1) // 2
s = input()
n = len(s)
dp = [0] * 2020
mod = 2019
temp = 0
dp[0] = 1
for i in range(n):
    m = (int(s[i]) * pow(10, n - i - 1, mod) + temp)% mod
    dp[m] += 1
    temp = m
ans = 0
for i in range(2020):
    if dp[i]:
        ans += nC2(dp[i])
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
Am = sorted(A, reverse = True)
m = Am[0] + Am[1]
ct = 0
for i in range(n):
    for j in range(i, n):
        if j - i > m:
            break
        elif j - i == A[i] + A[j]:
            ct += 1
print(ct)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
dic = {}
ans = 0
for i in range(n):
    L = i + A[i]
    if L not in dic:
        dic[L] = 1
    else:
        dic[L] += 1
for j in range(n):
    R = j - A[j]
    if R in dic:
        ans += dic[R]
print(ans)
### BUGGY CODE ###

#for _ in range(int(input())):
n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
for i in range(1,k):
  ans[i]=ans[i-1]*x[i]
c=0
for i in range(k,n):
  ans[i]=(ans[i-1]//x[c])*x[i]
  c+=1

ans=ans[k-1:]

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

### FIXED CODE ###


n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
c=0
for i in range(k,n):

  if x[c]<x[i]:
    print('Yes')
  else:print('No')
  c+=1
### BUGGY CODE ###

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    S = input()

    return N, S


def main(N: int, S: str) -> None:
    """
    メイン処理

    Args:\n
        N (int): 桁数
        S (str): ラッキーナンバー
    """
    # 求解処理
    ans = 0
    for n in range(1000):
        V = str(n).zfill(3)
        f = 0
        for j in range(N):
            if S[j] == V[f]:
                f += 1
            if f == 3:
                break
        ans += (f == 3)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, S = get_input()

    # メイン処理
    main(N, S)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
S = input()

# 求解処理
ans = 0
x_bit = [False for n in range(10)]
for x in range(N):
    S_x = int(S[x])
    if x_bit[S_x]:
        continue
    x_bit[S_x] = True
    y_bit = [False for n in range(10)]
    for y in range(x + 1, N):
        S_y = int(S[y])
        if y_bit[S_y]:
            continue
        y_bit[S_y] = True
        z_bit = [False for n in range(10)]
        for z in range(y + 1, N):
            S_z = int(S[z])
            if z_bit[S_z]:
                continue
            z_bit[S_z] = True
            ans += 1

# 結果出力
print(ans)
### BUGGY CODE ###

N,K = [int(c) for c in input().split()]
h = [int(c) for c in input().split()]

dp=[0]*N
for i in range(1,N):
    dp[i]=dp[i-1]+abs(h[i]-h[i-1])
    for j in range(1,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 ###

N,K = [int(c) for c in input().split()]
h = [int(c) for c in input().split()]

dp=[0]*N
for i in range(1,N):
    dp[i]=dp[i-1]+abs(h[i]-h[i-1])
    for j in range(1,K+1):
        if i-j>=0:
            dp[i]=min([dp[i],dp[i-j]+abs(h[i]-h[i-j])])
            
print(dp[N-1])
### BUGGY CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 15
d = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = []
for i in range(4):
    d[x1][y1][i] = 0
    heappush(que, (0, x1, y1, i))
    
while len(que):
    dist, cur_x, cur_y, dir = heappop(que)
    if d[cur_x][cur_y][dir] < dist:
        continue
    if cur_x == x2 and cur_y == y2:
        break
    for i, (dx, dy) in enumerate(move):
        memo = dist
        if i != dir:
            memo = -(-dist // k) * k
            
        to_x, to_y = cur_x + dx, cur_y + dy
        if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
            if d[to_x][to_y][i] > memo + 1:
                d[to_x][to_y][i] = memo + 1
                heappush(que, (memo + 1, to_x, to_y, i))


if all(d[x2][y2][i] == inf for i in range(4)):
    print(-1)
else:
    print(-(-min(d[x2][y2]) // k))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
        a = int(input())
        A.append(a)

for i in range(N):
        B = A[:i] + A[i+1:]
        print(max(B))

### FIXED CODE ###

import numpy as np

N = int(input())
A = []
for i in range(N):
        a = int(input())
        A.append(a)
 
idx = np.argmax(np.array(A))
idx2 = np.argmax(np.array(A[:idx] + A[idx+1:]))
if idx2 >= idx:
        idx2 += 1

for i in range(N):
        if i != idx:
                print(A[idx])
        else:
                print(A[idx2])
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += max(0, bisect_left(l[j+1:], l[i]+l[j]))

print(c)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
 
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += bisect_left(l, l[i]+l[j]) - j - 1
 
print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
lis = list(map(int, input().split()))
p = 1000000007
fac_lis = [[0] for i in range(N)]
fac_lis[0] = 1
max_ans = 0
min_ans = 0

for i in range(1,N):
  fac_lis[i] = fac_lis[i-1]*(i+1)

def combi(n,k):
  if n == k:
    return 1
  else:
  	return fac_lis[n-1]*pow(fac_lis[k-1], p-2, p)*pow(fac_lis[n-k-1], p-2, p) % p

lis.sort()
for i in range(K-1,N):
  max_ans += lis[i]*combi(i, K-1)
  max_ans %= p
  
for i in range(N-K+1):
  min_ans += lis[i]*combi(N-(i+1), K-1)
  min_ans %= p

ans = (max_ans - min_ans) % p
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
### BUGGY CODE ###

# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)


### FIXED CODE ###

# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans
n = int(input())
a = list(map(int, input().split()))
max = 0
if n < 5:
    for i in range(0,n):
        p = a.pop(0)
        x = list_euclid(a)
        if max < x:
            max = x
        a.append(p)
else:
    for i in range(0,n):
        p = a.pop(0)
        k = n // 2
        y = list_euclid(a[0:k])
        z = list_euclid(a[k:n-1])
        x = euclid(y, z)
        if max < x:
            max = x
        a.append(p)
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))

    for _ in range(m):
        i = a_list.index(max(a_list))
        a_list[i] = int(a_list[i]/2)

    print(sum(a_list))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq


def main():
    n, m = map(int, input().split())
    a_list = list(map(lambda x: -int(x), input().split()))

    heapq.heapify(a_list)
    for _ in range(m):
        a = heapq.heappop(a_list)
        heapq.heappush(a_list, -(-a // 2))

    print(-sum(a_list))


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

from sys import stdin
A, B = [int(x) for x in stdin.readline().rstrip().split()]
cnt = 0
for i in range(A, B + 1):
    cnt = cnt ^ i
print(cnt)

### FIXED CODE ###

from sys import stdin
A, B = [int(x) for x in stdin.readline().rstrip().split()]
def binary_(A):
    A += 1
    n = 0
    ans = 0
    while 2 ** n <= A:
        a = 2 ** n
        a_ = a * 2
        b = A // a_
        b = b * a
        c = A % a_
        if c > a:
            d = (b + c - a) % 2
            ans += a * d
        elif c == 0:
            d = b % 2
            ans += a * d
        else:
            d = b % 2
            ans += a * d
        n += 1
    return ans
print(binary_(A-1) ^ binary_(B))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
K -= 1
A = list(map(lambda x: int(x) - 1, input().split()))
seen = []
now = 0
for i in range(N):
    seen.append(now)
    to = A[now]
    now = to
    if now in seen:
        seen.append(now)
        break
loop_s = seen.index(now)
loop_end = loop_s + seen[loop_s + 1:].index(now) + 1
size = loop_end - loop_s
if K <= loop_s:
    print(seen[K+1] + 1)
else:
    K -= loop_s
    seen = seen[loop_s + 1:]
    print(seen[K%size] + 1)

### FIXED CODE ###

N, K = list(map(int, input().split()))
K -= 1
A = list(map(lambda x: int(x) - 1, input().split()))
seen = [None]*N
seen_set = set()
now = 0
for i in range(N):
    seen[i] = now
    seen_set.add(now)
    to = A[now]
    now = to
    if now in seen_set:
        seen[i+1] = now
        loop_s = seen.index(now)
        loop_end = i + 1
        size = loop_end - loop_s
        break
if K <= loop_s:
    print(seen[K+1] + 1)
else:
    K -= loop_s
    print(seen[loop_s + 1 + K % size] + 1)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input()) 
a=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      a=a+gcd(i,j,l)
print(a)
      

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input()) 
a=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      a=a+gcd(i,j,l)
print(a)
### BUGGY CODE ###

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

floor_floor = []
for x in range(N+1):
    floor_floor.append((A*x)//B - A*(x//B))

print(max(floor_floor))


### FIXED CODE ###

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


if N//B == 0:
    ans_i = N
else :
    ans_i = B*(N//B)-1

print((A*ans_i)//B - A*(ans_i//B))
### BUGGY CODE ###

n,m,q = map(int, input().split())
List = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
  l,r = map(int, input().split())
  for j in range(l):
    for k in range(r - 1, n):
      List[j][k] += 1
for i in range(q):
  a, b = map(int, input().split())
  print(List[a - 1][b - 1])

### FIXED CODE ###

n,m,q = map(int, input().split())
List1 = [[0 for i in range(n+1)] for j in range(n+1)]
List2 = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
  l,r = map(int, input().split())
  List1[l - 1][r - 1] += 1


for i in range(n):
  for j in range(n - i):
    List2[j][j + i] = List2[j + 1][j + i] + List2[j][j + i - 1] - List2[j + 1][j + i - 1] + List1[j][j + i]


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])