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

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

max_length = max(melodies)
dp = [-1] * (max_length + 394)
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for s, l, p in phrases:
        for j in range(s, l + 1):
            dp[i + j] = max(dp[i + j], c + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

### FIXED CODE ###

from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [dp[melody] for melody in melodies]
print(-1 if -1 in results else '\n'.join(map(str, results)))
### BUGGY CODE ###

def main():
	s = list(str(input()))
	q = int(input())
	qu = [list(map(str,input().split())) for x in range(q)]

	for i in range(q):
		if qu[i][0] != '1':
			if qu[i][1] == '1':
				s.insert(0,qu[i][2])
			else:
				s.append(qu[i][2])
		else:
			s.reverse()

	print(''.join(map(str,s)))

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	s = str(input())
	q = int(input())
	shiji = 1
	rcount = 0
	from collections import deque
	s = deque(s)
	for i in range(q):
		qu = list(map(str,input().split()))
		if qu[0] != '1':
			if shiji == 1:
				if qu[1] == '1':
					s.appendleft(qu[2])
				else:
					s.append(qu[2])
			else:
				if qu[1] == '2':
					s.appendleft(qu[2])
				else:
					s.append(qu[2])
		else:
			shiji *= -1
			rcount += 1
	if rcount % 2 == 0:
		print(''.join(map(str,s)))
	else:
		s.reverse()
		print(''.join(map(str,s)))

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

n = int(input())

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

ans = 1

for i in range(n):
    ans *= a[i]
    
if ans > 1e18:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

n = int(input())

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

ans = 1

for i in range(n):
   if a[i] == 0:
        print(0)
        exit()

for i in range(n):
    ans *= a[i]
    if ans > 1e18:
        print(-1)
        exit()

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

from collections import deque

# 命令数入力
n = int(input())
# 命令入力
order_list = [input().split() for i in range(n)]


# 双方向連結リスト
doubly_linked_list = deque()

for order in order_list:
    
   
    
    if order[0] == "insert":
        doubly_linked_list.appendleft(order[1])
    
    elif order[0] == "delete":
        if order[1] in doubly_linked_list:
            doubly_linked_list.remove(order[1])
    
    elif order[0] =="deleteFirst":
        doubly_linked_list.popleft()
    
    elif order[0] == "deleteLast":
        doubly_linked_list.pop()
        
# 最終結果出力
print(*doubly_linked_list)


### FIXED CODE ###

from collections import deque

# 命令数入力
n = int(input())
# 命令入力
# order_list = [input().split() for i in range(n)]


# 双方向連結リスト
doubly_linked_list = deque()

for _ in range(n):
    
    order = input().split()
    
    if order[0] == "insert":
        doubly_linked_list.appendleft(order[1])
    
    elif order[0] == "delete":
        if order[1] in doubly_linked_list:
            doubly_linked_list.remove(order[1])
    
    elif order[0] =="deleteFirst":
        doubly_linked_list.popleft()
    
    elif order[0] == "deleteLast":
        doubly_linked_list.pop()
        
# 最終結果出力
print(*doubly_linked_list)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
ans = 0
for i in range(a,b+1):
  if i % c != 0:
    if i % d != 0:
      ans += 1
print(ans)


### FIXED CODE ###

A,B,C,D = map(int,input().split())

def gcd(a,b):
  while b:
    a,b = b,a%b
  return a

def F(N,C,D):
  x = N
  x -= N//C
  x -= N//D
  lcm = C*D//gcd(C,D)
  x += N//lcm
  return x

answer = F(B,C,D) - F(A-1,C,D)
print(answer)
### BUGGY CODE ###

import itertools

N = int(input())
s = []
for _ in range(N):
    b = list(input())
    b.sort()
    c = ''.join(b)
    s.append(c)

count = 0
for v in itertools.combinations(s, 2):
    if v[0] == v[1]:
        count += 1

print(count)

### FIXED CODE ###

import itertools
from math import factorial
from scipy.misc import comb

N = int(input())
s = {}
for _ in range(N):
    b = list(input())
    b.sort()
    c = ''.join(b)
    if not c in s:
        s[c] = 1
    else:
        s[c] += 1

a = [comb(v, 2, exact=True) for v in s.values()]
print(sum(a))
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
l=[[] for i in range(m)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(-b)
tmp=[]
ans=0
for i in range(m):
  tmp+=l[i]
  heapq.heapify(tmp)
  if len(tmp)>0:
    ans+= heapq.heappop(tmp)
print(-ans)

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[] for i in range(m)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(-b)
tmp=[]
heapq.heapify(tmp)
ans=0
for i in range(m):
  for j in l[i]:
    heapq.heappush(tmp,j)
  if len(tmp)>0:
    ans+= heapq.heappop(tmp)
print(-ans)
### BUGGY CODE ###

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

AA = [0]*1000000

for i in range(N):
    j = 1
    while (j*A[i]<=1000000):
        AA[j*A[i]-1] += 1
        j += 1

ans = 0

for i in range(N):
    if AA[A[i]-1] == 1:
        ans += 1
        
print(ans)

### FIXED CODE ###

import math
N = int(input())
A = list(map(int,input().split()))
M = max(A)
cnt = [0 for i in range(M)]
for i in range(N):
    if cnt[A[i]-1] != 0:
        cnt[A[i]-1] = 2
    else:
        j = A[i]-1
        while j<M:
            cnt[j] += 1
            j += A[i]

ans = 0
for i in range(N):
    if cnt[A[i]-1] == 1:
        ans += 1
        
print(ans)
### BUGGY CODE ###

from collections import deque
N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]

def calc(x): # type(x) == str型
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

q = deque([1])
ans = 0
while q:
    tmp = q.popleft()
    tmp = str(tmp)
    if len(tmp) == N:
        ans = max(ans, calc(tmp))
    else:
        for i in range(int(tmp[-1]), M+1):
            q.append(tmp+str(i))

print(ans)

### FIXED CODE ###

from collections import deque


# 数列の点数を計算する関数
def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b - 1] - seq[a - 1] == c:
            score += d

    return score


