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

class WarshallFloyd:
    def __init__(self,n):
        self.dist = {}
        for i in range(n-1):
            for j in range(i,n):
                self.dist[(i,j)] = 1e100

    def unite(self,x,y,c):
        if x == y:
            return False
        elif x > y:
            x,y = y,x
        if self.dist[(x,y)] <= c:
            return False
        else:
            for i in range(n-1):
                for j in range(i+1,n):
                    self.dist[(i,j)] = min(self.d(i,j), self.d(i,x) + c + self.d(y,j), self.d(i,y) + c + self.d(x,j))

    def d(self,x,y):
        if x == y:
            return 0
        if x > y:
            x,y = y,x
        return self.dist[(x,y)]

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.unite(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
for a,b,c in ABC:
    ans += (c > wf.d(a,b))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
wf.build()
for a,b,c in ABC:
    ans += (c > wf.d[a][b])
print(ans)
### BUGGY CODE ###

import heapq as hq
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
event = []
for s,t,x in STX:
    event += [[s - x, t-x, x]]
event.sort(key=lambda x:x[0])
h = []
tdic = {}
ind = 0
for Di in Dlist:
    while ind<N and event[ind][0] <= Di:
        #Diまでに始まった工事を追加
        hq.heappush(h, event[ind][2])
        tdic[event[ind][2]] = event[ind][1]
        ind += 1
    while h and Di >= tdic[h[0]]:
        #Diまでに終わった工事を削除
        hq.heappop(h)
    if h:
        print(h[0])
    else:
        print(-1)

### FIXED CODE ###

import heapq as hq
from collections import defaultdict
N, Q = map(int, input().split())
event = []
for i in range(N):
    si, ti, xi = map(int, input().split())
    event.append([si - xi, ti - xi, xi])
#STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
#for s,t,x in STX:
#    event.append([s - x, t-x, x])
event.sort(key=lambda x:x[0])
h = []
tdic = defaultdict(int)
ind = 0
for Di in Dlist:
    while ind<N and event[ind][0] <= Di:
        #Diまでに始まった工事を追加
        hq.heappush(h, event[ind][2])
        tdic[event[ind][2]] = event[ind][1]
        ind += 1
    while h and Di >= tdic[h[0]]:
        #Diまでに終わった工事を削除
        hq.heappop(h)
    if h:
        print(h[0])
    else:
        print(-1)
### BUGGY CODE ###

from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None
        self.ancestor = self


def ancestor(elems, x):
    s = elems[x].ancestor
    while s.parent is not None:
        s = s.parent
    s.ancestor = s
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()



### FIXED CODE ###

class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))


def main():
    n, q = [int(x) for x in input().split()]
    ds = DisjointSet(n)

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            ds.unite(x, y)
        else:
            print(1 if ds.same(x, y) else 0)


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

import sys
from collections import deque
input = sys.stdin.readline

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            black.append((i, j, 0))

# print(m)
# print(root)

queue = deque(black)
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue.append((next_p[0], next_p[1], ans+1))
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    if b == se[0]:
      heappop(se)
      while remove_task and (se[0] == remove_task[0]):
        heappop(se)
        heappop(remove_task)
    else:
      heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  else:
    if se:
      answer[b] = se[0]
  #print(a,c,b,se,remove_task)
print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]

for i in range(n):
    a = l[0]
    del l[0]
    print(max(l))
    l.append(a)

### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
ll = sorted(l, reverse = True)
m1 = ll[0]
m2 = ll[1]

for i in range(n):
    if l[i] == m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

import bisect

n = int(input())
length = list(map(lambda x:int(x), input().split()))
length.sort()
ans = 0
for i in range(n):
    a = length[i]
    for j in range(n):
        b = length[j]
        if i >= j:
            continue
        else:
            c_candidates = length[j+1:]
            min_bar = bisect.bisect_right(c_candidates,max(a-b, b-a))
            max_bar = bisect.bisect_left(c_candidates,a+b)
            ans += max_bar - min_bar
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
#length = list(map(lambda x:int(x), input().split()))
length = list(map(int, input().split()))
length.sort()
ans = 0
for i in range(n-2):  
    a = length[i]
    for j in range(i+1,n-1):
        b = length[j]
        if i >= j:
            continue
        else:
            max_bar = bisect.bisect_left(length,a+b)
            ans += max_bar - j - 1
            
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
from math import floor


def p_d():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    for _ in range(M):
        x = A.pop() / 2

        i = bisect_left(A, x)

        A.insert(i, x)

    ans = 0

    for a in A:
        ans += floor(a)

    print(ans)


