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

from time import time
from random import randrange

t0 = time()

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

N = 26


t = [max(range(26), key=lambda x: si[x]) for si in s]


while time() - t0 < 1.9:
    # init
    diff = 0

    di = randrange(D)
    qi = randrange(N)

    # delete
    old_type = t[di]

    for next_d in range(di + 1, D):
        if t[next_d] == old_type:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == old_type:
            break
    else:
        prev_d = -1

    diff -= s[di][old_type]
    diff -= (next_d - di) * (di - prev_d) * c[old_type]

    # insert
    for next_d in range(di + 1, D):
        if t[next_d] == qi:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == qi:
            break
    else:
        prev_d = -1

    diff += s[di][qi]
    diff += (next_d - di) * (di - prev_d) * c[qi]

    # saiyou
    if diff >= 0:
        t[di] = qi

ans = [ti + 1 for ti in t]
print(*ans, sep="\n")

### FIXED CODE ###

from time import time

t0 = time()

from random import randrange

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

N = 26


t = [max(range(26), key=lambda x: si[x]) for si in s]


while time() - t0 < 1.8:
    # init
    diff = 0

    di = randrange(D)
    qi = randrange(N)

    # delete
    old_type = t[di]

    for next_d in range(di + 1, D):
        if t[next_d] == old_type:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == old_type:
            break
    else:
        prev_d = -1

    diff -= s[di][old_type]
    diff -= (next_d - di) * (di - prev_d) * c[old_type]

    # insert
    for next_d in range(di + 1, D):
        if t[next_d] == qi:
            break
    else:
        next_d = D

    for prev_d in range(di - 1, -1, -1):
        if t[prev_d] == qi:
            break
    else:
        prev_d = -1

    diff += s[di][qi]
    diff += (next_d - di) * (di - prev_d) * c[qi]

    # saiyou
    if diff >= 0:
        t[di] = qi

ans = [ti + 1 for ti in t]
print(*ans, sep="\n")
### BUGGY CODE ###

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

visited = {}

for d in lst:
  if d in visited.keys():
    visited[d] += 1
  else:
    visited[d] = 1
    
searched = {}
for i in range(n):
  if i in searched.keys():
    print(searched[i])
    continue
  visited[lst[i]] -= 1
  ans = 0
  for d in visited.keys():
    v = visited[d]
    ans += v*(v-1)/2
  print(int(ans))
  searched[i] = ans
  visited[lst[i]] += 1

### FIXED CODE ###

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

visited = {}

for d in lst:
  if d in visited.keys():
    visited[d] += 1
  else:
    visited[d] = 1
count = 0
for d in visited.keys():
  count += int(visited[d]*(visited[d]-1)/2)
for d in lst:
  v = visited[d] - 1
  ans = count - v
  print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(S):
    N = len(S)
    r = 0
    d = [0] * 2019
    d[0] = 1
    for i in range(N):
        r = (r + int(S[N - 1 - i]) * 10 ** i) % 2019
        d[r] += 1
    ans = 0
    for c in d:
        ans += c * (c - 1) // 2
    return ans


S = input()
print(calc(S))

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().rstrip('\n')

def calc(S):
    N = len(S)
    r = 0
    d = [0] * 2019
    p = 1
    d[0] = 1
    for i in range(N):
        r = (r + int(S[N - 1 - i]) * p) % 2019
        p = (p * 10) % 2019
        d[r] += 1
    ans = 0
    for c in d:
        ans += c * (c - 1) // 2
    return ans


S = input()
print(calc(S))
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = A.copy()
for i in range(1, N):
    ans += (-1) ** i * np.concatenate([A[i:].copy(), A[:i].copy()])
