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

import random
from math import sqrt, ceil

def is_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    if not temp[N]:
        return False
    return True

# スペース区切りの整数の入力
Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    
    for num in range(l, r+1, 2):
        if is_prime(num) and is_prime((num + 1)//2):
            ans += 1
    
    print(ans)

### FIXED CODE ###

def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)
### BUGGY CODE ###

from itertools import combinations
N, K = map(int, input().split())
P = list(map(int, input().split()))

ans = float('inf')

for buy_list in list(combinations(P, K)):
    ans_ = 0
    for buy in buy_list:
        ans_ += buy
    ans = min(ans, ans_)
    
print(ans)

### FIXED CODE ###

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

p_list = sorted(p_list)

print(sum(p_list[:K]))
### BUGGY CODE ###

import math

K = int(input())

ans = 0

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(math.gcd(a,b),c)

print(ans)


### FIXED CODE ###

from math import gcd

K = int(input())

ans = 0

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += gcd(gcd(a,b),c)

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

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

ans = 0
for i in range(a, b + 1):
    if i % x == 0:
        ans += 1

print(ans)


### FIXED CODE ###

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


ans = b // x - (a - 1) // x


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

n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
ans=0
for i in range(1,n+1):
    for j in range(i):
        if s[j:i] in s[i:]:
            ans=max(ans,len(s[j:i]))
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0
def z_algo(S):
    N=len(S)
    A=[0]*N
    i=1;j=0
    A[0]=l=len(S)
    while i<l:
        while i+j<l and S[j]==S[i+j]:
            j+=1
        if not j:
            i+=1
            continue
        A[i]=j
        k=1
        while l-i>k<j-A[k]:
            A[i+k]=A[k]
            k+=1
        i+=k;j-=k
    return A

for i in range(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)
### BUGGY CODE ###

a,b,k = map(int, input().split())
for i in range(k):
    if (a > 0):
        a -= 1
    elif(b > 0):
        b -= 1
print(max(a,0),max(b,0))


### FIXED CODE ###

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

if (a > k):
    a = a-k
    k = 0
else:
    k -= a
    a = 0
    
if (b > k):
    b -= k
    k = 0
else:
    b = 0
    
print(a,b)
### BUGGY CODE ###

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

CommonDivs =[]
for i in range(1, min(A, B)+1): 
    if A%i==B%i==0: 
        CommonDivs.append(i)
        
#print(CommonDivs)

from collections import deque
CommonDivs.reverse()
q = deque(CommonDivs)
ans = [q.pop()]
max_n = max(CommonDivs)
while len(q) > 0:
    a = q.pop()
    ans.append(a)
    if max_n/2 < a:
        break
    for _ in range(len(q)):
        b = q.pop()
        if b % a != 0:
            q.appendleft(b)
            
print(len(ans)+len(q))

### FIXED CODE ###

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


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

import math

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

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

import fractions
x = fractions.gcd(A, B)
divisors = make_divisors(x)
ans = 0
for d in divisors:
    if is_prime(d):
        ans += 1
print(ans)
### BUGGY CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""
import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

s = input()
question_count = s.count("?")
max_str = {"point":0,"str":""}

for i in range(2**question_count):
    swap_str = ""
    for j in range(question_count):
        if ((i>>j)&1):
            swap_str += "P"
        else:
            swap_str += "D"

    check_str = str(s)
    for char in range(question_count):
        check_str = check_str.replace("?",swap_str[char],1)
    
    point = 0
    point += check_str.count("D")
    point += check_str.count("PD")
    if max_str["point"] < point:
        max_str["point"] = point
        max_str["str"] = check_str
print(max_str["str"])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

s = input()
# question_count = s.count("?")
# max_str = {"point":0,"str":""}

# for i in range(2**question_count):
#     swap_str = ""
#     for j in range(question_count):
#         if ((i>>j)&1):
#             swap_str += "P"
#         else:
#             swap_str += "D"
#     check_str = str(s)
#     for char in range(question_count):
#         check_str = check_str.replace("?",swap_str[char],1)
    
