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

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
k -= 1
shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(shortest[x][k] + shortest[y][k])

### FIXED CODE ###

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
shortest = dijkstra(adj, n, k - 1)
for i in range(q):
    x, y = map(int, input().split())
    print(shortest[x - 1] + shortest[y - 1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import heapq
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
d=[int(input()) for i in range(q)]
L1=[]
for i in range(n):
  L1.append([l[i][0]-l[i][2],1,l[i][2]])
  L1.append([l[i][1]-l[i][2],-1,l[i][2]])
L1.sort()
L2=[]
heapq.heapify(L2)
L3=[]
L3=set(L3)
ctd=0
for i in range(len(L1)):
  if ctd<q:
    while L1[i][0]>d[ctd]:
      if len(L2)!=0:
        while L2[0] not in L3:
          heapq.heappop(L2)
          if len(L2)==0:
            heapq.heappush(L2,-1)
            break
        x=heapq.heappop(L2)
        print(x)
        if x!=-1:
          heapq.heappush(L2,x)
      else:
        print(-1)
      ctd+=1
      if ctd==q:
        break
  else:
    break
  if L1[i][1]==1:
    heapq.heappush(L2,L1[i][2])
    L3.add(L1[i][2])
  else:
    L3.remove(L1[i][2])
while ctd<q:
  print(-1)
  ctd+=1

### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L1=[]
for i in range(n):
  L1.append((l[i][0]-l[i][2],1,l[i][2]))
  L1.append((l[i][1]-l[i][2],-1,l[i][2]))
for i in range(q):
  L1.append((int(input()),2,0))
L1.sort()
L2=[]
heapq.heapify(L2)
L3=[]
L3=set(L3)
for i in range(len(L1)):
  if L1[i][1]==1:
    heapq.heappush(L2,L1[i][2])
    L3.add(L1[i][2])
  elif L1[i][1]==-1:
    L3.remove(L1[i][2])
  else:
    while L2 and L2[0] not in L3:
      heapq.heappop(L2)
    if L2:
      print(L2[0])
    else:
      print(-1)
### BUGGY CODE ###

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

dp = [[[ 0 for _ in range(50*50 + 5)] for _ in range(N+1) ] for _ in range(N+1)]

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*50+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

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


### FIXED CODE ###

N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for _ in range(50*50 + 1)] for _ in range(N+1)] for _ in range(N+1)]

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(i+1):
        for k in range(50*j+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][A * i]
print(ans)
### BUGGY CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
BC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

card_list = A
for i in range(M):
    list = [BC[i][1]] * BC[i][0] 
    card_list.extend(list)

sorted_cards = sorted(card_list, reverse=True)
ans = sum(sorted_cards[:N])
print(ans)

### FIXED CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
A = [[1, i] for i in list(map(int, sys.stdin.readline().split()))]
BC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

card_list = A + BC
sorted_cards = sorted(card_list, key=lambda x: x[1], reverse=True)
n = 0
cards_sum = 0
for i in range(N):
    if sorted_cards[i][0] + n <= N:
        cards_sum += sorted_cards[i][1] * sorted_cards[i][0]
        n += sorted_cards[i][0]
    elif n < N and sorted_cards[i][0] + n > N:
        cards_sum += sorted_cards[i][1] * (N - n)
        n = N
        break
    else:
        break

print(cards_sum)
### BUGGY CODE ###

n = int(input())
i = 2

while i < 10**9:
  if i % 2 == 0 and i % n == 0:
    print(i)
    break
  i = i+1

### FIXED CODE ###

n = int(input())
if n % 2 == 0:
  print(n)
else:
  print(n*2)
### BUGGY CODE ###

import numpy as np
n = input()
a = np.array([int(i) for i in input().split()])

a_unique = np.unique(a)

out = 0
for i in a_unique:
    count = np.sum(a==i)
    if(count < i):
        out += count
    else:
        out += count - i

print(out)

### FIXED CODE ###

import numpy as np
from collections import Counter

n = input()
a = np.array([int(i) for i in input().split()])

x = Counter(a)
out = 0
for i in x:
    if(x[i] < i):
        out += x[i]
    else:
        out += x[i] - i

