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

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g == n:
            ans += 1
        elif (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g == n:
            ans += 1
        elif (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))

### FIXED CODE ###


S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    keta = keta % 13
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))
### BUGGY CODE ###

import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full((N+1, W+1), INF, dtype = np.int64)
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    dp[i+1] = np.minimum(dp[i+1], dp[i])
    for j in range(A, W+1):
        dp[i+1][j] = np.minimum(dp[i+1][j], dp[i+1][j-A] + B)
print(np.min(dp[N][H:W+1]))

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

n, m = map(int, input().split())
cand_path = [tuple(map(int, input().split())) for _ in range(m)]

ans = 'IMPOSSIBLE'

for i in range(2, n):
  if (1, i) in cand_path and (i, n) in cand_path:
    ans = 'POSSIBLE'
    break
  
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
all_cand = [tuple(map(int, input().split())) for _ in range(m)]

start_path_end = set([path[1] for path in all_cand if path[0]==1])
end_path_start = set([path[0] for path in all_cand if path[1]==n])

print('POSSIBLE' if start_path_end&end_path_start else 'IMPOSSIBLE')
### BUGGY CODE ###

import sys
from itertools import accumulate

import numpy as np

h, w = list(map(int, input().split()))
field = [['#.'.index(c) for c in line.rstrip()] for line in sys.stdin]
field = np.array(field)
cumsum = lambda iterable: np.array([list(accumulate(row, func=lambda x, a: (x + a) * a)) for row in iterable])
l = cumsum(field)
l += cumsum(field.T).T
l += np.fliplr(cumsum(np.fliplr(field)))
l += np.flipud(cumsum(np.flipud(field).T).T)

print(l.max() - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = []
for i in range(n):
  if a[i] in m:
    print('NO')
    exit(0)
  m.append(a[i])
print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
  if a[i] == a[i+1]:
    print('NO')
    exit(0)
print('YES')
### BUGGY CODE ###

from collections import Counter
from scipy import special
S = input()
a = [int(S[i:]) % 2019 for i in range(len(S))]
a.append(0)
b = [kv[1]*(kv[1]-1)//2 for kv in Counter(a).items() if kv[1] > 1]
print(sum(b))

### FIXED CODE ###

from collections import Counter,deque
from scipy import special
S = input()
l = [int(n) for n in S]
a = [0]
t = 0
m = 1
d = deque(l)
mod = 2019
while d:
    temp = d.pop()
    t = (t + (temp * m)) % mod
    m = (m * 10) % mod
    a.append(t%mod)
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))
### BUGGY CODE ###

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if prev[a] == 0:
      a_color=set([])
    else:
      a_color=set([G[a][prev[a]][1]])
    for b in G[a]:
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        for c in range(1,N+1):
          if c not in a_color:
            a_color.add(c)
            colors.append((G[a][b][0],c))
            G[a][b][1]=G[b][a][1]=c
            if c > cmax: cmax = c
            break
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])

### FIXED CODE ###

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)
b = np.array(input().split(), dtype=np.int)
flag = False
for i in np.where(a <= b)[0]:
  mask = np.ones(n, dtype=np.bool)
  mask[i] = False
  if np.all(np.sort(a[mask]) <= np.sort(b[mask])):
    flag = True
    break
if flag:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)
b = np.array(input().split(), dtype=np.int)
arg = np.argsort(b)
a = a[arg]
b = b[arg]
arg = np.argsort(a)
if np.all(a[arg] <= b):
  i = arg[0]
  cycle_size = 1
  while i != 0:
    i = arg[i]
    cycle_size += 1
  if cycle_size == n and np.all(a[arg[1:]] > b[:-1]):
    print('No')
  else:
    print('Yes')
else:
  print('No')
### BUGGY CODE ###

S=input()
Q=int(input())
checker=-1#-1で正向き、1で反転
for _ in range(Q):
  B=input().split()
  if len(B)==3:
    T,F,C=B
  else:
    T=B[0]
    F,C="",""
    
  if T=="1":
    checker*=-1
  elif T=="2":
    if all([F=="1",checker==-1]):
      S=C+S
    elif all([F=="1",checker==1]):
      S=S+C
    elif all([F=="2",checker==-1]):
      S=S+C
    elif all([F=="2",checker==1]):
      S=C+S
