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

import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[set([])]*2*num
def init(S):
    for i in range(n):
        SEG[i+num-1]=set([S[i]])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = set(x)
    while k:
        k = (k-1)//2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    ans=set([])
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(s-1,t)
    if a=='2':
        s=int(s)
        t=int(t)
        print(len(query(s-1,t)))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[0]*2*num
def word_num(a):
    return 1<<(ord(a)-96)
def init(S):
    for i in range(n):
        SEG[i+num-1]=word_num(S[i])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = word_num(x)
    while k:
        k-=1
        k//=2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    ans=0
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p //=2
        q-=1
        q//=2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(s-1,t)
    if a=='2':
        s=int(s)
        t=int(t)
        print(bin(query(s-1,t)).count('1'))
### BUGGY CODE ###

N = int(input())
S = [list(input()) for i in range(N)]
for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2
ans = 0
for i in range(N-1):
    Si = S[i]
    for j in range(i+1,N):
        Sj = S[j]
        if Si == Sj:
            ans += 1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2

ans = 0
Sc = collections.Counter(S).most_common()
for s in Sc:
    ans += s[1]*(s[1]-1)//2

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

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in range(2, n+2):
    if i - 1 in a:
        if dp[i-1] == 0:
            print(0)
            sys.exit()
        else:
            dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

### FIXED CODE ###

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

safe = sorted(set(range(1,n+1)) - set(a))
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in safe:
    dp[i+1] = (dp[i] + dp[i-1]) % mod

print(dp[-1])
### BUGGY CODE ###

import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = [i for i in range(300001) if x[i] == mx]
y1 = [i for i in range(300001) if y[i] == my]
z1 = list(itertools.product(x1, y1))
if all(i in z for i in z1): print(mx + my - 1)
else: print(mx + my)

### FIXED CODE ###

import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = x.count(mx)
y1 = y.count(my)
z1 = x1 * y1
for i, j in z:
    if x[i] == mx and y[j] == my:
        z1 -= 1
