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

 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n

   # AAABBCCCCA ⇒ A3B2C4A1

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a_c,a_n =rle(S)
a_len =len(a_c)
count =[0]*a_len
ans =0
if a_c[-1] ==1:
    f=1 
if a_c[-1] ==0:
    f=0 

if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=0
        while not(i +2*K +1 ==a_len+2 or i +2*K +1 ==a_len+3):
            count[i] =sum(a_n[i:i+2*K +1])
            i +=2
    else:
        count[0] =sum(a_n[:2*K])
        i=1
        while not(i +2*K +1 ==a_len +2 or i +2*K +1 == a_len +3):
            count[i] =sum(a_n[i:i+2*K+1])
            i +=2      

    ans =max(count)
print(ans)

### FIXED CODE ###

 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a_c,a_n =rle(S)
a_len =len(a_c)
a_n +=[0]
count =[0]*a_len
ans =0

#
if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=2
        indx =i +2*K 
        count[0] =sum(a_n[:0 +2*K +1])
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2
            indx =i +2*K 
    else:
        count[0] =sum(a_n[:2*K])
        count[1] =sum(a_n[1: 1+2*K+1])
        i=3
        indx =i +2*K 
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2      
            indx =i +2*K 
    ans =max(count)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n=int(input())
sumy=0
for i in range(n):
  t=i+1
  k=int(n/t)
  sumy+=int(t*k*(k+1)/2)
print(sumy)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n=int(input())
sumy=0
#nの半分より上の倍数は1個なのでそこで分ける
numhalf=int(n/2)
#nの半分までは倍数ごとに個数を求めて足していく
for i in range(numhalf):
  t=i+1
  k=int(n/t)
  sumy+=int(t*k*(k+1)/2)
#半分より上の倍数はすべて1個ずつなのでまとめて足す
sumy+=int((n+numhalf+1)*(n-numhalf)/2)
print(sumy)
### BUGGY CODE ###

import collections
S=str(input())

T=[0 for i in range(len(S))]
T[0]=int(S[-1])

for i in range(1,len(S)):
    T[i]=((10**i)*int(S[len(S)-1-i])+T[i-1])%2019
    
cnt=0
T_di=collections.Counter(T)

for key in T_di.keys():
    x=T_di[key]
    cnt+=x*(x-1)/2
    if key==0:
        cnt+=x

print(int(cnt))

### FIXED CODE ###

import collections
S=str(input())

T=[0 for i in range(len(S))]
T[0]=int(S[-1])

for i in range(1,len(S)):
    T[i]=(pow(10,i,2019)*int(S[len(S)-1-i])+T[i-1])%2019
    
cnt=0
T_di=collections.Counter(T)

for key in T_di.keys():
    x=T_di[key]
    cnt+=x*(x-1)/2
    if key==0:
        cnt+=x

print(int(cnt))
### BUGGY CODE ###

N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

dp = [-INF] * (T + 1)
dp[0] = 0

for a, b in AB:
    for t in range(T)[:: -1]:
        dp[min(T, t + a)] = max(dp[min(T, t + a)], dp[t] + b)

print(max(dp))

### FIXED CODE ###

N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

dp = [-INF] * (T + 1)
dp[0] = 0

for a, b in AB:
    newDp = dp[::]
    for t, d in enumerate(dp[:T]):
        newDp[min(T, t + a)] = max(newDp[min(T, t + a)], d + b)
    dp = newDp

print(max(dp))
### BUGGY CODE ###

S = list(input())
Q = int(input())
query = [list(input().split()) for _ in range(Q)]

for i in query:
    if i[0] == '1':
        S.reverse()
    elif i[0] == '2':
        if i[1] == '1':
            S.insert(0, i[2])
        elif i[1] == '2':
            S.append(i[2])
print(''.join(S))


### FIXED CODE ###

S = list(input())
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
a = 0
mem = []
for i in query:
    if i[0] == '1':
        if a == 0:
            a = 1
        else:
            a = 0
    elif i[0] == '2':
        if i[1] == '1':
            if a == 1:
                S.append(i[2])
            else:
                #S.insert(0, i[2])
                mem.append(i[2])
        elif i[1] == '2':
            if a == 1:
                #S.insert(0, i[2])
                mem.append(i[2])
            else:
                S.append(i[2])
