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

def search_by_hash(s1, s2):
    tg = hash(bytes(s2, 'utf8'))
    sb = memoryview(bytes(s1, 'utf8'))
    l1, l2 = len(s1), len(s2)

    for i in range(l1-l2+1):
        h = hash(sb[i:i+l2])
        if h == tg:
            yield i

def run():
    s1 = input()
    s2 = input()
    for idx in search_by_hash(s1, s2):
        print(idx)


if __name__ == '__main__':
    run()


### FIXED CODE ###

class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


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

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

def solv_quadratic_equation(a, b, c):
    """ 2次方程式を解く  """
    D = (b**2 - 4*a*c)
    
    if D<0:
        return None,None
    D = D ** (1/2)
    x_1 = (-b + D) / (2 * a)
    x_2 = (-b - D) / (2 * a)

    return x_1, x_2

N=one_int()

def solve(n):
    ret = []
    X=int(n**(1/2) +0.5)+1
    Y=int(n**(1/2) +0.5)+1 
    Z=int(n**(1/2) +0.5)+1
    for x in range(1,X):
        for y in range(1,Y):
#             ans1, ans2 = solv_quadratic_equation(1, y+x, x**2 + y**2 + x*y -n)
#             if ans1 is None:
#                 continue
            for z in range(1,Z):
                if (x**2 + y**2 + z**2 + y*z + x*y + z*x)==n:
                    ret.append((x,y,z))
    return len(set(ret))

for i in range(1,N+1):
    print(solve(i))

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()

def solve(n):
    ret = {i:[] for i in range(n+1)}
    X=int(n**(1/2) +0.5)+1
    Y=int(n**(1/2) +0.5)+1 
    Z=int(n**(1/2) +0.5)+1
    for x in range(1,X):
        for y in range(1,Y):
            d = x**2+y**2+x*y
            for z in range(1,Z):
                if n < d+z**2 + y*z + z*x:
                    continue
                ret[d+z**2 + y*z + z*x].append((x,y,z))
    return ret

ret = solve(N)
for i in range(1,N+1):
    print(len(set(ret[i])))
### BUGGY CODE ###

import math
import numpy as np

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

a, b = a[::-1], b[::-1]
a = np.array(a)

dif = 0
ans = 0
for i in range(n):
    if a[i] % b[i] != 0:
        dif =  math.ceil(a[i]/b[i]) * b[i] - a[i]
        ans += dif
        a[i:] += dif

print(ans)

### FIXED CODE ###

n = int(input())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0
for i in range(n-1, -1, -1):
    if (A[i]+ans) % B[i] == 0:
        continue
    else:
        ans += B[i] - (A[i]+ans) % B[i]
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
res = 0
if max(len(r),len(g),len(b)) == len(r):
  for i in g:
    for j in b:
      res += len(r) - r.count((i + j) / 2) - r.count( 2 * i - j) - r.count(2 * j - i)
else:
  for i in b:
    for j in r:
      res += len(g) - g.count((i + j) / 2) - g.count( 2 * i - j) - g.count(2 * j - i)
print(res)


### FIXED CODE ###

n=int(input())
s=input()
R=[]
G={}
B=[]
for i in range(n):
  if s[i]=='R':
    R.append(i+1)
  elif s[i]=='G':
    G[i+1]=G.get(i+1,0)+1
  else:
    B.append(i+1)