if z1: print (mx + my)
else: print (mx + my - 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,k,X):
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        return max(X[0][1]*i + X[1][1]*((N-i*X[0][0])//X[1][0]) + (N-i*X[0][0])%X[1][0] for i in range(N//X[0][0]+1))

    if k == 3:
        return max(X[0][1]*i + X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for i in range(N//X[0][0]+1) for j in range((N-i*X[0][0])//X[1][0]+1))
        
        dp = np.zeros((k, N+1), dtype=int)
        dp[0] = X[0][1]*(np.arange(N+1)//X[0][0]) + np.arange(N+1)%X[0][0]
        for i in range(1,k):
            d = X[i][1]*(np.arange(N+1)//X[i][0]) + np.arange(N+1)%X[i][0]
            for w in range(1, N+1):
                dp[i,w] = np.max(dp[i-1,w::-1] + d[:w+1])
        N = dp[k-1][N]
        return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, len(X), X)
    res = N

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
import heapq
heap = []
for i in range(n):
  m = 0
  for j in range(i,n-1):
    if h[j] >= h[j+1]:
      m += 1
    else:
      break
  heapq.heappush(heap, -m)
print(-heapq.heappop(heap))

### FIXED CODE ###

n = int(input())
H = list(map(int, input().split()))
A = [0]*(n*1)
for i in range(1,n):
  A[-(i+1)] = (A[-i] + 1 if H[-(i+1)] >= H[-i] else 0)
print(max(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(1,n+1):
    for j in range(n-i+1):
        if sum(a[j:j+i]) == 0:
            count += 1
print(count)

### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))
b = {0:0}
c = 0
for i in range(n):
    c = c+a[i]
    if c in b:
        b[c] += 1
    else:
        b[c] = 0
d = list(b.values())
ans = 0
for i in d:
    ans+= ((i+1)*i)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = map(int, input())
A = list(map(int, input().split()))

while len(A) >= 2:
    x = A.pop(A.index(max(A)))
    n = x
    for i in range(len(A)):
        if x % A[i] > 0:
            n = min(n, x % A[i])

    if n == x:
        pass
    else:
        A.append(n)

print(A[0])


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = map(int, input())
A = list(map(int, input().split()))

while len(A) >= 2:
    idx = A.index(min(A))
    x = A.pop(idx)
    B = list()
    for i in range(len(A)):
        if A[i] % x != 0:
            B.append(A[i] % x)
    B.append(x)
    A = B[:]

print(A[0])
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [[''] * W for _ in range(H)]
for _ in range(H):
    S = input()
    for __ in range(W):
        maze[_][__] = S[__]

Light = [[[0, 0]for _ in range(W)] for __ in range(H)]


for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        if Light[i][j][0] == 0:
            num = 0
            while True:
                num += 1
                if i + num >= H:
                    break
                if maze[i+num][j] == '#':
                    break
            for k in range(num):
                Light[i+k][j][0] = num


        if Light[i][j][1] == 0:
            num = 0
            while True:
                num += 1
                if j + num >= W:
                    break
                if maze[i][j + num] == '#':
                    break
            for k in range(num):
                Light[i][j+k][1] = num

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, Light[i][j][0] + Light[i][j][1])
print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]
Ans = [[[-1, -1]for __ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            if Ans[i-1][j][0] != -1:
                Ans[i][j][0] = Ans[i-1][j][0]
            else:
                num0 = 0
                while True:
                    num0 += 1
                    if i + num0 >= H:
                        break
                    elif S[i+num0][j] == '#':
                        break
                Ans[i][j][0] = num0

            if Ans[i][j-1][1] != -1:
                Ans[i][j][1] = Ans[i][j-1][1]
            else:
                num1 = 0
                while True:
                    num1 += 1
                    if j + num1 >= W:
                        break
                    elif S[i][j+num1] == '#':
                        break
                Ans[i][j][1] = num1

        ans = max(ans, sum(Ans[i][j]))
print(ans-1)
### BUGGY CODE ###

n,m,s,t=map(int,input().split())
import numpy as np
u,v,a,b=map(np.array,zip(*[list(map(int,input().split())) for i in range(m)]))
from scipy.sparse import csr_matrix
g1=csr_matrix((a,(u-1,v-1)),shape=(n,n))
g2=csr_matrix((b,(u-1,v-1)),shape=(n,n))
from scipy.sparse.csgraph import dijkstra
d1=dijkstra(g1,directed=False,indices=s-1)
d2=dijkstra(g2,directed=False,indices=t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')

### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[map(int,input().split()) for i in range(m)]
inf=10**20
c1=[[] for i in range(n)]
c2=[[] for i in range(n)]
for u,v,a,b in uvab:
    c1[u-1].append((v-1,a))
    c1[v-1].append((u-1,a))
    c2[u-1].append((v-1,b))
    c2[v-1].append((u-1,b))
from heapq import heappop,heappush
def dij(c,N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v,w in c[u]:
            if w<inf:
                temp=d[u]+w
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d1=dij(c1,n,s-1)
d2=dij(c2,n,t-1)
r=[0]*n
for i in range(n):
    r[-i-1]=max(r[-i],10**15-int(d1[-i-1])-int(d2[-i-1]))
print(*r,sep='\n')
### BUGGY CODE ###

import sys

import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(s, sh, sw, gh, gw, c, ans):
    N = np.sum(s)  # num of strawberry
    if N == 1:
        ans[sh:gh + 1, sw:gw + 1] = c
        c += 1
        return c
    # Horizontal division
    for h in range(gh - sh + 1):
        if 0 < np.sum(s[:h, :]) < N:
            c = dfs(s[:h, :], sh, sw, sh + (h - 1), gw, c, ans)
            c = dfs(s[h:, :], sh + h, sw, gh, gw, c, ans)
            return c
    # Vertical division
    for w in range(gw - sw + 1):
        if 0 < np.sum(s[:, :w]) < N:
            c = dfs(s[:, :w], sh, sw, gh, sw + (w - 1), c, ans)
            c = dfs(s[:, w:], sh, sw + w, gh, gw, c, ans)
            return c


def main():
    H, W, K = map(int, input().split())
    s = [None] * H
    s = np.full(shape=(H, W), fill_value=False, dtype=bool)
    for i in range(H):
        s[i] = [j == "#" for j in input().rstrip()]

    ans = np.zeros(shape=(H, W), dtype=int)
    _ = dfs(s, 0, 0, H - 1, W - 1, 1, ans)
    for i in range(H):
        print(" ".join(map(str, ans[i])))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    s = np.zeros(shape=(H, W), dtype=np.bool)
    for i in range(H):
        s[i] = tuple(map(lambda x: True if x == "#" else False, input().rstrip()))

    ans = np.zeros(shape=(H, W), dtype=np.int64)
    h_keep = 0
    k = 1
    for h in range(H):
        if s[h].sum() > 0:
            indices = np.where(s[h])[0]
            ans[h_keep:h + 1] = k
            k += 1
            for idx in reversed(indices[:-1]):
                ans[h_keep:h + 1, :idx + 1] = k
                k += 1
            h_keep = h + 1
        else:
            h_keep = min(h_keep, h)

    if h_keep < H:
        h_base = h_keep - 1
        for h in range(h_keep, H):
            ans[h] = ans[h_base]

    for h in range(H):
        print(" ".join(map(str, ans[h])))


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

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

for k in range(K):
    S = [0] * N

    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])

        for j in range(l, r + 1):
            S[j] += 1

    A = S

A = [str(a) for a in A]
print(' '.join(A))


### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

n,m=[int(s)for s in input().split()]
cit=[]
for _ in range(m):
    p,y=[int(s)for s in input().split()]
    cit.append((p,y))
pref={}
for c in cit:
    p,y=c
    if p not in pref:pref[p]=[]
    pref[p].append(y)
for p in pref:
    pref[p]=sorted(pref[p])
    for i in range(len(pref[p])):
        num="%06d%06d"%(p,i+1)
        ind=cit.index((p,pref[p][i]))
        cit[ind]=num
for s in cit:
    print(s)

### FIXED CODE ###

n,m=[int(s)for s in input().split()]
pref={}
yn={}
res=[-1 for _ in range(m)]
for i in range(m):
    p,y=[int(s)for s in input().split()]
    if p not in pref:pref[p]=[]
    pref[p].append(y)
    yn[y]=i
for p in pref:
    pref[p]=sorted(pref[p])
    for i in range(len(pref[p])):
        num="%06d%06d"%(p,i+1)
        res[yn[pref[p][i]]]=num
for s in res:print(s)
### BUGGY CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if not [cand_h[i], cand_w[j]] in object:
            ans = h_max + w_max
            break
            break           
else:
   ans += 1
print(ans) 

### FIXED CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
cand_h = set(cand_h)
cand_w = set(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))
### BUGGY CODE ###

n = int(input())
s = input()
count = 0

for i in range(len(s)):
        for j in range(i, len(s)):
            if s[j] != s[i]:
                for k in range(j, len(s)):
                    if s[k] != s[i] and s[k] != s[j] and j - i != k - j:
                        count += 1
print(count)

### FIXED CODE ###

import math

n = int(input())
s = input()
count = 0

rCount = s.count("R")
gCount = s.count("G")
bCount = s.count("B")
ans = rCount * gCount * bCount

for dis in range(1, math.ceil(len(s) / 2)):
    for i in range(dis, len(s) - dis):
        if s[i-dis] != s[i] and s[i-dis] != s[i+dis] and s[i] != s[i+dis]:
            ans -= 1
print(ans)
### BUGGY CODE ###


l = list(map(int, input().split()))
prices = list(map(int, input().split()))

for i in range(l[1]):
    prices.sort(reverse = True)
    prices[0] = int(prices[0] / 2)

print(sum(prices))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
values = list(map(int, input().split()))
sortedValues = []

for v in values:
    heapq.heappush(sortedValues, (-1)*v)

for i in range(M):
    heapq.heappush(sortedValues, int((heapq.heappop(sortedValues) * 1/2)))

print((-1) * sum([heapq.heappop(sortedValues) for i in range(len(sortedValues))]))
### BUGGY CODE ###

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def solve(a,b,c,d):
  if a < b or d < b:
    return True

  cnt=gcd(b,d)
  mi=a-b
  ma=min(a-c,mi+1+cnt)
  for i in range(mi+1,ma):
    if i%cnt==0:
      return True
  return False

T=int(input())
for i in range(T):
  A,B,C,D=map(int,input().split())
  if solve(A,B,C,D):
    print("No")
  else:
    print("Yes")
    

### FIXED CODE ###

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def solve(a,b,c,d):
  if a < b or d < b:
    return True

  cnt=gcd(b,d)
  mi=a-b
  ma=a-c
  if ma-mi > cnt :
    return True
  elif ma-mi <= 1:
    return False
  elif (mi+cnt)//cnt*cnt < ma:
    return True
  else:
    return False

T=int(input())
for i in range(T):
  A,B,C,D=map(int,input().split())
  if solve(A,B,C,D):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

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

E = []
mx = 0

for i in range(N-K+1):
    a = (sum(p[i:i+K])+K)/2
    if a>mx:
        mx=a

print(mx)

### FIXED CODE ###

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

S = [0]
E = []

for i in range(0, N):
    S.append(S[i]+p[i])

for i in range(0, N-K+1):
    E.append(S[i+K]-S[i])


print((max(E)+K)/2)
### BUGGY CODE ###

def main():
	n=int(input())
#	for i in range(n):
	src = [int(item) for item in input().split()]
	dst = [int(item) for item in input().split()]
	q=set()
	s=set()
	ans=0
	def	SandQ(i):
		ri=i+1
		li=i-1
		if i==0:li=n-1
		if i==n-1:ri=0
		x=0
		if dst[i]-src[i]>=dst[ri]+dst[li]:
			x=(dst[i]-src[i])//(dst[ri]+dst[li])
			dst[i]-=(dst[ri]+dst[li])*x
			q.add(li)
			q.add(ri)
		if dst[i]<=src[i]:
			s.add(i)
#		print (i,dst,x)
		return x;
#	print(src)
#	print(dst)
	for i in range(n):
		ans+=SandQ(i)
	while len(q)>0:
		i=q.pop()
		ans+=SandQ(i)
	if len(s)!=n:print(-1)
	else:print(ans)
#	print(dst)
main()


### FIXED CODE ###

def main():
	n=int(input())
	src = [int(item) for item in input().split()]
	dst = [int(item) for item in input().split()]
	ans=0
	def	SandQ(i):
		ri=i+1
		li=i-1
		if i==0:li=n-1
		if i==n-1:ri=0
		x=0
		if dst[i]-src[i]>=dst[ri]+dst[li]:
			x=(dst[i]-src[i])//(dst[ri]+dst[li])
			dst[i]-=(dst[ri]+dst[li])*x
			x+=SandQ(li)
			x+=SandQ(ri)
		return x;
	for i in range(n):
		ans+=SandQ(i)
	for i in range(n):
		if src[i]!=dst[i]:
			print(-1)
			exit()
	else:print(ans)
main()
### BUGGY CODE ###

import heapq

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

# A_q = Heapq(A, True)
# B_q = Heapq(B, True)
# C_q = Heapq(C, True)
# pop_c_list = []
# pop_b_list = []
#
# max_list = []
# for i in range(min(X, K)):
#     a = A_q.pop()
#     for j in range(min(Y, K)):
#         b = B_q.pop()
#         pop_b_list.append(b)
#         for k in range(min(Z, K)):
#             c = C_q.pop()
#             pop_c_list.append(c)
#             max_list.append(a+b+c)
#         for pop_c in pop_c_list:
#             C_q.push(pop_c)
#     for pop_b in pop_b_list:
#         B_q.push(pop_b)

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

max_list = []
for a in A[:K]:
    for b in B[:K]:
        for c in C[:K]:
            max_list.append(a + b + c)

max_list_q = Heapq(max_list, True)
for i in range(K):
    print(max_list_q.pop())

### FIXED CODE ###

import heapq

import itertools

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)

p = itertools.product(A, B)
A_B_list = [sum(v) for v in itertools.product(A, B)]
A_B_list.sort(reverse=True)
A_B_C_list = [sum(v) for v in itertools.product(A_B_list[:3000], C[:3000])]
A_B_C_list.sort(reverse=True)

for ans in A_B_C_list[:K]:
    print(ans)
### BUGGY CODE ###

N = int(input()) 
sub = list(map(int,input().split())) 
number = list(range(1, N+1))
cnt = 0 
t = len(sub)
for i in range(N):
    for j in range(t):
        if number[i] == sub[j]:
            cnt = cnt + 1
        
    print(cnt)
    cnt = 0



### FIXED CODE ###

N = int(input())
sub = list(map(int, input().split()))
ans = [0]*(N)
for i in sub:
    ans[i-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

from collections import Counter
S = input()
mod = 2019
p = [0] * len(S)
r = 0
for i,s in enumerate(S[::-1]):
  t = int(s)%mod
  d = (10**i)%mod
  r += t*d
  p[i] = r%mod

p.append(0)
ans = 0
c = Counter(p)
for k,n in c.most_common():
  if n > 1:
    ans += 1
  else:break
  
print(ans)

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))