print(out)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
R,G,B,ans = 0,0,0,0
for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        for k in range((n-i*r-j*g)//b+1):
            if r*i+j*g+k*b==n:
                ans +=1
print(ans)

### FIXED CODE ###

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

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


X,Y,Z,K = (int(x) for x in input().split())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

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

abc = [[0,0,0]]
#next_abc = [[1,0,0],[0,1,0],[0,0,1]]
#print(A[abc[0][0]]+B[abc[0][1]]+C[abc[0][2]])

for i in range(K):
    max_v = 0
    for j in range(len(abc)):
        if A[abc[j][0]]+B[abc[j][1]]+C[abc[j][2]] > max_v:
            max_v = A[abc[j][0]]+B[abc[j][1]]+C[abc[j][2]]
            temp_j = j
            
    max_abc = abc.pop(temp_j)
    #print(max_abc)
    #print(A[max_abc[0]]+B[max_abc[1]]+C[max_abc[2]])
    print(max_v)
    
    if max_abc[0]<X-1:
        abc.append([max_abc[0]+1,max_abc[1],max_abc[2]])
    if max_abc[1]<Y-1:
        abc.append([max_abc[0],max_abc[1]+1,max_abc[2]])
    if max_abc[2]<Z-1:
        abc.append([max_abc[0],max_abc[1],max_abc[2]+1])
    abc = get_unique_list(abc)
    #print(abc)


### FIXED CODE ###

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


X,Y,Z,K = (int(x) for x in input().split())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

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

abc = [[0,0,0,A[0]+B[0]+C[0]]]
list_abc = [[0,0,0]]
#next_abc = [[1,0,0],[0,1,0],[0,0,1]]
#print(A[abc[0][0]]+B[abc[0][1]]+C[abc[0][2]])

for i in range(K):
    max_v = 0
    for j in range(len(abc)):
        if abc[j][3] > max_v:
            max_v = abc[j][3]
            temp_j = j
            
    max_abc = abc.pop(temp_j)
    #print(max_abc)
    #print(A[max_abc[0]]+B[max_abc[1]]+C[max_abc[2]])
    print(max_v)
    
    if max_abc[0]<X-1:
        if not([max_abc[0]+1, max_abc[1], max_abc[2]] in list_abc):
            abc.append([max_abc[0]+1,max_abc[1],max_abc[2],A[max_abc[0]+1]+B[max_abc[1]]+C[max_abc[2]]])
            list_abc.append([max_abc[0]+1, max_abc[1], max_abc[2]])
    if max_abc[1]<Y-1:
        if not([max_abc[0], max_abc[1]+1, max_abc[2]] in list_abc):
            abc.append([max_abc[0],max_abc[1]+1,max_abc[2],A[max_abc[0]]+B[max_abc[1]+1]+C[max_abc[2]]])
            list_abc.append([max_abc[0], max_abc[1]+1, max_abc[2]])
    if max_abc[2]<Z-1:
        if not([max_abc[0], max_abc[1], max_abc[2]+1] in list_abc):
            abc.append([max_abc[0],max_abc[1],max_abc[2]+1,A[max_abc[0]]+B[max_abc[1]]+C[max_abc[2]+1]])
            list_abc.append([max_abc[0], max_abc[1], max_abc[2]+1])
    #abc = get_unique_list(abc)
    #print(abc)
### BUGGY CODE ###

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

ball=[]

while len(ball)<=N:
    for x in range(A):
        ball.append(1)
    for x in range(B):
        ball.append(-1)

print(ball[0:N].count(1))

### FIXED CODE ###

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

r=N//(A+B)*A
s=N%(A+B)

x=r+min(A,s)
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def sol():
    s=input().rstrip()
    q=int(input())
    x=0
    for i in range(q):
        l=tuple([i for i in input().split()])
        if l[0]=="1":
            x=(x+1)%2
        elif l[1]=="1":
            if x==0: s=l[2]+s
            else: s=s+l[2]
        elif l[1]=="2":
            if x==0: s=s+l[2]
            else: s=l[2]+s
    print(s if x==0 else s[::-1])

if __name__=="__main__":
    sol()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    s=input().rstrip()
    q=int(input())
    x=0
    a,b="",""
    for i in range(q):
        l=tuple([i for i in input().split()])
        if l[0]=="1":
            x=(x+1)%2
        elif l[1]=="1":
            if x==0: a=l[2]+a
            else: b=b+l[2]
        elif l[1]=="2":
            if x==0: b=b+l[2]
            else: a=l[2]+a
    s=a+s+b
    print(s if x==0 else s[::-1])

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

# -*- coding utf-8 -*-
import functools
import operator

n=int(input())
lst=list(range(1,n+1,1))

result = functools.reduce(operator.mul, lst)

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


### FIXED CODE ###

# -*- coding utf-8 -*-
n=int(input())
ans=1

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

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

from collections import deque

h, w = map(int, input().split())

todo = deque([])
draw = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[0] * (w + 2)]
for i in range(h):
    done.append([0] + [1000 for _ in range(w)] + [0])