#     point = 0
#     point += check_str.count("D")
#     point += check_str.count("PD")
#     if max_str["point"] < point:
#         max_str["point"] = point
#         max_str["str"] = check_str
#     print(point,check_str)
# print(max_str["str"])
print(s.replace("?","D"))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ans = []
for i in range(q):
  l,r = map(int, input().split())
  flg = False
  cnt = 0
  for j in range(l-1,r):
    if flg and s[j] == 'C':
      cnt += 1
      flg = False
    elif s[j] == 'A':
      flg = True
    else:
      flg = False
  ans.append(cnt)
for i in range(len(ans)):
  print(ans[i])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
tmp = [0]
cnt = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    cnt += 1
  tmp.append(cnt)

for i in range(q):
  l, r = map(int, input().split())
  print(tmp[r-1]-tmp[l-1])
### BUGGY CODE ###

N = int(input())

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

ans = 1

for a in As:
    ans *= a

if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

if 0 in As:
    print(0)
    exit()
 
ans = 1
 
for a in As:
    ans *= a
    
    if ans > 10**18:
        print(-1)
        exit()

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

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (visited[pos] != -INF):
            if (visited[pos] >= cost):
                continue
            if (update_cnt[pos] >= MAX_N):
                continue
            visited[pos] = cost
            update_cnt[pos] += 1
        else:
            visited[pos] = cost
            update_cnt[pos] += 1

        if (pos == N - 1):
            result = max(result, cost)
            if (update_cnt[N - 1] >= MAX_N):
                return (0, False)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (cost + nxt_cost > visited[nxt]):
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき

if (X+Y)%3 != 0:
    print(0)
else:

    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        print(len(list(itertools.combinations(range(n+m), n))) % (10**9+7))

### FIXED CODE ###