res=len(R)*len(G)*len(B)
for i in R:
  for j in B:
    if ((i+j)%2==0 and G.get((i+j)//2,0)==1):
      res-=1
    if G.get(2*max(i,j)-min(i,j),0)==1:
      res-=1
    if G.get(2*min(i,j)-max(i,j),0)==1:
      res-=1
print(res)
### BUGGY CODE ###

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

A.sort()

#変えられるカードを格納
change_card = []
for _ in range(M):
    B,C = map(int,input().split())
    for _ in range(B):
        change_card.append(C)

change_card.sort()

for i in range(N):
    if max(change_card) > A[i]:
        A[i] = max(change_card)
        change_card[change_card.index(max(change_card))] = -1

print(sum(A))

### FIXED CODE ###

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

A.sort()

BC = [list(map(int,input().split())) for _ in range(M)]
#変えられるカードを格納
BC_sort = sorted(BC,key=lambda x: x[1])

BC_sort_index = M-1

for i in range(N):
    if BC_sort[BC_sort_index][1] > A[i]:
        A[i] = BC_sort[BC_sort_index][1]
        BC_sort[BC_sort_index][0] -= 1
        if BC_sort[BC_sort_index][0] == 0:
            BC_sort_index -= 1
            if BC_sort_index < 0:
                break

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

n = int(input())
s = input()
l = [0,1,2,3,4,5,6,7,8,9]
ans = 0
for i in l:
    for j in l:
        for k in l:
            a,b,c = i,j,k
            # print(a,b,c)
            for m in s:
                # print(m)
                if a==int(m):
                    # print(i)
                    a = -1
                elif a==-1 and b==int(m):
                    b = -1
                elif b==-1 and c==int(m):
                    ans+=1
                    # print(i,j,k)
                    break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
l = [0,1,2,3,4,5,6,7,8,9]
ans = 0
for i in l:
    for j in l:
        for k in l:
            a,b,c = i,j,k
            # print(a,b,c)
            for m in s:
                # print(m)
                if a==int(m):
                    # print(i)
                    a = -1
                elif a==-1 and b==int(m):
                    b = -1
                elif b==-1 and c==int(m):
                    ans+=1
                    # print(i,j,k)
                    break
print(ans)
### BUGGY CODE ###

from collections import deque

N, Q = map(int, input().split())
T = [[0, deque(), deque()] for _ in range(N+1)] #counter, parents, children
E = [list(map(int, input().split())) for _ in range(N-1)]
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)
### BUGGY CODE ###

from heapq import heappop, heappush
import numpy as np

import sys
input = sys.stdin.buffer.readline


def main():

    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    ds = [int(input()) for _ in range(q)]
    INF = 10 ** 18
    START = 1
    END = 0

    tfdi = []
    for i, (s, t, x) in enumerate(stx):
        t_start = max(0, s - x)
        t_end = max(0, t - x)
        if t_end == 0:
            continue

        tfdi.append([t_start, START, x, i])
        tfdi.append([t_end, END, x, i])

    tfdi.append([INF, START, INF, -1])
    tfdi.sort()

    hp = [[INF, -1]]
    ts = []
    dists = []
    t_prev = -1
    passed = set()
    for t, f, d, i in tfdi:
        if t != t_prev:
            ts.append(t_prev)
            while hp[0][1] in passed:
                heappop(hp)

            dists.append(hp[0][0])

        if f == START:
            heappush(hp, [d, i])
        else:
            passed.add(i)

        t_prev = t

    ts = np.array(ts, np.int64)
    ds = np.array(ds, np.int64)
    dists = np.array(dists, np.int64)

    idx = np.searchsorted(ts, ds, "right") - 1
    ans = dists[idx]
    ans[ans==INF] = -1
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

INF = 10 ** 9 + 1

stx.sort(key=lambda x: x[2])

nxt = [-1] * q
ans = [-1] * q

for s, t, x in stx:
    l = bisect_left(d, s - x)
    r = bisect_left(d, t - x)

    while l < r:
        if nxt[l] == -1:
            ans[l] = x
            nxt[l] = r
            l += 1
        else:
            l = nxt[l]

print(*ans, sep="\n")
### BUGGY CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

geta = 10**6        
Q = [-(B[i]*geta+i) for i in range(N)] + [0]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = divmod(-hpp(Q), geta)
    bsec = Q[0]
    bsec = (-bsec)//geta
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = (1+(b-bsec)//bside)
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, -(B[idx]*geta+idx))
print(ans)


### FIXED CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

geta = 10**6        
Q = [-(B[i]*geta+i) for i in range(N)] + [0]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = divmod(-hpp(Q), geta)
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = 1+(b-bside)//bside
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, -(B[idx]*geta+idx))
print(ans)
### BUGGY CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

    r1, c1, r2, c2 = map(int, input().split())

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

    ans = 0
    for r in range(r1, r2 + 1):
        ans = (ans + nCr(r + c2 + 1, r + 1) - nCr(r + c1 - 1 + 1, r + 1)) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# http://drken1215.hatenablog.com/entry/2020/02/09/225000