done.append([0] * (w + 2))

grid = [list("#" * (w + 2))]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append((i + 1, j + 1))
            done[i + 1][j + 1] = 0
    grid.append(list("#" + s + "#"))
grid.append(list("#" * (w + 2)))

while todo:
    n, m = todo.popleft()
    d = done[n][m]
    for dn, dm in draw:
        if done[n + dn][m + dm] != 1000:
            pass
        elif done[n + dn][m + dm] > d + 1:
            todo.append((n + dn, m + dm))
            done[n + dn][m + dm] = d + 1

print(max(max(i) for i in done))

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "#")
cost = np.full((h, w), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, h):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(h - 1)[::-1]:
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, w):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(w - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))
### BUGGY CODE ###

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

sum_list = [None] * (N+1)

sum_list[0] = 0
for i in range(N):
    sum_list[i+1] = sum_list[i] + A[i]

output = 0
sum_list_sorted = sorted(sum_list)
for i in range(N):
    if sum_list_sorted[i] == sum_list_sorted[i+1]:
        for j in range(i+1, N+1):
            if sum_list_sorted[i] == sum_list_sorted[j]:
                output += 1
            else:
                break

print(output)

### FIXED CODE ###

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

sum_list = [None] * (N+1)

sum_list[0] = 0
for i in range(N):
    sum_list[i+1] = sum_list[i] + A[i]

output = 0
sum_list_sorted = sorted(sum_list)
i = 0
while i < N:
    k = 1
    for j in range(i+1, N+1):
        if sum_list_sorted[i] == sum_list_sorted[j]:
            k += 1
        else:
            break
    output += k * (k-1) // 2
    i += k
    
print(output)
### BUGGY CODE ###

from sys import setrecursionlimit, stdin


def f(i, links, dp):
    if dp[i] != -1:
        return dp[i]
    if len(links[i]) == 0:
        dp[i] = 0
    else:
        dp[i] = max(f(j, links, dp) for j in links[i]) + 1
    return dp[i]


def main():
    setrecursionlimit(10 ** 6)
    readline = stdin.readline

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

    links = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, readline().split())
        links[x - 1].append(y - 1)

    dp = [-1] * N
    print(max(f(i, links, dp) for i in range(N)))


main()


### FIXED CODE ###

from sys import setrecursionlimit


def f(i, links, dp):
  if dp[i] != -1:
    return dp[i]
  if len(links[i]) == 0:
    dp[i] = 0
  else:
    dp[i] = max(f(j, links, dp) for j in links[i]) + 1
  return dp[i]


setrecursionlimit(1000000)

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

links = [[] for _ in range(N)]
for _ in range(M):
  x, y = map(int, input().split())
  links[x - 1].append(y - 1)

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))
### BUGGY CODE ###

# YouTube
def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

# 準備
md = p
n_max = p-1
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

b = [0] * p
for ai, ak in enumerate(a):
    if ak:
        b[0] = (b[0] + 1) % p
        for bi in range(p):
            b[bi] = (b[bi] - pow(-ai, p - 1 - bi, p) * com(p - 1, bi)) % p
print(*b)


### FIXED CODE ###

# YouTube
def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

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

# 準備
md = p
n_max = p-1
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

b = [0] * p
for ai, ak in enumerate(a):
    if ak:
        b[0] = (b[0] + 1) % p
        s=1
        for bi in range(p-1,-1,-1):
            b[bi] = (b[bi] - s * com(p - 1, bi)) % p
            s=(-ai*s)%p
print(*b)
### BUGGY CODE ###

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

cnt = 0
cnt_max = 0

t = 0

#aの本を全部読む場合を考える
#bを1冊ずつ増やしたときに最大になるかどうかを判定する

c = []