ans = list(ans)
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N = int(input())
A = np.array(list(map(int, input().split())))
sgn = np.tile(np.array([1, -1]), N // 2)
sgn = np.concatenate([sgn, np.array([1])])
ans = np.empty(N, dtype=np.int)
ans[0] = (A * sgn).sum()
for i in range(1, N):
    ans[i] = 2 * A[i - 1] - ans[i - 1]
print(*ans)
### BUGGY CODE ###

S=input()
i=0
s=S
count=0
while True:
    if (i==(len(s)-1))or(len(s)==0):
        break
    if not(s[i]==s[i+1]):
        #print(s[:i],s[i+2:])
        s="".join((s[:i],s[i+2:]))
        #print(s)
        #input()
        i=0
        count=count+1
    else:
        i=i+1
print(count*2)

### FIXED CODE ###

S=input()
i=0
s=S
count0=0
count1=0
for i in range(len(S)):
    if S[i]=="0":
        count0=count0+1
    else:
        count1 = count1 + 1
print(min(count0,count1)*2)
### BUGGY CODE ###

ar = list(input())
total = 0
for i in range(len(ar)+1):
    rc = 0
    lc = 0
    r = ar[i:len(ar)]
    l = ar[0:i][::-1]
    for j in r:
        if j == ">":
            rc += 1
        else:
            break
    for k in l:
        if k == "<":
            lc += 1
        else:
            break
    total += max(rc,lc)
print(total)

### FIXED CODE ###

a = input()
ar = [0 for i in range(len(a)+1)]
for i in range(len(a)):
    if a[i] == '<':
        ar[i+1] = max(ar[i] + 1,ar[i+1])
for i in range(len(a)-1,-1,-1):
    if a[i] == '>':
        ar[i] = max(ar[i+1] + 1,ar[i])
print(sum(ar))
### BUGGY CODE ###

S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]=dp[i+1][(10*k+j)%13]+dp[i][k]
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]=dp[i+1][(10*k+a)%13]+dp[i][k]
print(dp[len(S)][5]%MOD)

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]+=dp[i][k]%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]+=dp[i][k]%MOD
print(dp[len(S)][5]%MOD)
### BUGGY CODE ###

N=range(int(input()))
S=input()
ans=0
for x in N:
  for y in N:
    for z in N:
      if x-y!=y-z and x<y and y<z:
        p,q,r=S[x],S[y],S[z]
        if p!=q and q!=r and r!=p:
          ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
all=S.count("R")*S.count("G")*S.count("B")

for i in range(N-1):
  for j in range(i,N):
    if 0<=2*i-j<N:
      if S[2*i-j]!=S[i]!=S[j]!=S[2*i-j]:
        all-=1
print(all)
### BUGGY CODE ###

def solve(s, t):
    n, m = len(s), len(t)

    ans, dp = 0, [0] * (m + 1)
    for i in xrange(n):
        for j in xrange(m, 0, -1):
            if s[i] == t[j - 1]:
                dp[j] = 1 + dp[j - 1]
            else:
                dp[j] = 0
            ans = max(ans, dp[j])
    return ans

while True:
    try:
        s = raw_input().strip()
        t = raw_input().strip()
    except EOFError:
        break

    print solve(s, t)

### FIXED CODE ###

# coding:utf-8
from __future__ import division, print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass

p, q = 10 ** 9 + 7, 0xffffffff
pow_p = [1]
for i in range(4010):
    pow_p.append(pow_p[-1] * p & q)


def exists(a, b, k):
    n, m = len(a), len(b)

    s = [a[k + i] - a[i] * pow_p[k] & q for i in range(n - k)]
    t = [b[k + i] - b[i] * pow_p[k] & q for i in range(m - k)]
    return len(set(s).intersection(set(t))) > 0


def hash(s):
    t = 0
    yield t
    for c in s:
        t = t * p + ord(c) & q
        yield t
    return


def solve(s, t):
    n, m = len(s), len(t)
    a, b = list(hash(s)), list(hash(t))

    l, r = 0, min(n, m) + 1
    while l + 1 < r:
        m = (l + r) // 2
        if exists(a, b, m):
            l = m
        else:
            r = m
    return l


while True:
    try:
        s = input().strip()
        t = input().strip()
    except EOFError:
        break

    print(solve(s, t))
### BUGGY CODE ###

n, m = map(int, input().split())

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        if a == n:
            ln.append(b)
        else:
            ln.append(a)

