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

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            T = S[i-ki]
            if T == 'D' :
                d -= 1
                dm -= m
            elif T == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###

n,x,y = map(int,input().split())
dic = [[0 for i in range(n)]for j in range(n)]
for i in range(n):
    for j in range(i,n):
        dic[i][j] = abs(i-j)
        if i < x and y-1 <= j :
            dic[i][j] = dic[i][x-1]+1+(j-y+1)
        elif i < x and y-1 > j :
            dic[i][j] = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)))
        elif x <= i :
            dic[i][j] = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)))

ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        ans[dic[i][j]] += 1
for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

from functools import reduce

n = int(input())
v = list(map(int, input().split(' ')))

partial_sum = lambda a, b: a + [min(a[-1], b)]
mini = reduce(partial_sum, v[1:], v[0:1])

ans = 0
for i in range(len(v)):
    if (v[i] == mini[i]):
        ans += 1

print(ans)

### FIXED CODE ###

from functools import reduce

n = int(input())
v = list(map(int, input().split(' ')))

ans = 0
mini = v[0]
for i in range(len(v)):
    mini = min(mini, v[i])
    if (mini == v[i]):
        ans += 1

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

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

t = [0]*n
for i in range(n-(k-1)):
    for j in range(i,i+k):
        t[i] += p[j]
T = t.index(max(t))
ans = 0
for i in range(k):
    ans += (p[T+i]+1)/2
print(ans)

### FIXED CODE ###

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

t = [0]*n
for j in range(k):
    t[0] += p[j]
for i in range(1,n-k+1):
    t[i] = t[i-1]-p[i-1]+p[i+k-1]
T = t.index(max(t))
ans = 0
for i in range(k):
    ans += (p[T+i]+1)/2
print(ans)
### BUGGY CODE ###

import math

while True:
    try:
        n = int(input())
        c = [1 for i in range(n)]
        c[0] = 0
        i = 2
        while i**2 <= n:
            j = i*2
            while j <= n:
                c[j - 1] = 0
                j += i
            i += 1
        print(sum(c))
    except:
        break

### FIXED CODE ###

n = 999999
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        print(sum(c[:n]))
    except:
        break
### BUGGY CODE ###

a, b = map(int, (input().split()))
ans = b
for i in range(a, b):
    ans ^= i
print(ans)


### FIXED CODE ###

a, b = map(int, (input().split()))
if a % 2 ==0:
    if b % 2 ==0:
        print(int((b - a) /2 % 2) ^ b)
    else:
        print(int((b - a + 1)/2 % 2))
else:
    if b % 2 ==0:
        print(a ^ b ^ int((b - a)/2 % 2))
    else:
        print(a ^ int((b - a)/2 %2))
### BUGGY CODE ###

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

set_ID = {i for i in range(N)}

for _ in range(M):
    L, R = map(int, input().split())
    set_M = {i for i in range(L - 1, R)}
    set_ID = set_ID & set_M
    
print(len(set_ID))

### FIXED CODE ###

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

L_limit = 1
R_limit = N
for _ in range(M):
    L, R = map(int, input().split())
    L_limit = max(L_limit, L)
    R_limit = min(R_limit, R)
    