n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]

ans = 0

que = deque()

# 数列の1番目、[1]～[m]までキューに追加しますが、
# 実は、この問題は数列の最初が[1]の場合だけを考えても解けます。
for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.popleft()

    if len(seq) == n:
        # 長さがnになったので、得点を計算します
        score = calc(seq)
        ans = max(ans, score)
    else:
        # 次に追加する数字は、下限が今の数列の一番後ろの数字、上限がmです
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)

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

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

lcm = A[0]

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

ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

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

ans = 0
for a in A:
    ans += (lcm % MOD) * pow(a, MOD - 2, MOD)
    ans %= MOD

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

x = int(input())
n = 10 ** 9
for b in range(n):
    a = (x + b ** 5) ** 0.2
    if a == int(a.real):
        a = int(a.real)
        break
    b *= -1
    a = (x + b ** 5) ** 0.2
    if a == int(a.real):
        a = int(a.real)
        break
print(a, b)

### FIXED CODE ###

x = int(input())
for a in range(-118, 120):
    for b in range(-119, 119):
        if a ** 5 - b ** 5 == x:
            print(a, b)
            exit()
### BUGGY CODE ###

N = int(input())

dp = [1] * (N + 1)
ans = 1
for i in range(2, N + 1):
    for j in range(i, N + 1, i):
        dp[j] += 1
    ans += i * dp[i]
    
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1, N + 1):
    j = N // i
    ans += i * (j * (j + 1) // 2)

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

from bisect import bisect_left,bisect
import sys
 
N=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
b=list(map(int,sys.stdin.readline().split()))
ans=0
for i in range(29):
  a_nex=list(map(lambda x:x%2**(i+1),a))
  b_nex=sorted(list(map(lambda x:x%2**(i+1),b)))
  l=0
  for k in a_nex:
    p=bisect_left(b_nex,2**i-k-0.1)
    q=bisect(b_nex,2*2**i-1-k)
    r=bisect_left(b_nex,3*2**i-k-0.1)
    s=bisect(b_nex,4*2**i-1-k)
    l+=q-p+r-s
  if l%2==1:
    ans+=1<<i
print(ans)   
  


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p=0
for i in range(n):
    if i+1 in a[p:]:
        p+=a[p:].index(i+1)
    else:
        ans=i
        break
else:
    ans=n
print(n-ans if ans>0 else -1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=ans=0
for i in range(1,n+1):
    for j in range(p,n):
        if i==a[j]:
            p=j
            break
    else:
        ans=i-1
        break
else:
    ans=n
print(n-ans if ans>0 else -1)
### BUGGY CODE ###

n = input()
n = int(n)
lin = input().split()
# 要素の個数を求める
dic_s = {}
for c in lin:
  dic_s.setdefault(c, 0)
  dic_s[c] += 1
# 1つしかない要素は計算対象外
dic_cp = dic_s.copy()
for key, value in dic_cp.items():
  if value == 1:
    del dic_s[key]
dic_tot = {}
for c in lin:
  # 1度求めたら再計算しない
  # 同じ数字が多いと時間短縮
  if dic_tot.get(c):
    print(int(dic_tot[c]))
  else:
    # 指定数値を除いた2つを選ぶ
    tot = 0
    for key,value in dic_s.items():
      v = value
      if key == c:
        v -= 1
      tot += v * (v - 1) / 2
    dic_tot.setdefault(c,tot)
    print(int(tot))

### FIXED CODE ###

n = input()
n = int(n)
lin = input().split()
# 要素の個数を求める
dic_s = {}
for c in lin:
  dic_s.setdefault(c, 0)
  dic_s[c] += 1
# ペアの総数
tot = 0
for key,value in dic_s.items():
  v = value
  tot += v * (v - 1) / 2
# print(int(tot))
# 指定位置のペアを除く
for c in lin:
  if tot > 0:
    v = dic_s[c]
    print(int(tot-(v-1)))
  else:
    print(0)
### BUGGY CODE ###

k , s = map(int , input().split())

ans = 0

for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i+j+k == s:
                ans += 1
                
print(ans)

### FIXED CODE ###

k , s = map(int , input().split())

ans = 0

for i in range(k+1):
    for j in range(k+1):
            if 0 <= s-i-j <= k:
                ans += 1
                
print(ans)
### BUGGY CODE ###

import itertools

N, K = map(int, input().split())
a = list(map(int, input().split()))
beautiful_num = []
bit_mask = []

for i in range(N):
    for j in range(N):
        if i <= j:
            temp = [0] * N
            for k in range(i, j+1):
                temp[k] = 1
            bit_mask.append(temp)

for bit in bit_mask:
    temp = 0
    for b, num in zip(bit, a):
        if b == 1:
            temp += num
    beautiful_num.append("{:040b}".format(temp))

ma_b_cnt = 0
target_set = None

for i in range(40):
    if target_set is None:
        for b in beautiful_num:
            if b[i] == "1":
                ma_b_cnt += 1
        if ma_b_cnt < K:
            ma_b_cnt = 0
        else:
            target_set = set([b for b in beautiful_num if b[i] == "1"])
    else:
        count = 0
        for b in target_set:
            if b[i] == 0:
                count += 1
        if len(target_set) - count >= K:
            for b in target_set:
                if b[i] == 0:
                    target_set.remove(b)
        else:
            break

result = 0
for comb in itertools.combinations(target_set, K):
    temp = bin(int(comb[0], 2))
    for b in comb:
        temp = bin(int(b, 2) & int(temp, 2))
    temp = int(temp, 2)
    if temp > result:
        result = temp

print(result)

### FIXED CODE ###

import itertools

N, K = map(int, input().split())
a = list(map(int, input().split()))
beautiful_num = []

for i in range(N):
    temp = 0
    for n in a[i:]:
        temp += n
        beautiful_num.append("{:040b}".format(temp))

ma_b_cnt = 0
target_set = None

result = 0
for i in range(40):
        for b in beautiful_num:
            if b[i] == "1":
                ma_b_cnt += 1
        if ma_b_cnt >= K:
            result += 2**(40-i-1)
            beautiful_num = [b for b in beautiful_num if b[i] == "1"]
        ma_b_cnt = 0

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

n = int(input())
power = 1
for i in range(1,n+1):
    power *= i

print(power % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
power = 1
for i in range(1,n+1):
    power *= i
    power = power % (10 ** 9 + 7)

print(power % (10 ** 9 + 7))
### BUGGY CODE ###

a, b, x = map(int, input().split())

ans = 0
p = a
while p <= b:
    if p%x == 0:
        break
    p += 1

t = b-p
s = t//x
ans = s + 1

print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())

p = 0
y = int(b//x) + 1

i = 1
#for i in range(1,y):
while x*i <= b:
    if a <= x*i:
        p = x*i
        break
    i += 1

if p != 0:
    t = b-p
    s = t//x
    ans = s + 1
    if a == 0:
        ans += 1
    print(ans)
elif a == 0:
    print(1)
else:
    print(0)
### BUGGY CODE ###

nums = [int(e) for e in input().split()]
Min=nums[0]
y=nums[1]
t=True
while t:
    a = abs(Min - y)
    if(a<Min):
        Min = a
    elif(a>Min):
        break
print(Min)

### FIXED CODE ###

nums = [int(e) for e in input().split()]
Min=nums[0]
y=nums[1]
ans = Min % y
t = True
if (ans <= Min):
    Min = ans
    while t:
        a = abs(Min - y)
        if(a<Min):
            Min = a
        elif(a>Min):
            break
    print(Min)
else:
    print(ans)
### BUGGY CODE ###

#二分探索
from bisect import bisect_left
#input
N = int(input())
#print(N)

A = sorted(list(map(int, input().split()))) #この表記について...
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
#print(A,B,C)

#sort 昇順に並び替え
#A.sort()
#B.sort()
#C.sort()

#3重を考えるとC<B<A
ans = 0
for i in range(N):
    M = bisect_left(B, C[i])
    if M == 0:
        continue
    for j in range(M):
        ans += bisect_left(A,B[j])
print(ans)

### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right
#input
N = int(input())
#print(N)

A = sorted(list(map(int, input().split()))) #この表記について...
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
#print(A,B,C)

#sort 昇順に並び替え
#A.sort()
#B.sort()
#C.sort()
ans = 0
for i in range(N):
    ab = bisect_left(A,B[i])
    bc = N-bisect_right(C,B[i])
    #print(ab, end='  ')
    #print(bc)
    ans += ab*bc
print(ans)
### BUGGY CODE ###

from functools import reduce
import math


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
gcdsum = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            #print(gcd(a, b, c))
            gcdsum += int(gcd(a, b, c))
print(gcdsum)


### FIXED CODE ###

from functools import reduce
import math


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
gcdsum = K*K*K
gcd_ab = []
ab_list = []
for a in range(1, K + 1):
    for b in range(1, K + 1):
        #print(str(gcd(a, b))+', a:'+str(a)+', b:'+str(b))
        if gcd(a, b) != 1:
            ab_list.append(a)
            ab_list.append(b)
            gcd_ab.append(ab_list)
            ab_list = []
for ab in gcd_ab:
    ab = gcd(ab[0], ab[1])
    for c in range(1, K+1):
        if gcd(ab, c) != 1:
            #print(gcd(ab, c))
            gcdsum += gcd(ab, c)-1

print(gcdsum)
### BUGGY CODE ###

h, w = map(int, input().split(' '))
a1 = 0
for i in range(0, h + w):
    if((h % (2 ** 32) == 0) or (w % (2 ** 32) == 0) or ((h * w) % (2 ** 32) == 0)):
        a1 = 0
    elif(((h * w) % 2) == 1):
        a1 = ((h * w) // 2) + 1
    elif(((h * w) % 2) == 0):
        a1 = (h * w) // 2
print(a1)

### FIXED CODE ###

h, w = map(int, input().split(' '))
a1 = 0
if ((h == 1) or (w == 1)):
    a1 = 1
elif(((h * w) % 2) == 1):
    a1 = ((h * w) // 2) + 1
elif(((h * w) % 2) == 0):
    a1 = (h * w) // 2
print(a1)
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    #N = [list(map(int, input().split())) for i in range(3)]

    A.sort()
    B.sort()
    C.sort()

    import bisect
    cnt = 0
    for ai in range(n):
        j = bisect.bisect_right(B, A[ai])

        for bi in range(j, n):
            k = bisect.bisect_right(C, B[bi])
            cnt += n - k
        #print(cnt)

    print(cnt)
    # print(A)
    # print(B)
    # print(C)

resolve()

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    #N = [list(map(int, input().split())) for i in range(3)]

    A.sort()
    B.sort()
    C.sort()

    import bisect
    cnt = 0
    for bi in B:
        a_ok = bisect.bisect_left(A, bi)
        c_ok = bisect.bisect_right(C, bi)
        cnt += a_ok * (n - c_ok)
    print(cnt)

resolve()
### BUGGY CODE ###

K = int(input())
s = 0
for i in range (1,K + 1):
    for j in range (i + 1,K + 1):
        for k in range (j + 1,K + 1):
            for x in range (66):
                a = min(i,K//3) - x
                if i%a == 0 and j%a == 0 and k%a == 0:
                    s = s + 6 * a
                    break
for i in range(1,K + 1):
    for j in range (i + 1,K + 1):
        for x in range (100):
            a = min(i,K//2) - x
            if i%a == 0 and j%a == 0:
                    s = s + 6 * a
                    break
for i in range(1,K + 1):
    s = s + i

print(s)

### FIXED CODE ###

K = int(input())
s = 0
def gcd(a,b):
    if a == 1 or b == 1:
        return 1
    elif a == 0 or b == 0:
        return max(a,b)
    else:
        if a > b:
            return gcd(a%b,b)
        else:
            return gcd(a,b%a)
for i in range (1,K + 1):
    for j in range (i + 1,K + 1):
        x = gcd(i,j)
        for k in range (j + 1,K + 1):
            s = s + 6 * gcd(x,k)
for i in range(1,K + 1):
    for j in range (i + 1,K + 1):
        s = s + 6 * gcd(i,j)
                    
for i in range(1,K + 1):
    s = s + i

print(s)
### BUGGY CODE ###

import collections
N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))
def taikaku(A):
    n = len(A)
    b = True
    for i in range(n):
        for j in range(n):
            if A[j][i] != A[i][j]:
                b = False
                break
        if not b:
            break
    return(b)
ans = 0
for i in range(N):
    if taikaku(S[i:]+S[:i]):
        ans += N
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))
def taikaku(A):
    n = len(A)
    b = True
    for i in range(n):
        for j in range(i+1):
            if A[j][i] != A[i][j]:
                b = False
                break
        if not b:
            break
    return(b)
ans = 0
for i in range(N):
    if taikaku(S[i:]+S[:i]):
        ans += N
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
ks = list(map(int,input().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')

### FIXED CODE ###

import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')
### BUGGY CODE ###

'''
Created on 2020/09/08

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

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

  d=[]
  for i in A:
    for j in B:
      d.append(i+j)
  d.sort(reverse=True)
  d=d[:K]
  ans=[]
  for k in d:
    for l in C:
      ans.append(k+l)
  ans.sort(reverse=True)
  for m in range(K):
    print(ans[m])
  return
main()



### FIXED CODE ###

'''
Created on 2020/09/08

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

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

  d=[]
  for i in A:
    for j in B:
      d.append(i+j)
  d.sort(reverse=True)
  d=d[:K]
  ans=[]
  for k in d:
    for l in C:
      ans.append(k+l)
  ans.sort(reverse=True)
  for m in range(K):
    print(ans[m])
  return
main()
### BUGGY CODE ###

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

for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)

for i in range(1,N+1):
  print(count[i])
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
ans = []
for i in range(1, N+1):
    ans.append(str(A.index(i)+1))
print(' '.join(ans))

### FIXED CODE ###

N = int(input())
A = dict(zip(map(int, input().split()), [i for i in range(1, N+1)]))

for i in range(1, N + 1):
    print(A[i], end=' ')