for i in la:
    if i in ln:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

A = sorted(A, reverse=True)

for _ in range(M):
    A[0] = A[0] / 2
    A = sorted(A, reverse=True)

ans = 0
for a in A:
    ans += int(a)

print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(i) for i in input().split()]

heapq.heapify(A)

for _ in range(M):
    x = heapq.heappop(A) / 2
    heapq.heappush(A, x)

ans = 0
for a in A:
    ans -= int(a)

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

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

dp = [float('inf')]*n
dp[0] = 0
for i in range(1,n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf')]*n
dp[0] = 0
for i in range(1,n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
print(dp[-1])
### BUGGY CODE ###

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

dp = [[[0] * (n + 1) for i in range(n + 1)] for j in range(50 * 50 + 1)]
dp[0][0][0] = 1

for j in range(1, n + 1):
    for k in range(n + 1):
        for s in range(50 * 50 + 1):
            if s < x[j - 1]:
                dp[s][k][j] += dp[s][k][j - 1]
            else :
                dp[s][k][j] += dp[s][k][j - 1] + dp[s - x[j - 1]][k - 1][j - 1]

ans = 0
for k in range(1, n + 1):
    ans += dp[k * a][k][n]
print(ans)


### FIXED CODE ###

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

dp = [[[0] * (n + 1) for i in range(n + 1)] for j in range(50 * 50 + 1)]
dp[0][0][0] = 1

for j in range(1, n + 1):
    for k in range(n + 1):
        for s in range(50 * 50 + 1):
            if s < x[j - 1]:
                dp[s][k][j] += dp[s][k][j - 1]
            else :
                dp[s][k][j] += dp[s][k][j - 1] + dp[s - x[j - 1]][k - 1][j - 1]

ans = 0
for k in range(1, n + 1):
    ans += dp[k * a][k][n]
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)

a = []
for i in range(n):
    a.append(ord(s[i])-ord('a'))

for i in range(n):
    need = 26 - a[i]
    if(k>=need):
        a[i]=0
        k-=need


k %= 26

for ii in range(n):
    i = n-1-ii
    rem = 25 - a[i]
    if(rem<=k):
        a[i]+=rem
        k-=rem
    else:
        a[i]+=k
        k=0
        
        break
ans = ''
for i in range(n):        
    ans += chr(a[i]+ord('a'))
print(ans)


### FIXED CODE ###


s = input()
k = int(input())
n = len(s)

a = []
for i in range(n):
    a.append(ord(s[i])-ord('a'))

for i in range(n):
    need = (26 - a[i])%26
    if(k>=need):
        a[i]=0
        k-=need


k %= 26

for ii in range(n):
    i = n-1-ii
    rem = 25 - a[i]
    if(rem<=k):
        a[i]+=rem
        k-=rem
    else:
        a[i]+=k
        k=0
        
        break
ans = [' ' for i in range(n)]
for i in range(n):        
    ans[i] = chr(a[i]+ord('a'))
print(''.join(map(str,ans)))
### BUGGY CODE ###

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

list = [1]*N

for i in range(M):
	L, R = map(int, input().split())
	list[:L-1] = [0]*len(list[:L-1])
	list[R:] = [0]*len(list[R:])

print(list.count(1))
  

### FIXED CODE ###

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

llist = []
rlist = []

for i in range(M):
  L, R = map(int, input().split())
  llist.append(L)
  rlist.append(R)

if min(rlist) >= max(llist):
  print(min(rlist) - max(llist) + 1)
else:
  print(0)
### BUGGY CODE ###

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

a_sorted = sorted(a)

for i in range(m):
    maximum = a_sorted.pop(-1)
    bisect.insort_left(a_sorted, maximum//2)

ans = sum(a_sorted)
print(ans)

### FIXED CODE ###

import heapq

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

for i in range(m):
    maximum = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-maximum//2))
print(-sum(a))
### BUGGY CODE ###

N = int(input())
array=[int(n) for n in input().split()]
lst=[]
left_array=array[:N] 
right_array=array[-N:]
l_sum=sum(left_array)
r_sum=sum(right_array)
left_lst=[l_sum]
right_lst=[r_sum]
for k in range(N,2*N):
    new_a=array[k]
    new_b=array[-k-1]
    left_array.append(new_a)
    old_a=min(left_array)
    left_array.remove(old_a)
    l_sum+=(new_a-old_a)
    left_lst.append(l_sum)
    right_array.append(new_b)
    old_b=max(right_array)
    right_array.remove(old_b)
    r_sum+=(new_b-old_b)
    right_lst.append(r_sum)
lst = [a-b for a,b in zip(left_lst,list(reversed(right_lst)))]
print(max(lst))

### FIXED CODE ###

N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    C = []
    F = [[0]*(N+1) for i in range(N+1)]
    A = [1]*(N+1)

    for i in range(M):
        a, b = map(int, input().split())
        if F[a][b] == 0:
            F[a][b] += 1
            A[a] += 1
        if F[b][a] == 0:
            F[b][a] += 1
            A[b] += 1
    ans = max(A)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return -self.parents[self.find(x)]

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 1
    if M == 0:
        print(ans)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

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

N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*N
for i in range(1, N):
    v = 10**18
    for k in range(min(K, i)):
        v = min(v, dp[i-k-1] + abs(A[i] - A[i-k-1]))
    dp[i] = v
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*N
for i in range(1, N):
    v = 10**18
    for k in range(min(K, i)):
        v = min(v, dp[i-k-1] + abs(A[i] - A[i-k-1]))
    dp[i] = v
print(dp[N-1])
### BUGGY CODE ###

N=int(input())
l=list()
for i in range(N):
    l.append(int(input()))

num=list()
for k in range(N):
    num=l[:k]+l[k+1:]
    print(max(num))

### FIXED CODE ###

N=int(input())
l=list()
for i in range(N):
    l.append(int(input()))
a=sorted(l)
m1=a[-1]
m2=a[-2]
for k in range(N):
    if(m1==l[k]):
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

import math
from itertools import accumulate

def is_prime(n):
    if n == 1: return 0

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1

Q = int(input())
L = [0]*Q
R = [0]*Q

for j in range(Q):
    L[j],R[j] = [int(i) for i in input().split()]

li = []
for i in range(min(L),max(R)+1,1):
    if i%2 == 1:
        li.append(is_prime(i) * is_prime((i+1)//2))
    else:
        li.append(0)

ans = [0]
ans += list(accumulate(li))

for i,j in zip(L,R):
    print(ans[j-min(L)+1] - ans[i-min(L)])


### FIXED CODE ###

import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0

    return 1


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] - min_L + 1] - check[L[i] - min_L])
### BUGGY CODE ###

cnt = 0
S = input()  
for left in range(len(S)-3):
    for right in range(left+3,len(S)):
        if int(S[left:right+1]) < 2019:
            continue
        if int(S[left:right+1]) % 2019 == 0:
            cnt += 1
print(cnt) 

### FIXED CODE ###

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

from itertools import combinations as comb
n = int(input())
str_list = []
ans = 0
for i in range(n):
    str_list.append(sorted(input()))

comb_list = list(comb(str_list, 2))

for comb in comb_list:
    if comb[0] == comb[1]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
str_list = ["".join(sorted(input())) for i in range(n)]
ans = 0
str_dic = {}

for i in range(n):
    if str_list[i] in str_dic:
        str_dic[str_list[i]] += 1
    else:
        str_dic[str_list[i]] = 0

for v in str_dic.values():
    ans += v*(v+1)/2

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

#Frog2
n,k=map(int,input().split())
h=list(map(int,input().split()))
h.insert(0,0)
dp={1:0}
for val3 in range(2,n+1):
    dp[val3]=int(1e9)
for val in range(2,n+1):
    for val2 in range(1,min(val,k+1)):
        dp[val]=min(dp[val],dp[val-val2]+abs(h[val]-h[val-val2]))
print(dp[n])
        

### FIXED CODE ###

#Frog2
n,k=map(int,input().split())
h=list(map(int,input().split()))
h.insert(0,0)
dp={1.0:0}
for val3 in range(2,n+1):
    dp[val3]=float(1e9)
for val in range(2,n+1):
    for val2 in range(1,min(val,k+1)):
        dp[val]=min(dp[val],dp[val-val2]+abs(h[int(val)]-h[int(val-val2)]))
print(dp[n])
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()
counter = {'R': [0], 'G': [0], 'B': [0]}
for s in S:
    for c in 'RGB':
        counter[c].append(counter[c][-1] + (1 if s == c else 0))
ans = 0
for i, j in combinations(range(N-1), 2):
    if S[i] == S[j]: continue
    l = j - i
    temp = set([S[i], S[j]])
    if 'R' not in temp: key = 'R'
    elif 'G' not in temp: key = 'G'
    else: key = 'B'
    cnt = counter[key]
    if j + l > N:
        ans += cnt[-1] - cnt[j]
    else:
        ans += cnt[j+l] - cnt[j] + (cnt[-1] - cnt[j + l + 1] if j + l + 1 <= N else 0)
print(ans)

### FIXED CODE ###

from itertools import combinations

N = int(input())
S = input()
counter_R = [0]
counter_G = [0]
counter_B = [0]
for s in S:
    counter_R.append(counter_R[-1] + (s == 'R'))
    counter_G.append(counter_G[-1] + (s == 'G'))
    counter_B.append(counter_B[-1] + (s == 'B'))
ans = 0
for i, j in combinations(range(N-1), 2):
    if S[i] == S[j]: continue
    l = j - i
    temp = [S[i], S[j]]
    if 'R' not in temp: cnt = counter_R
    elif 'G' not in temp: cnt = counter_G
    else: cnt = counter_B
    if j + l > N:
        ans += cnt[-1] - cnt[j]
    else:
        ans += cnt[j+l] - cnt[j] + (cnt[-1] - cnt[j + l + 1] if j + l + 1 <= N else 0)
print(ans)
### BUGGY CODE ###

import itertools

X, Y, Z, K = list(map(int, input().split()))
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

AB_list = [a + b for (a, b) in itertools.product(A_list, B_list)]
AB_list.sort(reverse=True)
ABC_list = [ab + c for (ab, c) in itertools.product(AB_list[:min(3000, X*Y*Z)], C_list)]
ABC_list.sort(reverse=True)
for i in range(K):
  print(ABC_list[i])

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
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)