mem.reverse()
S[0:0] = mem
if a == 1:
    S.reverse()
# print(S)
print(''.join(S))
### BUGGY CODE ###

from fractions import gcd
#from math import gcd
#import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]

sums=[0]
[sums.append( (sums[-1]+lcms[-1]//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
### BUGGY CODE ###

N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
if len(bro) >= 1 and bro[0] != 1:
    dp[1] = 1
elif len(bro) >= 1:
    del bro[0]
elif len(bro) == 0:
    dp[1] = 1
for i in range(2,N+1):
    if i in bro:
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)


### FIXED CODE ###

N,M = map(int,input().split())
bro = [int(input()) for i in range(M)]
mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
if len(bro) >= 1 and bro[0] != 1:
    dp[1] = 1
elif len(bro) >= 1:
    del bro[0]
elif len(bro) == 0:
    dp[1] = 1
for i in range(2,N+1):
    if len(bro) == 0:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
    elif bro[0] == i:
        del bro[0]
        continue
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % mod
print(dp[-1] % mod)
### BUGGY CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          if d[x][y] < d[x0][y0] + 1: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
Max = 0
for start in range(n-1):
    count = 0
    for i in range(start+1, n):
        if h[i] <= h[i-1]:
            count += 1
        else:
            break
    Max = max(Max ,count)
print(Max)


### FIXED CODE ###

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

Max = 0
start = 0
# cnt = 0
while start < n-1:
    # print(f"start = {start}")
    # cnt += 1
    count = 0
    for i in range(start+1, n):
        if h[i] <= h[i-1]:
            count += 1
        else:
            break
    Max = max(Max ,count)
    start = i
    # if cnt > 10:
    #     break
print(Max)
### BUGGY CODE ###

S, C = map(int, input().split())

if S * 2 >= C:
    print(C//2)
    exit()

i = 0
while (C - 2*i)/(S + i) >= 2:
    i += 1

print(S + i - 1)


### FIXED CODE ###

S, C = map(int, input().split())

if S * 2 >= C:
    print(C//2)
    exit()

i = (C - 2 * S) // 4

print(S + i)
### BUGGY CODE ###


def main():
    from itertools import combinations

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    ans = 0
    for i in combinations(a, 2):
        ans += i[0] ^ i[1]
        ans %= mod

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array(list(map(int, input().split())))

mod = 10 ** 9 + 7

ans = 0
for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    ans += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(ans%mod)
### BUGGY CODE ###

n,w=map(int,input().split())
ab=[]
w-=1
take=[]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
k=w
take=[]
for i in range(n):
	if dp[n-i-1][w]!=dp[n-i][w]:
		w-=ab[n-i-1][0]
		take.append(n-i-1)
take=set(take)
ans=0
for i in range(n):
	if i not in take:
		ans=max(ans,ab[i][1])
print(dp[-1][-1]+ans)




### FIXED CODE ###

n,w=map(int,input().split())
ab=[]
w-=1
take=[]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
k=w
take=[]
for i in range(n):
	if dp[n-i-1][w]!=dp[n-i][w]:
		w-=ab[n-i-1][0]
		take.append(n-i-1)
take=set(take)
ans=0
for i in range(n):
	if i not in take:
		ans=max(ans,ab[i][1])
print(dp[-1][-1]+ans)
### BUGGY CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

INF = 10**9+10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        l_min = min(l_min,Bi[k]+Bj[k])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

### FIXED CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)
### BUGGY CODE ###

import sys
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    if a.count(i)>=3:
        print(0)
        sys.exit()
if a.count(0) >= 2:
    print(0)
    sys.exit()
if 0 in a:
    a.remove(0)
b = set(a)
print(2**(len(b)))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
out = 0
if n == 1:
    if a[0] != 0:
        out = 1
elif a[0] == 0:
    if n%2 == 0:
        out = 1
    else:
        for i in range(1,n//2+1):
            if a[2*i-1] == a[2*i] and a[2*i] == 2*i:
                None
            else:
                out = 1
elif a[0] == 1:
    if n%2 == 1:
        out = 1
    else:
        for i in range(n//2):
            if a[2*i] == a[2*i+1] == 2*i+1:
                None
            else:
                out = 1
else:
    out = 1
if out:
    print(0)
else:
    a = 1
    for i in range(n//2):
        a *= 2
        a = a%(10**9+7)
    print(a)
### BUGGY CODE ###

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

for i in d:
  print(i)

### FIXED CODE ###

n, x, y = list(map(int,input().split()))
d = [0 for i in range(n-1)] 
for i in range(1,n+1):
  for j in range(i+1,n+1):
    d[min([j-i, abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)])-1] += 1

for i in d:
  print(i)
### BUGGY CODE ###

x = input()
while('ST' in x):
    x = x.replace('ST', '')
print(len(x))

### FIXED CODE ###

x = input()
s, t = 0, 0
for c in x:
    if(c == 'S'):
        s += 1
    else:
        if(s):
            s -= 1
        else:
            t += 1
print(t*2)
### BUGGY CODE ###

S = raw_input().split(" ")
S[0] = int(S[0])
S[1] = int(S[1])

while S[0] != 0 or S[1] != 0:
  if(S[0] < S[1]):
    print(str(S[0]) + " " + str(S[1]))
  else:
    print(str(S[1]) + " " + str(S[0]))

### FIXED CODE ###

S = raw_input().split(" ")
S[0] = int(S[0])
S[1] = int(S[1])

while S[0] != 0 or S[1] != 0:
  if(S[0] < S[1]):
    print(str(S[0]) + " " + str(S[1]))
  else:
    print(str(S[1]) + " " + str(S[0]))
  S = raw_input().split(" ")
  S[0] = int(S[0])
  S[1] = int(S[1])
### BUGGY CODE ###

from functools import reduce
import math

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    S = list(_ for _ in input())
    S = S[::-1]    
    S_num = 0
    temp_ans_0 = ''
    temp_ans_1 = ''
    num_temp_ans_0 = 0
    num_temp_ans_1 = 0
    # for i in range(len(S)):
    #     if(i%2 ==0):
    #         temp_ans_0 += '0'
    #         temp_ans_1 += '1'
    #     else:
    #         temp_ans_0 += '1'
    #         temp_ans_1 += '0'
    i = 0
    for s in S:
        S_num += int(s) * 2**i
        if(i%2 ==0):
            num_temp_ans_0 += 0 * 2**i
            num_temp_ans_1 += 1 * 2**i
        else:
            num_temp_ans_0 += 1 * 2**i
            num_temp_ans_1 += 0 * 2**i
        i +=1
    c0 = bin(S_num ^ num_temp_ans_0).count('1')
    c1 = bin(S_num ^ num_temp_ans_1).count('1')
    
    print(min(c0,c1))
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import math

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    S = list(_ for _ in input())
    S = S[::-1]    
    S_num = 0
    temp_ans_0 = '0b'
    temp_ans_1 = '0b'
    num_temp_ans_0 = 0
    num_temp_ans_1 = 0
    for i in range(len(S)):
        if(i%2 ==0):
            temp_ans_0 += '0'
            temp_ans_1 += '1'
        else:
            temp_ans_0 += '1'
            temp_ans_1 += '0'
    # i = 0
    # for s in S:
    #     S_num += int(s) * 2**i
    #     if(i%2 ==0):
    #         num_temp_ans_0 += 0 * 2**i
    #         num_temp_ans_1 += 1 * 2**i
    #     else:
    #         num_temp_ans_0 += 1 * 2**i
    #         num_temp_ans_1 += 0 * 2**i
    #     i +=1
    S_str ='0b'+''.join(S)
    S_num = int(S_str,0)
    num_temp_ans_0 = int(temp_ans_0,0)
    num_temp_ans_1 = int(temp_ans_1,0) 
    c0 = bin(S_num ^ num_temp_ans_0).count('1')
    c1 = bin(S_num ^ num_temp_ans_1).count('1')
    
    print(min(c0,c1))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
mod = 10**9 + 7
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if len(s)==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(len(s)-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
                    nextdp[l] %= mod
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
                nextdp[l] %= mod
        mul *= 10
        dp = nextdp
    print(dp[5])
    exit()

### FIXED CODE ###

s = input()
mod = 10**9 + 7
N = len(s)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if N==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(N-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
                    nextdp[l] %= mod
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
                nextdp[l] %= mod
        mul *= 10
        mul %= 13
        dp = nextdp
    print(dp[5])
    exit()
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

INF = 10 ** 10 + 7


def main():
    X, Y, Z, K = map(int, readline().split())
    A = sorted(list(map(int, readline().split())), reverse=True)
    B = sorted(list(map(int, readline().split())), reverse=True)
    C = sorted(list(map(int, readline().split())), reverse=True)

    ans = solve1(X, Y, Z, K, A, B, C)
    print('\n'.join(map(str, ans)))


def solve1(X, Y, Z, K, A, B, C):

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])

    AB.sort(reverse=True)
    AB = AB[:min(X * Y, K)]

    ABC = []
    for i in range(len(AB)):
        for j in range(Z):
            ABC.append(AB[i] + C[j])

    ABC.sort(reverse=True)

    return ABC[:K]


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

INF = 10 ** 10 + 7


def main():
    X, Y, Z, K = map(int, readline().split())
    A = sorted(list(map(int, readline().split())), reverse=True)
    B = sorted(list(map(int, readline().split())), reverse=True)
    C = sorted(list(map(int, readline().split())), reverse=True)

    ans = solve1(X, Y, Z, K, A, B, C)
    print('\n'.join(map(str, ans)))


def solve1(X, Y, Z, K, A, B, C):

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])

    AB.sort(reverse=True)
    AB = AB[:min(X * Y, K)]

    ABC = []
    for i in range(len(AB)):
        for j in range(Z):
            ABC.append(AB[i] + C[j])

    ABC.sort(reverse=True)

    return ABC[:K]


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

from sys import stdin

k, s = map(int, stdin.readline().split())

result = set()


def get_variants(target, maximum):
    result = []
    for x in range(maximum, -1, -1):
        y = target - x
        if 0 <= y <= maximum:
            result.append([x, y])
    return result

for z in range(k+1):
    variants = get_variants(s - z, k)
    for var in variants:
        result.add((z, var[0], var[1]))

print(len(result))


### FIXED CODE ###

from sys import stdin

k, s = map(int, stdin.readline().split())

result = 0


def get_variants(target, maximum):
    result = 0
    for x in range(maximum, -1, -1):
        y = target - x
        if 0 <= y <= maximum:
            result += 1
    return result

for z in range(k+1):
    variants = get_variants(s - z, k)
    result += variants

print(result)
### BUGGY CODE ###

from collections import defaultdict

def get_p(ind):
    global parent
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]

parent = []

def main():
    global parent

    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [i for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        a_parent = get_p(a)
        b_parent = get_p(b)

        if a_parent != b_parent:
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)


    ans = 0

    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int) == get_p(ind):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###



def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind =  data[i]
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

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

N = int(input())
cnt = 0
for i in range(1,N+1):
    a = str(i)
    a0 = a[0]
    an = a[-1]
    if an=="0":continue
    k = 0
    while eval(an+"9"*k+a0)<=N:
        cnt += 10**k
        k += 1
    for j in range(10**k):
        b = str(j)
        b = "0"*(k-len(b))+b
        if eval(an+b+a0)<=N:
            cnt += 1
    if a0==an and int(a0)<=N:
        cnt += 1
print(cnt)

### FIXED CODE ###

def f(x):
    if 1<=x<=9:
        return 1
    if x%10==0:
        return 0
    x = str(x)
    a = x[0]
    b = x[-1]
    k = len(x)
    if int(a)<int(b):
        if k==2:
            return 0
        else:
            return 2*(10**(k-2)-1)//9
    elif int(a)>int(b):
        return 2*(10**(k-1)-1)//9
    else:
        if k==2:
            return 3
        else:
            return (1+(10**(k-2)-1)//9+int(x[1:k-1]))*2+1

N = int(input())
dp = [0 for _ in range(N+1)]
for i in range(min(N,9)+1):
    dp[i] = i
for i in range(10,N+1):
    dp[i] = dp[i-1]+f(i)
print(dp[N])