print(S if checker==-1 else "".join(list(reversed(S))))

### FIXED CODE ###

S=input()
Q=int(input())
checker=-1#-1で正向き、1で反転
BUF1,BUF2="",""
for _ in range(Q):
  B=input().split()
  if len(B)==3:
    T,F,C=B
    if all([F=="1",checker==-1]):
      BUF1+=C
    elif all([F=="1",checker==1]):
      BUF2+=C
    elif all([F=="2",checker==-1]):
      BUF2+=C
    elif all([F=="2",checker==1]):
      BUF1+=C
  else:
    checker*=-1
S=BUF1[::-1]+S+BUF2
print(S if checker==-1 else S[::-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = 0
for i in range(n):
    x = a[i]
    if abs(x-m) < x:
        x -= m
    y = 0
    for j in range(i+1, n):
        y = (y + a[j]) % m
    result = (result + (x*y)) % m

if(result < 0):
    result += m
print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = 0

sum_a = 0
for i in range(n):
    sum_a = (sum_a + a[i]) % m

result = 0
for i in range(n):
    x = a[i]
    sum_a -= x
    result = (result + x*sum_a) % m

if(result < 0):
    result += m
print(result)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range([q][0]):
    l, r = map(int, input().split())
    print(s[l - 1:r]. count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [0 for i in range(n)]
for i in range(1, n):
    if s[i] == "C" and s[i - 1] == "A":
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]
for i in range([q][0]):
    l, r = map(int, input().split())
    print(a[r - 1] - a[l - 1])
### BUGGY CODE ###

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

    m = 10 ** 9 + 7
    a = [i % m for i in a]
    sum_a = [a[i] * a[j] for i in range(n) for j in range(i+1, n)]
    ans = sum(sum_a)
    print(ans % m)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or d[t]<=d[s]or'.'<m[i][j]:break
   q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
summ = 0
answer = 0
for i in range(N):
    for l in range(i):
        summ += A[l] * A[i]
answer = summ % 1000000007
print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
summ1 = 0
answer = 0
temp = 0
summ2 = 0
summ3 = 0
for i in range(N):
    summ1 += A[i]
for l in range(N):
    summ3 += A[l]
    summ2 += A[l]*(summ1-summ3)
answer = summ2 % 1000000007
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y
        

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
print(recursion(s1,s2,0,0,len(s1),len(s2),dp))

### FIXED CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)
### BUGGY CODE ###

import math

K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(math.gcd(i, j),k)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input()) + 1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      ans += gcd(gcd(i, j),l)
print(ans)
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
t=0
for i in range(n+1):
    for j in range(m+1):
        if sum(a[0:i])+sum(b[0:j])<=k and t<=i+j:
            t=i+j
print(t)

### FIXED CODE ###

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

a,b=[0],[0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])


ans,j=0,M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j]>K-a[i]:
        j-=1
    ans =max(ans,i+j)

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

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
P = list(map(float, input().split()))

# suml = [[1 for _ in range(N)] for _ in range(N+1)]
suml = [[1 for x in range(round+1)] for round in range(N+1)]
# print(sum(p) / 3)

# for foreachCoinIndex,p in enumerate(P):
for e,p in enumerate(P):
    for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):

        if (es == 0):
            suml[e+1][es]   = suml[e][es] * (1-p)
        else:
            suml[e+1][es]   += suml[e][es] * (1-p)

        suml[e+1][es+1] = suml[e][es] * p


