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

x,y,z,K = map(int,input().split())
ans = 0
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i+1)*(j+1)*(k+1)<=K:
                ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

x,y,z,K = map(int,input().split())
ans = 0
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ans = []
for i in range(x):
    for j in range(min(K//(i+1),y)):
        for k in range(min(z,K//((i+1)*(j+1)))):
            if (i+1)*(j+1)*(k+1)<=K:
                ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
robot = []
for _ in range(n):
    x, l = map(int, input().split())
    arm_left = x - l
    arm_right = x + l
    robot.append([arm_left, arm_right])

robot.sort(key=lambda x: x[1])
count = 0
while True:
    if len(robot) == 0:
        break
    count += 1
    current_right = robot[0][1]
    robot = [i for i in robot if i[0] >= current_right]

print(count)

### FIXED CODE ###

n = int(input())
robot = []
for _ in range(n):
    x, l = map(int, input().split())
    arm_left = x - l
    arm_right = x + l
    robot.append([arm_left, arm_right])

robot.sort(key=lambda x: x[1])
count = 0
current_right = -1000000000
for i in range(n):
    if robot[i][0] >= current_right:
        count += 1
        current_right = robot[i][1]

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

from collections import deque
import sys
input = sys.stdin.readline

N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append([next_playerA,next_playerB])
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit, number remain(not 0 exists)
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1)
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)


### FIXED CODE ###

from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [deque(list(map(lambda x :int(x)-1, input().split()))) for _ in range(N)]

day = 0
candidates = set(range(N))
while len(candidates)>0:
    day += 1
    nextday = set()
    checked = set()
    #print(candidates)
    for candidate in candidates:
        if len(A[candidate]) == 0:
            continue
        if candidate in checked:
            continue
        opponent = A[candidate][0]
        if opponent in checked:
            continue
        if A[opponent][0] == candidate:
            A[opponent].popleft()
            A[candidate].popleft()
            nextday.add(candidate)
            nextday.add(opponent)
            checked.add(candidate)
            checked.add(opponent)
    candidates = nextday

for p in A:
    if len(p) > 0:
        print(-1)
        break
else:
    print(day-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(ans)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
### BUGGY CODE ###

#lの位置は線形探索、rの位置はさぶたん
N, C = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(N)]
csv = [0] * (N + 1)
s.sort()
for i in range(N):
  csv[i + 1] = csv[i] + s[i][1]
res = 0
for l in range(N):
  rlim = N - 1
  llim = 0
  x1 = (rlim - llim) // 3
  x2 = 2 * x1
  while x2 - x1 > 3:
    x1 = (rlim - llim) // 3
    x2 = 2 * x1
    xres = [0, 0]
    i = 0
    #print(x1, x2)
    for r in (x1, x2):
      if l > r:
        a = (C - s[l][0]) * 2 + s[r][0]
        b = (C - s[l][0]) + s[r][0] * 2
        xres[i] = csv[r + 1] + (csv[-1] - csv[l]) - min(a, b)
      else:
        xres[i] = csv[r + 1] - csv[l] - s[r][0]
      i += 1
    #print(xres)
    if xres[0] > xres[1]:
      res = max(xres[0], res)
      rlim = x2
    else:
      res = max(xres[1], res)
      llim = x1
  for r in range(llim, rlim + 1):
    if l > r:
      a = (C - s[l][0]) * 2 + s[r][0]
      b = (C - s[l][0]) + s[r][0] * 2
      res = max(res, csv[r + 1] + (csv[-1] - csv[l]) - min(a, b))
    else:
      res = max(res, csv[r + 1] - csv[l] - s[r][0])
print(res)

### FIXED CODE ###

from itertools import accumulate as acc
N, C = map(int, input().split())
ds, vs = [], []
for i in range(N):
  d, v = map(int, input().split())
  ds.append(d)
  vs.append(v)
rvcs = list(acc(vs))
lvcs = list(acc(vs[:: -1]))
rds = ds
lds = [C - d for d in ds[:: -1]]
re = [v - d for d, v in zip(rds, rvcs)]
le = [v - d for d, v in zip(lds, lvcs)]
remax = [0]
lemax = [0]
for i in range(N):
  remax.append(max(remax[-1], re[i]))
  lemax.append(max(lemax[-1], le[i]))
res = 0
#i個のスシを補給する時、右回り直進、左回り直進、右回り反転左回り、左回り反転右回りがある
#反転の際はエネルギー累積maxを使わないと同じスシを２回食べちゃうかも
#反転しない際は取れるだけ取らせてみてもいい
for i in range(N):
  res = max(res, re[i], le[i], re[i] + lemax[N - i - 1] - rds[i], le[i] + remax[N - i - 1] - lds[i])
print(res)
### BUGGY CODE ###

n = int(input())
x = input()

val = 0
rui = 1
mod = 0

nagasa = 2*10**5+1
#nagasa = 5
d_li = [0]*(nagasa)

for i in range(1,nagasa):
    t_v = i
    t_m = bin(t_v).count("1")
    ans = 0
    while t_v != 0:
        if d_li[t_v] != 0:
            ans += d_li[t_v]
            break
        ans += 1
        t_v %= t_m
        #t_m = bin(t_v).count("1")
    d_li[i] = ans

#print(d_li)
#exit()
"""
for i in range(n):
    val += int(x[n-1-i])*rui
    rui *= 2
"""
val = int(x, 2)
#print(val)
#exit()

mod = bin(val).count("1")

rui = 1
ans_li = []
    
for i in range(n):
    t_v = val
    t_m = mod
    if int(x[n-1-i]) == 1:
        t_v -= rui
        t_m -= 1
    else:
        t_v += rui
        t_m += 1
    rui *= 2
    ans = 0
    #while t_v != 0:
    if t_v != 0:
        t_v %= t_m
        ans += 1
    
    ans += d_li[t_v]
    #t_m = bin(t_v).count("1")
    ans_li.append(ans)
    #print(ans_li)

#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])


### FIXED CODE ###

def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        #t_v = val
        #t_m = mod
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                #t_v -= rui % (mod-1)
                t_v %= (mod-1)
                ans += 1
                #t_m -= 1
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            #print(t_v,rui)
            #t_v += rui % (mod+1)
            t_v %= (mod+1)
            ans += 1
            #t_m += 1
        rui //= 2
        #print(t_v,mod)
        #while t_v != 0:
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            #t_v %= t_m
            ans += 1
        """
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""
### BUGGY CODE ###

s = str(input())
n = int(input())
q_list = [list(map(str, input().strip().split())) for i in range(n)]

for q in q_list:
    if q[0] == '1':
        s = s[::-1]
    elif q[1] == '1':
        s = q[2] + s
    else:
        s = s + q[2]
print(s)


### FIXED CODE ###

s = str(input())
n = int(input())
q_list = [list(map(str, input().strip().split())) for i in range(n)]

rev = 0
for_s = ''
rev_s = ''

out = ''
for q in q_list:
    if q[0] == '1':
        rev = 1 - rev
    elif q[1] == '1':
        if rev == 0:
            rev_s += q[2]
        else:
            for_s += q[2]
    else:
        if rev == 0:
            for_s += q[2]
        else:
            rev_s += q[2]

if rev == 0:
    out = rev_s[::-1] + s + for_s
else:
    out = for_s[::-1] + s[::-1] + rev_s
print(out)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
ans = 0
for n in range(a, b+1):
    ans = ans ^ n
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
a, b = map(int, input().split())
a-=1
ans = [a,1,a+1,0][a%4]^[b,1,b+1,0][b%4]
print(ans)
### BUGGY CODE ###

M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
for _ in'_'*input():
 a=input();s+=a;i=s
 while~i:d[i]+=d[i-a]*2%M;e[i]+=e[i-a]%M;i-=1
print(sum(d)+~s%2*e[s/2]*3-3*sum(d[:s/2+1]))%M

### FIXED CODE ###

M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[i+1]*3)%M
### BUGGY CODE ###

import math
N = int(input())


def combination(n, r):
    if n >= 2:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0

A = input().split()
B = []
C = []
for i in range(N):
    B.append(combination(A.count(str(i + 1)) - 1, 2))
    C.append(combination(A.count(str(i + 1)), 2))
for i in A:
    print(B[int(i)-1] - C[int(i)-1] +sum(C))

### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
s = [0]*n
for i in range(n):
    s[a[i]-1] += 1
k = 0
for i in range(n):
    if s[i] >= 2:
        k += ((s[i]*(s[i]-1))//2)
for i in range(n):
    if s[a[i]-1] >= 2:
        print(k-(s[a[i]-1]-1))
    else:
        print(k)
### BUGGY CODE ###

N, M = map(int,input().split())
A_list = [int(input()) for _ in range(M)]
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue
#        elif i in A_list and i-1 in A_list:
#            Dp_list = [0] * (N + 1)
#            break
        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
#        else:
#            Dp_list[i] = 0
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N])
else:
    print(1)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
### BUGGY CODE ###

from collections import deque

b = deque(map(int, input()))
cnt = 0
while len(b) > 1:

    if len(list(set(b))) == 1:
        break
    if b[0] != b[1]:
        b.popleft()
        b.popleft()
        cnt += 1
        continue
    b.append(b.popleft())

print(cnt * 2)


### FIXED CODE ###

s = input()
zom = min(s.count("1"),s.count("0"))
if len(set(list(s))) == 1:
    zom = 0
print(zom*2)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        S = S[::-1]
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            S = C + S
        else:
            S = S + C

print(S)


### FIXED CODE ###

from collections import deque

S = deque([x for x in input()])
Q = int(input())
switch = 0
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        T = int(inp)
        if switch:
            switch = 0
        else:
            switch = 1
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            if switch:
                S.append(C)
            else:
                S.appendleft(C)
        else:
            if switch:
                S.appendleft(C)
            else:
                S.append(C)
if switch:
    print("".join(list(S)[::-1]))
else:
    print("".join(S))
### BUGGY CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
events = sorted(events, key=itemgetter(0,1), reverse=True)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)

    

### FIXED CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)
### BUGGY CODE ###

import collections
from math import gcd
import sys
input=sys.stdin.readline
n=int(input())
c=collections.Counter()
mod=10**9+7
for _ in range(n):
    a,b=map(int,input().split())
    g=abs(gcd(a,b))
    if g==0:
        g=1
    a//=g
    b//=g
    c[(a,b)]+=1
ans=1
s=set()
for i,j in c:
    if (i,j)==(0,0):
        continue
    if (i,j) not in s:
        s.add((i,j))
        s.add((-i,-j))
        s.add((-j,i))
        s.add((j,-i))
        ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
print((ans-1+c[(0,0)])%mod)


### FIXED CODE ###

import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

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

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []
for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
for i in range(len(s)):
    if A[0]==0:
        if i%2==0:
            a = max(a,sum(s[i:i+2*K]))
        else:
            a = max(a,sum(s[i:i+2*K+1]))
    else:
        if i%2==0:
            a = max(a,sum(s[i:i+2*K+1]))
        else:
            a = max(a,sum(s[i:i+2*K]))
print(a)

### FIXED CODE ###

N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
        a = max(a,su)
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
        a = max(a,su)

print(a)
### BUGGY CODE ###

n = int(input())

A = [0 for _ in range(n)]
for i in range(n):
    a = int(input())
    for k in range(i):
        if a <= A[k]:
            # print(A[k + 1: i + 1], A[k:i])
            A[k + 1: i + 1] = A[k: i]
            A[k] = a
            break
    else:
        A[i] = a
    # print(A)
# A.sort()
# print(A)

ans = 0
end = [A[0], A[-1]]
ans += abs(A[-1] - A[0])
A = A[1:-1]
while len(A) != 0:
    # print(ans, A, end)
    sl = [A[0], A[-1]]

    tmp_l = []
    tmp_l.append(abs(end[0] - sl[0]))
    tmp_l.append(abs(end[1] - sl[0]))
    tmp_l.append(abs(end[0] - sl[1]))
    tmp_l.append(abs(end[1] - sl[1]))

    tmp = max(tmp_l)
    index = tmp_l.index(tmp)
    ans += tmp

    # print(index, tmp_l[index])
    if index % 2 == 0:
        end[0] = sl[index == 2]

    else:
        end[1] = sl[index == 3]

    if index < 2:
        A = A[1:]
    else:
        A = A[:-1]

print(ans)

### FIXED CODE ###

n = int(input())

A = []
for i in range(n):
    A.append(int(input()))
A.sort()
# print(A)

ans = 0
end = [A[0], A[-1]]
ans += abs(A[-1] - A[0])
A = A[1:-1]
s = 0
L = -1
for _ in range(n - 2):
    # print(ans, A, end)
    sl = [A[s], A[L]]
    # print(sl)

    tmp_l = []
    tmp_l.append(abs(end[0] - sl[0]))
    tmp_l.append(abs(end[1] - sl[0]))
    tmp_l.append(abs(end[0] - sl[1]))
    tmp_l.append(abs(end[1] - sl[1]))

    tmp = max(tmp_l)
    index = tmp_l.index(tmp)
    ans += tmp

    # print(index, tmp_l[index])
    if index % 2 == 0:
        end[0] = sl[index == 2]

    else:
        end[1] = sl[index == 3]

    if index < 2:
        s += 1
    else:
        L -= 1

print(ans)