class Calc:
    def __init__(self, *, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def factorial(self, n):
        return self.fact[n]


def main():
    mod = 10 ** 9 + 7

    r1, c1, r2, c2 = map(int, input().split())

    cl = Calc(max_value=r2 + c2 + 1, mod=mod)

    ret = 0
    for r in range(r1, r2 + 1):
        ret += cl.combination(r + c2 + 1, r + 1)
        ret -= cl.combination(r + (c1 - 1) + 1, r + 1)
        ret %= mod

    print(ret)


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

n, x, y = map(int, input().split())
ans = [0] * (n - 1)
x -= 1
y -= 1
for i in range(n-1):
    for j in range(i+1, n):
        d = min(abs(y-i)+abs(y-j), abs(x-i)+abs(x-j), abs(i-j),
                abs(y-i)+abs(x-j)+1, abs(x-i)+abs(y-j)+1) - 1
        if i == x and j == y:
            d = 0
        # print(i, j, d)
        ans[d] += 1
print(*ans, sep='\n')


### FIXED CODE ###

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

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [[] for i in range(n)]
    flag = 0
    for i in range(n):
        s[i] = raw_input()
    for i in range(n,0,-1):
        for j in range(n-i+1):
            for k in range(n-i+1):
                out = ""
                for l in range(i):
                    for m in range(i):
                        out += s[j+l][k+m]
                if out.count("*") == 0:
                    print i
                    flag = 1
                if flag == 1: break
            if flag == 1: break
        if flag == 1: break
    if flag == 0:
        print 0

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))
### BUGGY CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

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

N, P = map(int, input().split())
S = input()
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]*P
    list_a[0]+=1
    counter=0
    for i in range(len(S)):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
    print(counter)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
for i in range(N):
    if S[i]=="R":
        r.append(i)
    elif S[i]=="G":
        g.append(i)
    elif S[i]=="B":
        b.append(i)
t=0
for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            if abs(r[i]-g[j])!=abs(b[k]-g[j]) and abs(r[i]-b[k])!=abs(b[k]-g[j]) and abs(r[i]-g[j])!=abs(b[k]-r[i]):
                t=t+1
print(t)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

X.sort(key=lambda x: x[0])

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while X[j][0] < 2*q:
#        print(X[j])
        _, f, x = X[j]
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
#    print(ll, j)
#    print(d, ll)
#    j -= 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

S = list(input())
N = len(S)
ans = 0
num = S.count('B')
check = ['W']*(N-num) + ['B']*num

while S != check:
    for i in range(1, N):
        if S[i-1] == 'B' and S[i] == 'W':
            S[i-1], S[i] = 'W', 'B'
            ans += 1

print(ans)

### FIXED CODE ###

S = input()
N = len(S)
ans = 0

cnt_B = S.count('B')
idx_B = N - cnt_B

for i in range(N):
    if S[i] == 'B':
        ans += idx_B - i
        idx_B += 1

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

N=int(input())
p=list(map(float,input().split()))

DP=[0 for i in range(N+1)]
DP[0]=10**12
for i in range(N):
    #DP[0]=1
    for j in range(N+1):
        if DP[N-j]>0:
            DP[N-j+1]+=DP[N-j]*p[i]
            DP[N-j]*=(1-p[i])
    #print(DP)