for i in a:
  t += i
  if t <= k:
    c.append(i)
    cnt += 1
  else:
    t -= i
    break

#print(c)
cnt_max = cnt
tmp_cnt = cnt

t_max = t

for i in range(len(c) + 1):
  if i == 0:
    pass
  else:
    t_max -= c[i-1]
    tmp_cnt -= 1
    
  #print(i, t_max, tmp_cnt)
  
  t = t_max
  cnt = tmp_cnt
  
  for j in b:
    t += j
    #print('j:', j, t)
    if t <= k:
      cnt += 1
      if cnt > cnt_max:
        cnt_max = cnt
        #print('cnt', cnt, 'max', cnt_max)
    else:
      break
      
print(cnt_max)
        


### FIXED CODE ###

from collections import deque

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = deque(list(map(int, input().split())))

cnt = 0
cnt_max = 0

t = 0

#aの本を全部読む場合を考える
#bを1冊ずつ増やしたときに最大になるかどうかを判定する

c = []

for i in a:
  t += i
  if t <= k:
    c.append(i)
    cnt += 1
  else:
    t -= i
    break

#print(c)
cnt_max = cnt
tmp_cnt = cnt

t_max = t

c.reverse()
for i in range(len(c) + 1):
  d = []
  
  if i == 0:
    pass
  else:
    t_max -= c[i-1]
    tmp_cnt -= 1
    
  #print(i, t_max, tmp_cnt, c[i-1])
  
  t = t_max
  cnt = tmp_cnt
  
  for j in b:
    t += j
    #print('j:', j, t)
    if t <= k:
      cnt += 1
      d.append(j)
      t_max = t
      if cnt > cnt_max:
        cnt_max = cnt
        #print('cnt', cnt, 'max', cnt_max)
    else:
      break
      
  for i in range(len(d)):
    b.popleft()
    tmp_cnt += 1
      
print(cnt_max)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  ans %= MOD
 
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  # ans %= MOD
 
print(ans%MOD)
### BUGGY CODE ###

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

ans = 0

for i in range(1, 2**n):
    sum = 0
    num = 0
    for j in range(n):
        if (i>>j) & 1:
            sum += x[j]
            num += 1
    #print(sum, num, sum/num)
    if sum/num == a:
        ans += 1

print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = [0] + list(map(int, input().split()))
nx = 2501

# DP: x1からxjまでの間でk枚を選んで合計がsになる組み合わせの数
dp = [ [ [0 for s in range(nx+1)] for k in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1

for j in range(1, n+1):
    for k in range(n+1):
        for s in range(nx+1):
            if x[j] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif k >= 1:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j]]
#print(dp)
ans = 0
for k in range(1, n+1):
    ans += dp[-1][k][a * k]

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

import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline.rstrip()
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = sorted(inpl())
B = sorted(inpl())
C = sorted(inpl())

ans = 0
for a in A:
    for b in B[bisect.bisect_right(B,a):]:
        ans += len(C[bisect.bisect_right(C,b):])
print(ans)

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = sorted(inpl())
B = sorted(inpl())
C = sorted(inpl())

ans = 0
for b in B:
    tmp = bisect.bisect_right(C,b)
    tmp2 = bisect.bisect_left(A,b)
    ans += (n-tmp) * tmp2

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

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

for i in range(n):
    t = a.pop(i)
    print(max(a))
    a.insert(i, t)
    



### FIXED CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

max_value = max(a)
max_value_index = a.index(max(a))

a.pop(max_value_index)
second_max_value = max(a)
a.insert(max_value_index,max_value)

#print("======")
#print(max_value)
#print(max_value_index)
#print(second_max_value)
#print("======")

for i in a:
    if i != max_value:
        print(max_value)
    else:
        print(second_max_value)
### BUGGY CODE ###

from math import ceil
from collections import deque


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)

q = deque()
q.append((sy, sx, 0))
while len(q) > 0:
    y, x, k = q.popleft()
    b[y][x] = True
    sl = shortest_len(y, x)
    need_len = min(need_len, sl)
    if sl - (K - k) >= need_len: continue
    if k == K: continue
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y + dy, x + dx
        if not(0 <= ny < H and 0 <= nx < W): continue
        if a[ny][nx] == '#': continue
        if b[ny][nx]: continue
        q.append((y + dy, x + dx, k + 1))

print(1 + ceil(need_len / K))


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()