# for i in range(len(suml)):
#     print(suml[i])
#     # print(sum(suml[i][:len(suml[i])//2+1]))
#     print(sum(suml[i]))
sumA = suml[N][:len(suml[N])//2-1:-1]
sumA = sum(sumA)
print(sumA)


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
p = list(map(float, input().split()))

import numpy as np
dp = np.full(N+1, 0, dtype=np.float64)
dp[0] = 1
n_p = np.array(p)

for i in range(N):
    tmp      = np.zeros_like(dp)
    tmp[1:]  = dp[:-1] * n_p[i]
    tmp[:-1]+= dp[:-1] * (1-n_p[i])
    dp = tmp

ans = np.sum(dp[N//2+1:])
print(ans)

# for i in range(1, 1+N): # timestep
#     for j in range(0, 0+i): # pos
#         dp[j] = dp[
#     # kdp[:i] a

# suml = [[1 for x in range(round+1)] for round in range(N+1)]
# 
# for e,p in enumerate(P):
#     for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):
# 
#         if (es == 0):
#             suml[e+1][es]   = suml[e][es] * (1-p)
#         else:
#             suml[e+1][es]   += suml[e][es] * (1-p)
# 
#         suml[e+1][es+1] = suml[e][es] * p
# 
# 
# sumA = suml[N][:len(suml[N])//2-1:-1]
# sumA = sum(sumA)
# print(sumA)
### BUGGY CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, abs((to_search_x[i]-to_search_x[j])*(to_search_y[k]-to_search_y[l])))

print(ans)


### FIXED CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
points_matrix = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if (points_matrix[i][k] + points_matrix[j+1][l+1] - points_matrix[i][l+1] - points_matrix[j+1][k]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

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

N, X = map(int, input().split())
A = set(list(map(int, input().split())))
lenA = len(A)
prev = 0
while prev != lenA:
    if X in A:
        print("POSSIBLE")
        exit()
    cand = set()
    for i, a in enumerate(A):
        if i == 0:
            aa = a
            continue
        tmp = abs(aa - a)
        if tmp not in A:
            cand.add(tmp)
        A = set.union(A, cand)
    prev= len(A)
print("IMPOSSIBLE")


### FIXED CODE ###

import fractions
N, K = map(int, input().split())
A = list(map(int, input().split()))
if max(A) >= K:
    for i, a in enumerate(A):
        if i == 0:
            gcd = a
            continue
        gcd = fractions.gcd(gcd, a)
    if K % gcd == 0:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
import sys
while (H-1,W-1) not in q:
    q2=[]
    for h,w in q:
        s[h][w]=i
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
    if len(q)==0:
        break
    q=q2
    i+=1
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)

### FIXED CODE ###

H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
s[0][0]=1
while (H-1,W-1) not in q:
    q2=[]
    i+=1
    for h,w in q:
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
            s[h-1][w]=i
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
            s[h+1][w]=i
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
            s[h][w-1]=i
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
            s[h][w+1]=i
    q=q2
    if len(q)==0:
        break
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        
        if sum(ANS[a[1]:a[1]+L]) < MAX + len(ANS[a[1]:a[1]+L]) - 1 : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == MAX:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == MAX : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == MAX : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.99975
MAX = 10**9+1
ANS = [MAX]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n,x,m = map(int,input().split())
ans = 0
l = [x]

for i in range(n):
	x = (x*x)%m
	if x in l:
		break
	l.append(x)

if x == 0:
	print(sum(l))
else:
	p = l[0]
	k = 1
	Su = 0
	while p != x and k < len(l):
		Su += p
		p = l[k]
		k += 1
	l = l[k-1:]

	Su2 = 0
	for r in range((n-k)%len(l) + 1):
		Su2 += l[r]
	print(Su + ((n-k)//len(l))*sum(l) + Su2)

### FIXED CODE ###

n,x,m = map(int,input().split())
ans = 0
l = [x]
s = [0]*m
s[0] = 1

for i in range(n):
	x = (x*x)%m
	if s[x] == 1:
		break
	s[x] = 1
	l.append(x)

if x == 0:
	print(sum(l))
else:
	p = l[0]
	k = 1
	Su = 0
	while p != x and k < len(l):
		Su += p
		p = l[k]
		k += 1
	l = l[k-1:]

	Su2 = 0
	for r in range((n-k)%len(l) + 1):
		Su2 += l[r]
	print(Su + ((n-k)//len(l))*sum(l) + Su2)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])