from heapq import heapify, heappop, heappush, heappushpop
 
 
class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)
 
    def push(self, item):
        heappush(self.heap, item)
 
    def pop(self):
        return heappop(self.heap)
 
    def pushpop(self, item):
        return heappushpop(self.heap, item)
 
    def __call__(self):
        return self.heap
 
 
heap = []  # ヒープといっても順序を工夫したただのリスト
 
q = PriorityQueue(heap)
q.push((-(A[0] + B[0] + C[0]), 0, 0, 0))
 
considered = set()
ans = []
for k_th in range(1, K+1):
    heap_max, i, j, k = q.pop()
    ans.append(-heap_max)
    for di, dj, dk in zip([1, 0, 0], [0, 1, 0], [0, 0, 1]):
        i_new, j_new, k_new = i + di, j + dj, k + dk
        if i_new >= X or j_new >= Y or k_new >= Z:
            continue
        if (i_new, j_new, k_new) in considered:
            continue
        considered.add((i_new, j_new, k_new))
        q.push((-(A[i_new] + B[j_new] + C[k_new]), i_new, j_new, k_new))
 
 
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
x=int(input())
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors
for i in make_divisors(x):
  a=0
  b=-i
  ab=0
  while b<=0 or i*ab<=x:
    ab=a**4+a**3*b+a**2*b**2+a*b**3+b**4
    if i*ab==x:
      print(a,b)
      sys.exit()
    a+=1
    b+=1

### FIXED CODE ###

import sys
x=int(input())
lim=10**3
for i in range(-lim,lim):
  for j in range(-lim,lim):
    if i**5-j**5==x:
      print(i,j)
      sys.exit()