print(max(R_limit - L_limit + 1, 0))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

    ans = 0

    for i in range(N):
        for j in range(i + 1, N):
            ans += A[i] * A[j]

    print(ans % (10**9 + 7))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

    s = sum(A)
    ans = 0
    mod = 10**9 + 7
    for i in A:
        ans = (ans + i * (s - i))
    print((ans // 2) % mod)


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

N = int(input())
a = 1
for Ai in input().strip().split(' '):
    a *= int(Ai)
if a > 10**18:
    print('-1')
else:
    print(a)

### FIXED CODE ###

_ = int(input())
A = [ int(i) for i in input().strip().split(' ')]
a = 1
if min(A) == 0:
    print(0)
else:
    for Ai in A:
        a *= Ai
        if a > 10**18:
            print('-1')
            break
    else:
        print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
prebit = [0 for _ in range(20)]
prem = 0
def binl(x, accl):
    if len(accl) == 20:
        return accl
    else:
        accl.append(x%2)
        return binl(x//2, accl)
ans = 0
for i in range(1, n+1):
    m = prem+1
    b = binl(a[i-1], [])
    for j in range(20):
        if b[j] == 1:
            m = min(m, i - prebit[j])
            prebit[j] = i
    prem = m
    ans += m
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + a[i]
l = 0
r = 0
count = 0
while(r < n or l < n):
    if r < n and (cum[r] - cum[l]) & a[r] == 0:
        r += 1
    else:
        count += r - l
        l += 1
print(count)
### BUGGY CODE ###

N = int(input())

a = 0
while N > 0:
  a += N % 10
  N //= 10

if a % 9 == 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

if int(input()) % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from sys import stdin

n, *a = (int(x) for x in stdin.read().split())

count = 0
for n in set(a):
    if a.count(n) % 2 == 1: count += 1

print(count)

### FIXED CODE ###

from sys import stdin

n, *a = (int(x) for x in stdin.read().split())

each_count = {n: 0 for n in set(a)}


for n in a:
    each_count[n] += 1

count = 0
for v in each_count.values():
    if v % 2 == 1: count += 1

print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = 0
            P.append(i)
    return P

P = primes(32000)
D = defaultdict(list)

for a in A:
    for p in P:
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt:
            D[p].append(cnt)
    if a > 1:
        D[a].append(1)

D = {k:[0]*(len(v) == N-1) + sorted(v) for k, v in D.items() if len(v) >= N-1}

ori = 1
for k, v in D.items():
    ori *= k**v[0]

ans = max(ori, 1)
for a in A:
    tmp = 1 * ori
    for p in D.keys():
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt == D[p][0]:
            tmp *= p**(D[p][1] - D[p][0])
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = 0
            P.append(i)
    return P

P = set(primes(32000))
D = defaultdict(list)
C = set()
for a in A:
    removes = []
    for p in P:
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt:
            D[p].append(cnt)
        else:
            if p in C:
                removes.append(p)
            else:
                C.add(p)
    P = P - set(removes)
    if a > 1:
        D[a].append(1)

D = {k:[0]*(len(v) == N-1) + sorted(v) for k, v in D.items() if len(v) >= N-1}

ori = 1
for k, v in D.items():
    ori *= k**v[0]

ans = max(ori, 1)
for a in A:
    tmp = 1 * ori
    for p in D.keys():
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt == D[p][0]:
            tmp *= p**(D[p][1] - D[p][0])
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * pow(b[-1], p - 2, p) % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        for j in range(len(fm)):
            ans[j] += fm[j] * pow(r, p - 2, p) % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))


### FIXED CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect

input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

lis = [0] * (N+1)
lis[1] = 1

def f(v,l,k):
    if visited[v]:
        return
    visited[v] = True
    A = a[v-1]
    i = bisect.bisect_left(l,A)
    l[i] = A 
    if k < i:
        k += 1
    lis[v] = k
    #lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:],k)

l = [inf] * (N+1)
f(1,l,0)

for i in range(1,N+1):
    print(lis[i]+1)







### FIXED CODE ###

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

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

N = int(input())
T = []
for k in range(N-1):
    t = list(map(int,input().split()))
    T.append(t)

T = sorted(T, key = lambda x: x[0])
A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    c = 0
    while A[T[c][0]-1] == A[T[c][1]-1] == -1:
        c += 1
    u = T[c][0]-1
    v = T[c][1]-1
    w = T[c][2] 
    T.pop(c)
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0

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

### FIXED CODE ###

N = int(input())
T = [[] for k in range(N)]
for k in range(N-1):
    u,v,w = map(int,input().split())
    T[u-1].append([v-1,w])
    T[v-1].append([u-1,w])

kyori = [-1 for k in range(N)]
kyori[T[0][0][0]] = 0
que = [T[0][0][0]]

while len(que) > 0:
    now = que.pop()
    for tsugi in T[now]:
        if kyori[tsugi[0]] == -1:
            kyori[tsugi[0]] = kyori[now] + tsugi[1]
            que.append(tsugi[0])

for a in kyori:
    print(a%2)
### BUGGY CODE ###

def Z_Algorithm(S):
    N = len(S)
    Z = [0]*N
    Z[0] = N
    
    i = 1   #左
    j = 0   #差分

    while i < N:
        while i + j < N and S[j] == S[j + i]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue

        k = 1   # 差分
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        
        i += k
        j -= k
    
    return Z

def calc(S):
    N = len(S)
    Z = Z_Algorithm(S)

    res = 0
    for i in range(N):
        res = max(res, min(Z[i], i))
    
    return res

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

res = 0

for i in range(N):
    res = max(res, calc(S[i:]))

print(res)

### FIXED CODE ###

def Z_Algorithm(S):
    N = len(S)
    Z = [0]*N
    Z[0] = N
    
    i = 1   #左
    j = 0   #差分

    while i < N:
        while i + j < N and S[j] == S[j + i]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue

        k = 1   # 差分
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        
        i += k
        j -= k
    
    return Z

def calc(S):
    N = len(S)
    Z = Z_Algorithm(S)

    res = 0
    for i in range(N):
        res = max(res, min(Z[i], i))
    
    return res

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

res = 0

for i in range(N):
    res = max(res, calc(S[i:]))

print(res)
### BUGGY CODE ###

import bisect as bi
def main():
  from builtins import input, int, map
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort()
  C.sort()

  ans = 0

  for i in range(N):
    a = bi.bisect_left(A,B[i])
    c = len(C[bi.bisect_right(C,B[i]):])
    ans += a*c
  print(ans)
main()


### FIXED CODE ###

import bisect as bi
def main():
  from builtins import input, int, map
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort()
  C.sort()

  ans = 0

  for i in range(N):
    a = bi.bisect_left(A,B[i])
    c = N-bi.bisect_right(C,B[i])
    ans += a*c
  print(ans)
main()
### BUGGY CODE ###

def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

  dp = [[0] * 13 for i in range(N)]

  for i in range(N):
    idx = N-i-1
    if i == 0:
      if S[idx] != '?':
        dp[i][int(S[idx])] = 1
      else:
        for j in range(10):
          dp[i][j] = 1
    else:
      amari = (10 ** i) % 13
      if S[idx] != '?':
        shift = int(S[idx]) * amari % 13
        for j in range(13):
          if j+shift < 13:
            dp[i][j+shift] = dp[i-1][j]
          else:
            dp[i][j+shift-13] = dp[i-1][j]
      else:
        for k in range(10):
          shift = k * amari % 13
          for j in range(13):
            if j+shift < 13:
              dp[i][j+shift] = (dp[i][j+shift] + dp[i-1][j]) % MOD
            else:
              dp[i][j+shift-13] = (dp[i][j+shift-13] + dp[i-1][j]) % MOD

  print(dp[N-1][5])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))