import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        ret = 1
        for i in range(m):
            ret = ret * ((X+Y)//3 - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        print(ret)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        group[v] = 0
        while q:
            cur_v, gid = q.popleft()
            group[cur_v] = gid
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        return -1
                    if group[cur_v] == group[next_v]:
                        return -1
                    else:
                        continue
                q.append((next_v, gid+1))
        return max(group) + 1

    ans = -1
    for i in range(N):
        ans = max(ans, bfs(i))

    print(ans)

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        group[v] = 0
        while q:
            cur_v, gid = q.popleft()
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        return -1
                    if group[cur_v] == group[next_v]:
                        return -1
                    else:
                        continue
                group[next_v] = gid + 1
                q.append((next_v, gid+1))
        return max(group) + 1

    ans = -1
    for i in range(N):
        ans = max(ans, bfs(i))

    print(ans)

main()
### BUGGY CODE ###

def insertionSort(A, n , g, in_cnt):
    lo_cnt = in_cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j>=0 and A[j]>v:
            A[j+g] = A[j]
            j = j - g
            lo_cnt = lo_cnt + 1
        A[j+g] = v
    return [A,lo_cnt]


A = []
G = []
data_num = int(input())
for i in range(data_num):
     A.append(int(input().rstrip()))

cnt = 0
gap = data_num
while True: 
    gap = gap // 2
    G.append(gap)
    A, cnt = insertionSort(A, data_num, gap, cnt)
    if gap == 1:
        break
    
print(str(len(G)))
print(" ".join(map(str,G)))
print(str(cnt))
print("\n".join(map(str,A)))

### FIXED CODE ###

def insertionSort(A, n , g, in_cnt):
    lo_cnt = in_cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j>=0 and A[j]>v:
            A[j+g] = A[j]
            j = j - g
            lo_cnt = lo_cnt + 1
        A[j+g] = v
    return [A,lo_cnt]


A = []
G = []
data_num = int(input())
for i in range(data_num):
     A.append(int(input().rstrip()))

cnt = 0
gap = data_num
while True: 
    if gap > 1:
        gap = gap // 2

    G.append(gap)
    A, cnt = insertionSort(A, data_num, gap, cnt)
    if gap == 1:
        break
    
print(str(len(G)))
print(" ".join(map(str,G)))
print(str(cnt))
print("\n".join(map(str,A)))
### BUGGY CODE ###


n = int(input())
ans = 10

def fun(a,b):
    if len(str(a)) <= len(str(b)):
        return(len(str(b)))
    else:
        return(len(str(a)))

#print(fun(125,80))


for i in range(1,n+1):
    if n % i == 0:
#        print(i,int(n/i))
        if ans > fun(i,int(n/i)):
            ans = fun(i,int(n/i))
#            print(ans)

print(ans)


### FIXED CODE ###


import math
n = int(input())
ans = 10

def fun(a,b):
    if len(str(a)) <= len(str(b)):
        return(len(str(b)))
    else:
        return(len(str(a)))

#print(fun(125,80))

b =int(math.sqrt(n+1) // 1) + 1
#print(b)

for i in range(1,b):
    if n % i == 0:
#        print(i,int(n/i))
        if ans > fun(i,int(n/i)):
            ans = fun(i,int(n/i))
#            print(ans)

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

n, q = [int(i) for i in input().split()]
s = input()
l =[]
r =[]
for i in range(q):
    l1, r1 = [int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)

memo = []
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        memo.append(i)

#print(memo)

for i in range(q):
    cnt = 0
    for j in memo:
        if l[i] <= j+1 <= r[i]-1:
            cnt+=1
    print(cnt)

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l =[]
r =[]
for i in range(q):
    l1, r1 = [int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)

Sum = [0]
for i in range(len(s)):
    if s[i-1]=="A" and s[i]=="C":
        Sum.append(Sum[i]+1)
    else:
        Sum.append(Sum[i])

#print(Sum)
for i in range(q):
    print(Sum[r[i]]-Sum[l[i]])
### BUGGY CODE ###

# DPの計算量…DPテーブルのノードの数＋エッジの数
# https://atcoder.jp/contests/dp/tasks/dp_b
# 理屈はあってるが、PythonなのでTLEになります…
import numpy as np


def chmin(a, b):
    '''a>bならbを代入して返すメソッド'''
    if a > b:
        a = b
        return a
    else:
        return a


def main():
    '''もらうDPとして実装'''
    N, K = list(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(i - K, 0), i))
    print(int(dp[i]))


main()


### FIXED CODE ###

def test():
    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(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

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


def solve():
    for a in A:
        if N % 2 == 1:
            if a % 2 == 1:
                return 0
            else:
                if a == 0 and A.count(a) != 1:
                    return 0
                elif a != 0 and A.count(a) != 2:
                    return 0
        else:
            if a % 2 == 0:
                return 0
            else:
                if A.count(a) != 2:
                    return 0
    return 2 ** (N // 2)


print(solve())


### FIXED CODE ###

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


def solve():
    cnt = {i + (1 - N % 2): 0 for i in range(0, 2 * N // 2, 2)}
    for a in A:
        if a not in cnt:
            return 0

        if N % 2 == 1:
            if a % 2 == 1:
                return 0
            cnt[a] += 1
        else:
            if a % 2 == 0:
                return 0
            cnt[a] += 1

    for key, value in cnt.items():
        if key == 0:
            if value != 1:
                return 0
        else:
            if value != 2:
                return 0

    return 2 ** (N // 2) % (10 ** 9 + 7)


print(solve())
### BUGGY CODE ###

N = int(input())
A = [int(input()) for n in range(N)]

res = []
while A:
    a = A.pop()
    if a in res:
        res.remove(a)
    else:
        res.append(a)

print(len(res))


### FIXED CODE ###

N = int(input())
A = [int(input()) for n in range(N)]
A = sorted(A)

res = []
tmp = A[0]
count = 1
for i in range(1,N):
    if A[i] == tmp:
        count += 1
    else:
        res.append(count%2 != 0)
        count = 1
    tmp = A[i]
res.append(count%2 != 0)

print(sum(res))
### BUGGY CODE ###

n,x,m=map(int,input().split())
A=[x]
ans=0
for i in range(min(n,m)):
  a_i=(A[i]**2)%m
  if i ==n-1:
    print(sum(A))
    exit()
  if a_i==0:
    print(sum(A))
    exit()
  if a_i in A:
    k=A.index(a_i)+1
    l=len(A)
    roop=A[k-1:l]
    many=(n-k+1)//(l-k+1)
    ans+=sum(A[:k-1])
    ans+=sum(roop)*many
    ans+=sum(roop[:(n-k+1)%(l-k+1)])
    print(ans)
    exit()
  A.append(a_i)

### FIXED CODE ###

N, X, M = map(int, input().split())
flag = [False for _ in range(M)]
record = list()
record.append(X)
flag[X] = 1

An = X

for i in range(M + 1):
    An = pow(An, 2, M)
    if flag[An]:
        start = flag[An]
        cnt = i + 2 - start
        cost = record[-1] - record[start - 2] if start > 1 else record[-1]
        break

    else:
        record.append(An + record[-1])
        flag[An] = i + 2

if start >= N:
    print(record[N - 1])
else:
    print(((N - start) // cnt) * cost
                + record[(N - start) % cnt + start - 1])
### BUGGY CODE ###

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

arr = [0] * N

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

print(0)


### FIXED CODE ###

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

arr = [0] * N

for i in A:
    arr[i-1] += 1

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

MOD = 10**9+7
s = input()

cumsum = {}
for key in ['A', 'B', 'C', '?']:
    cumsum[key] = [0]*(len(s)+1)
for i, ss in enumerate(s):
    for key in cumsum.keys():
        if key == ss:
            cumsum[key][i+1] = cumsum[key][i]+1
        else:
            cumsum[key][i+1] = cumsum[key][i]

ans = 0
for i in range(1, len(s)-1):
    if s[i] == 'A' or s[i] == 'C':
        continue
    
    n_a = cumsum['A'][i]
    n_c = cumsum['C'][-1] - cumsum['C'][i+1]
    n_q_left = cumsum['?'][i]
    n_q_right = cumsum['?'][-1] - cumsum['?'][i+1]

    n_left = n_a*pow(3, n_q_left) + n_q_left*pow(3, max(n_q_left-1, 0))
    n_right = n_c*pow(3, n_q_right) + n_q_right*pow(3, max(n_q_right-1, 0))
    ans += n_left*n_right

print(ans%MOD)


### FIXED CODE ###

MOD = 10**9+7
s = input()

dp = [[0]*4 for _ in range(len(s)+1)]
dp[0][0] = 1
for i, ss in enumerate(s):
    if ss == 'A':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][1] + dp[i][0])%MOD
        dp[i+1][2] = dp[i][2]
        dp[i+1][3] = dp[i][3]
    elif ss == 'B':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = (dp[i][2] + dp[i][1])%MOD
        dp[i+1][3] = dp[i][3]
    elif ss == 'C':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
        dp[i+1][3] = (dp[i][3] + dp[i][2])%MOD
    else:
        dp[i+1][0] = dp[i][0]*3%MOD
        dp[i+1][1] = (dp[i][1]*3%MOD + dp[i][0])%MOD
        dp[i+1][2] = (dp[i][2]*3%MOD + dp[i][1])%MOD
        dp[i+1][3] = (dp[i][3]*3%MOD + dp[i][2])%MOD

# for dp_ in dp: print(dp_)
print(dp[-1][3])
### BUGGY CODE ###

import numpy as np
from scipy import stats
n = int(input())
a = np.array([int(i) for i in input().split()])
x = np.hstack([a - 1, a, a + 1])
r = stats.mode(x)
print(int(r[1]))

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
x = np.hstack([a - 1, a, a + 1])
x[x < 0] = 0
r = np.bincount(x)
print(r[1:].max())
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n-1):
	ans += i+1
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import math
from functools import reduce

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

def main():
    K = int(input())
    g = 0
    for i in range(1, K+1, 1):
        for j in range(1, K+1, 1):
            for k in range(1, K+1, 1):
                g += gcd(i, j, k)         
    print(g)
main()

### FIXED CODE ###

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

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.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if i*j*k>K:
        continue
      m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)

### FIXED CODE ###

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.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)