print(sum(DP[N//2+1:])/(10**12))

### FIXED CODE ###

N=int(input())
p=list(map(float,input().split()))

DP=[0 for i in range(N+1)]
DP[0]=10**12
for i in range(N):
    #DP[0]=1
    for j in range(N+1):
        if DP[N-j]>0:
            DP[N-j+1]+=DP[N-j]*p[i]
            DP[N-j]*=(1-p[i])
    #print(DP)
print(sum(DP[N//2+1:])/(10**12))
### BUGGY CODE ###

N = int(input())
A = sorted([int(input()) for i in range(N)])
ans1 = [A[N-1]]
ans2 = [A[0]]

f = 0
b = N - 2
s = True
while f <= b:
    if s:
        ans1 = ans1 + [A[f]]
        f += 1
        if f <= b:
            ans1 = [A[f]] + ans1
            f += 1
    else:
        ans1 = ans1 + [A[b]]
        b -= 1
        if f <= b:
            ans1 = [A[b]] + ans1
            b -= 1
    s = not s

f = 1
b = N - 1
s = True
while f <= b:
    if s:
        ans2 = ans2 + [A[b]]
        b -= 1
        if f <= b:
            ans2 = [A[b]] + ans2
            b -= 1
    else:
        ans2 = ans2 + [A[f]]
        f += 1
        if f <= b:
            ans2 = [A[f]] + ans2
            f += 1
    s = not s

a1 = a2 = 0
for i in range(N-1):
    a1 += abs(ans1[i] - ans1[i+1])

for i in range(N-1):
    a2 += abs(ans2[i] - ans2[i+1])

print(max(a1,a2))

### FIXED CODE ###

N = int(input())
A = sorted([int(input()) for i in range(N)])

a = [0] * N
b = [0] * N
j = 1

for i in range(N-1):    
    a[i] += -j
    a[i+1] += j
    b[i] += j
    b[i+1] += -j    
    j = -j

a.sort()
b.sort()
s1 = sum([i*j for i,j in zip(a, A)])
s2 = sum([i*j for i,j in zip(b, A)])
print(max(s1,s2))
### BUGGY CODE ###

h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
map1=[[0]*w for i in range(h)]
map2=[[0]*w for i in range(h)]
for i in range(h):
  count=0
  for j in range(w):
    if data[i][j]=="#":
      count=0
    else:
      count+=1
      map1[i][j]=count
  count=0
  for j in range(w):
    if map1[i][-1-j]==0:
      count=0
    else:
      if count==0:count=map1[i][-1-j]
      map1[i][-1-j]=count
for i in range(w):
  count=0
  for j in range(h):
    if data[j][i]=="#":
      count=0
    else:
      count+=1
      map2[j][i]=count
  count=0
  for j in range(h):
    if map2[-j-1][i]==0:
      count=0
    else:
      count=max(map2[-j-1][i],count)
      map2[-j-1][i]=count
ans=0
for i in range(h):
  for j in range(w):
    tmp=map1[i][j]+map2[i][j]
    ans=max(ans,tmp)
print(ans-1)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
range_w=range(w)
range_h=range(h)
for i in range_h:
  tmp_1=0
  tmp_2=0
  for j in range_w:
    if s[i][j]=="#":
      tmp_1=0
    else:
      tmp_1+=1
    score[i][j]+=tmp_1
    
    if s[i][-j-1]=="#":
      tmp_2=0
    else:
      tmp_2+=1
    score[i][-j-1]+=tmp_2
    
for j in range_w:
  tmp_3=0
  tmp_4=0
  for i in range_h:
    if s[i][j]=="#":
      tmp_3=0
    else:
      tmp_3+=1
    score[i][j]+=tmp_3
    
    if s[-i-1][j]=="#":
      tmp_4=0
    else:
      tmp_4+=1
    score[-i-1][j]+=tmp_4-3
for i in range(h):
  for j in range(w):
    ans=max(ans,score[i][j])
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
al = list(map(int, input().split()))
for i in range(m):
  al.sort()
  al[n - 1] //= 2
print(sum(al))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
al = list(map(lambda x: (-1) * int(x), input().split()))
heapq.heapify(al)

for _ in range(m):
    al_min = heapq.heappop(al)
    heapq.heappush(al, (-1) * (-al_min // 2))

print(-sum(al))