### BUGGY CODE ###

r, g, b, n = map(int,input().split())
ans = 0

for i in range(n+1):
    for j in range(n+1):
        if (i*r) + (j*g) > n:
            break
        if n-(i*r)-(j*g) >= 0 and (n-(i*r)-(j*g))%b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    j = l.count(i)
    ans += int(j * (j - 1) / 2)

for i in range(n):
    ans_i = 0
    j = l.count(l[i])
    print(ans - j + 1)
    

### FIXED CODE ###

from collections import Counter

n = int(input())
l = [int(i) for i in input().split()]

S = Counter(l)

ans = 0
for i in S.values():
    ans += int(i * (i - 1) / 2)

for i in range(n):
    val = S[l[i]]
    print(ans - val + 1)
### BUGGY CODE ###

from pprint import pprint
from collections import deque
h, w = map(int, input().split())

m = deque([])
mv = deque([])
mh = deque([])

for i in range(h):
    mh.append(deque([0] * w))
for i in range(h):
    mv.append(deque([0] * w))

for i in range(h):
    m.append(input())

for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c

for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c

res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)


#pprint(mh)
#pprint(mv)


### FIXED CODE ###

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

m = list()
mv = list()
mh = list()

for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)

for i in range(h):
    m.append(input())

for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c

for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c

res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)
### BUGGY CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
#for i in range(1,max(a)+1):
for i in range(1,10**5+1):
    if not i in adic:
        adic[i]=0
        
        
q=int(input())
b=[0]*(q+1)
c=[0]*(q+1)
for i in range(q):
    bi,ci=map(int,input().split())
    b[i]=bi
    c[i]=ci
    
#print(adic)    
for i in range(q):
    adic[c[i]]=adic[c[i]]+adic[b[i]]
    adic[b[i]]=0
#    print(i,adic)
    asum=0
    for i in range(1,10**5+1):
#        asum+=a[i]*adic[a[i]]
        asum+=i*adic[i]
    print(asum)
    

### FIXED CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
bc=[[0]*2 for i in range(q)]
for i in range(q):
    bc[i]=map(int,input().split())
    
asum=0
for i,ad in adic.items():
    asum+=i*ad
    
#print(adic)    
for bi,ci in bc:
    if bi in adic and ci in adic:
        asum-=bi*adic[bi]
        adic[ci]=adic[ci]+adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        asum-=bi*adic[bi]
        adic[ci]=adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
#    print(i,adic)
    print(asum)
### BUGGY CODE ###

n = int(input())
ans = []


def xyz():
    count = 0
    for i in range(1, 110):
        for j in range(1, 110):
            for k in range(1, 110):
                zyx = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
                ans.append(zyx)


xyz()
for i in range(n):
    print(ans.count(i + 1))


### FIXED CODE ###

n = int(input())
ans = [0]*10**5


def xyz():
    count = 0
    for i in range(1, 101):
        for j in range(1, 101):
            for k in range(1, 101):
                zyx = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
                ans[zyx] += 1


xyz()
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

from collections import deque

N, M = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

stack = deque()
stack.appendleft((0, M, 0))

min_money = 10**9*10**5

while stack:
    i_t = stack.popleft()
    item_number = i_t[0]
    tickets = i_t[1]
    need_money = i_t[2]

    for use_tickets in range(tickets+1):
        if item_number + 1 <= N:
            money = A[item_number] // 2**use_tickets
            stack.appendleft((item_number+1, tickets-use_tickets,
                              need_money + money))

        else:
            min_money = min(need_money, min_money)

        if money == 0:
            break

print(min_money)


### FIXED CODE ###

import heapq

N, M = [int(x) for x in input().split()]
A = list([int(x) * - 1 for x in input().split()])
heapq.heapify(A)

for _ in range(M):
    target = heapq.heappop(A) * -1
    heapq.heappush(A, (target // 2) * -1)

print(sum(A) * -1)