if __name__ == '__main__':
    p_d()


### FIXED CODE ###

from heapq import heappop, heappush
from math import ceil, floor


def p_d():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    H = []

    for a in A:
        heappush(H, a * -1)

    for _ in range(M):
        x = heappop(H)

        heappush(H, ceil(x / 2))

    ans = 0

    for a in H:
        ans -= a

    print(ans)


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

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

sum = 1
for i in A:
    sum *= i

ans = -1

if sum <= 10**18:
    ans = sum

print(ans)


### FIXED CODE ###

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

A.sort()

sum = 1
for i in A:
    sum *= i
    if sum > 10**18:
        sum = -1
        break

ans = sum

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

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

for i in range(a, b):
  xor = xor ^ (i + 1)
  
print(xor)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 0

def xor(x):
  if x % 4 == 0:
    return x
  elif x % 4 == 1:
    return 1
  elif x % 4 == 2:
    return x + 1
  else:
    return 0

xor_of_a = xor(a - 1)
xor_of_b = xor(b)

ans = xor_of_a ^ xor_of_b

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

#!/usr/bin/env python3
import sys


def solve(S: int):
    S =str(S)
    l = len(S)
    elds = [x*2019 for x in range(10000) if "0" not in str(x*2019)]
    # print(elds)
    s = S
    ans = []
    for t in range(5,9):
        for x in range(l-t+1):
            # print(s[x:x+t])           
            if int(s[x:x+t]) in elds:
                ans.append((x,x+t))

    p= [a_[0] for a_ in ans]
    q= [a_[1] for a_ in ans]
    
    print(len(ans)+len(set(p)&set(q)))
    

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: int):
    S =str(S)[::-1]
    MOD = 2019
    mod_l = [int(0)]*2019
    mod_l[0] = 1
    prev = 0
    for x in range(len(S)):
        k = int(S[x]) * pow(10, x, MOD) % MOD + prev
        mod_l[k%2019] += 1
        prev = k%2019

    s = sum([x*(x-1)//2 for x in mod_l])
    print(s)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

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

s = input()
pos = 0
cnt = 0
acnt = 0
if len(s) < 3:
    print(0)
else:
    while(True):
        if s[pos:pos+3] == "ABC":
            s = s[:pos-acnt] + "BCA"+ s[pos-acnt:pos] + s[pos+3:]
            if pos > 0:
                pos -= acnt+1
            cnt += acnt+1
            acnt = 0
            # print(s, cnt)
        else:
            if s[pos] == "A":
                acnt += 1
            else:
                acnt = 0
            pos += 1
        if pos >= len(s)-2:
            break
    print(cnt)


### FIXED CODE ###

s = input()
pos = 0
cnt = 0
acnt = 0
if len(s) < 3:
    print(0)
else:
    while(True):
        if s[pos:pos+2] == "BC" and acnt > 0:
            pos += 2
            cnt += acnt
            # print(s, s[pos:pos+2], cnt, pos)
        else:
            if s[pos] == "A":
                acnt += 1
            else:
                acnt = 0
            pos += 1
        if pos >= len(s)-1:
            break
    print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache
 
    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
        self.n = len(prices)
    
    @lru_cache(None)
    def transaction(self, money, stock, i, last_buy):
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock,_money = stock,money

        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            self.transaction(money, stock, i + 1, self.prices[i])
        # backtracking
        money,stock = _money,_stock
 
        ## sell
        if stock > 0 and self.prices[i] > last_buy:
            stock, money = 0, stock * self.prices[i] + money
            if money > 1000:
                self.transaction(money, 0, i + 1,0)
        # backtracking
        money,stock = _money,_stock
 
        ## do nothing
        self.transaction(money, stock, i + 1,last_buy)
 
 
def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0, 0)
    print(solver._max)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
 

def maxProfit(prices) -> int:
    if len(prices) < 2:
        return 0
    ans = 1000
    for i in range(1,len(prices)):
        if prices[i] > prices[i - 1]:
            stock = ans // prices[i - 1]
            ans += stock * (prices[i] - prices[i - 1]) 
    return ans

def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]

    ans = maxProfit(A)
    print(ans)


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

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]*n
for i in range(n):
  a[i]=(p[i]+1)/2
ans=0
for i in range(n-k+1):
  ans=max(ans,sum(a[i:k+i]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]*n
b=[0]*n
for i in range(n):
  a[i]=(p[i]+1)/2
b[0]=a[0]
for i in range(1,n):
  b[i]=b[i-1]+a[i]
ans=b[k-1]
for i in range(1,n-k+1):
  ans=max(ans,b[i+k-1]-b[i-1])
print(ans)
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= A[i]
    
if ans > 10 ** 18:
    ans = -1   
else:
    pass

print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for i in range(n):
        if ans > 10 ** 9:
            if A[i] >= 10 ** 9:
                ans = -1
                break
            else:
                pass
        else:
            pass
        ans *= A[i]
        if ans > 10 ** 18:
            ans = -1
            break
        else:
            pass
    print(ans)
### BUGGY CODE ###

import sys
N = int(input())
L = list(map(int,input().split()))
if(0 in L):
    print(0)
    sys.exit()
    
sum_l = 1
for x in L:
    sum_l *= x

if(sum_l > 10** 18):
    print(-1)
else:
    print(sum_l)
    

### FIXED CODE ###

import sys
N = int(input())
L = list(map(int,input().split()))
if(0 in L):
    print(0)
    sys.exit()
    
sum_l = 1
for x in L:
    sum_l *= x
    if(sum_l > 10 **18):
        print(-1)
        sys.exit()

print(sum_l)
### BUGGY CODE ###

from collections import defaultdict, deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1

maze = []
for _ in range(H):
    row = list(input())
    maze.append(row)

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#":
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[num]:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)



### FIXED CODE ###

from collections import defaultdict, deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    maze = [input() for _ in range(H)]

    INF = 10**12
    path = [[INF] * W for _ in range(H)] # 各マスへの移動コスト
    
    # walk:移動A, warp:移動B
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[ch][cw] = 0
    q.append((ch, cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk: #移動A
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s)) # なぜleft?

        for dx, dy in warp: #移動B
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s+1)) # なぜright?

    ans = path[dh][dw] if path[dh][dw] != INF else "-1"
    print(ans)

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

import sys

def main():
    N, K = [int(_) for _ in input().split()]
    
    # dif = abs(N - K)
    # if N < dif:
    #     print(N)
    #     sys.exit()
    # elif K < dif:
    #     print(K)
    #     sys.exit()

    m = 0
    while True:
        m = abs(N - K)
        if m < N:
            N = m
            if N==0:
                print(N)
                break
        else:
            print(N)
            break

main()

### FIXED CODE ###

import sys

def main():
    n, k = [int(_) for _ in input().split()]
    
    m = abs(n - n // k * k)
    while True:
        ans = abs(m - k)
        if m <= ans:
            print(m)
            sys.exit()
        m = abs(m - k)
main()
### BUGGY CODE ###

S = str(input())
Q = int(input())

S_normal = S
S_inverse = S[::-1]
for q in range(Q):
    query = list(map(str, input().split()))
    if int(query[0]) == 1:
        S = S_inverse
        S_inverse = S_normal
        S_normal = S
    else:
        if int(query[1]) == 1:
            S = query[2]+S
            S_normal = S
            S_inverse += query[2]
        else:
            S += query[2]
            S_normal = S
            S_inverse = query[2]+S_inverse

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())

d = deque(list(S))

rev = False

for q in range(Q):
    query = list(map(str, input().split()))
    if int(query[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if int(query[1]) == 1:
            if not rev:
                d.appendleft(query[2])
            else:
                d.append(query[2])
        else:
            if not rev:
                d.append(query[2])
            else:
                d.appendleft(query[2])

if rev:
    print(''.join(d)[::-1])
else:
    print(''.join(d))
### BUGGY CODE ###

import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

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

ans = 0
for i in range(N):
    r1 = bisect.bisect_right(B,A[i])
    for j in range(r1,N):
        r2 = bisect.bisect_right(C,B[j])
        ans += N - r2
print(ans)


### FIXED CODE ###

import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

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

ans = 0
for i in range(N):
    l = bisect.bisect_left(A,B[i])
    r = bisect.bisect_right(C,B[i])
    ans += l*(N-r)

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

s=input()
c=0
for i in range(len(s)):
    for j in range(i,len(s)):
        if int(s[i:j+1]) %2019==0:
            c += 1

print(c)

### FIXED CODE ###

S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
A = A[::-1]

MOD = 2019

p10 = [1] * N
for i in range(1, N):
	p10[i] = (p10[i - 1] * 10) % MOD

for i in range(N):
	A[i] = (A[i] * p10[i]) % MOD

cumsum = [A[0]] * N
for i in range(1, N):
	cumsum[i] = (cumsum[i - 1] + A[i]) % MOD

cnt = [0] * MOD
cnt[0] = 1
for i in range(N):
	cnt[cumsum[i]] += 1

ans = 0
for i in range(MOD):
	ans += cnt[i] * (cnt[i] - 1) // 2

print(ans)