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

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

n,q = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

ans = [0 for _ in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    ans[p-1] += x

def dfs(pre,now,point):
    for to in G[now]:
        if to==pre:continue
        ans[to]+=point
        dfs(now,to,ans[to])
dfs(-1,0,ans[0])
print(*ans)

### FIXED CODE ###

n,q = map(int,input().split())
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    tree[a].append(b)

ans = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

#入力

stack = [0]
while len(stack) > 0:
    now = stack.pop()
    for i in tree[now]:
        ans[i] += ans[now]
        stack.append(i)

for i in range(n):
    print(ans[i],end=" ")
print()
### BUGGY CODE ###

a,b,x = map(int, input().split())
cnt=0
for i in range(a,b+1):
  if i%x ==0:
    cnt +=1
print(cnt)

### FIXED CODE ###

a,b,x = map(int, input().split())
if a %x==0:
  print(b//x - a//x+1)
else:
  print(b//x - a//x)
### BUGGY CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = list()
for i in range(0,n-1):
    if s[i] == "A" and s[i+1] == "C":
        check.append(i+1)
for i in range(0,q):
    num.append(list(map(int,input().split())))
    count = 0
    for k in check:
        if num[i][1] <=k:
            break
        if num[i][0] <= k:
            count +=1
    print(count)

### FIXED CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = [0]*n
for i in range(1,n):
        if s[i-1] == "A" and s[i] == "C":
                check[i] = check[i-1]+1
        else:
                check[i] = check[i-1]
ans = 0
for i in range(0,q):
        num = list(map(int,input().split()))
        ans = check[num[1]-1]-check[num[0]-1]
        print(ans)
### BUGGY CODE ###

N = int(input())

A = [int(i) for i in input().split()]

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

### FIXED CODE ###

import collections

N = int(input())

A = [int(i) for i in input().split()]

c = collections.Counter(A)

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

from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
if tmp != 1:
    print('not coprime')
    exit()

for i in A:
    f(i)

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

### FIXED CODE ###

from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x : int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9+7
fact = [1] * N
fact_inv = [1] * N
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [1] * N
count = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * N
def reroot(par, val_par, cnt_par, v):
    ans[v] = val_par * value[v] * comb(N-1, cnt_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(value[u] * comb(N-1, count[u])) % mod
        reroot(v, val, N-count[u],  u)

dfs(-1, 0)
reroot(-1, 1, 0, 0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x : int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9+7
fact = [1] * N
fact_inv = [1] * N
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [1] * N
count = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * N
def reroot(par, val_par, cnt_par, v):
    ans[v] = val_par * value[v] * comb(N-1, cnt_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(value[u] * comb(N-1, count[u])) % mod
        reroot(v, val, N-count[u],  u)

dfs(-1, 0)
reroot(-1, 1, 0, 0)
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j+1,N):
                if j-i != k-j and S[j] != S[k] and S[i] != S[k]:
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R*G*B
for i in range(N):
    for k in range(i+1,N):
        if (k+i)%2 == 1:
            continue
        else:
            j = (k+i)//2
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n=int(input())
l=[0]*n
l[:]=map(int,input().split())
ans=0
m=10**3
l=sorted(l)[::-1]
for i in range(n-2):
  m=min(m,l[i])
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if m<l[j]+l[k]:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)
### BUGGY CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N))
    for i in range(1, M + 2):
        var = i ** N
        if P % var == 0:
            _max = i

    print(_max)

### FIXED CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1.0 * 1e-9)
    for i in range(1, M + 1):
        if P % (i ** N) == 0:
            _max = i

    print(_max)
### BUGGY CODE ###

s=input()
k=int(input())
l=[i for i in s]
ans=[i for i in s]
mae=[]
for i in range(len(s)-1):
  for j in range(len(l)-1):
    nlen=len(l[j])
    lj=l[j+1]
    now=l[j]+lj[nlen-1:]
    mae.append(now)
  ans.extend(mae)
  l=mae
  mae=[]

ans=list(set(ans))
ans.sort()
print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
ans=[]

for i in range(len(s)):
  for j in range(i+1,min(k+i+1,len(s)+1)):
    ans.append(s[i:j])

ans=list(set(ans))
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
L = sorted(L,reverse=True)
total = 0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if L[j] + L[k] > L[i]:
                total += 1
            else:
                break
print(total)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        limit = L[i]+L[j]
        ans += bisect.bisect_left(L,limit) - (j+1)

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

# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)

def bfs(root):
    global AL, cnt, visited
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            bfs(v)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

visited = [False] * (N + 1)
bfs(1)
s = " ".join(map(str, cnt[1:]))
print(s)

### FIXED CODE ###

# 20/5/28
from collections import deque

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

visited = [False] * (N + 1)
stk = deque([1])
while stk:
    root = stk.pop()
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            stk.append(v)

s = " ".join(map(str, cnt[1:]))
print(s)
### BUGGY CODE ###

"""
D - String Formation
"""
s = input()
q = int(input())
string = []
is_normal = 1
for i in range(q):
    emir = input()
    if emir[0] == '1':
        is_normal *= -1
    elif emir[0] == '2':
        if is_normal == 1:
            if emir[2] == '1':
                s = emir[4] + s
            elif emir[2] == '2':
                s += emir[4]
        else:
            if emir[2] == '1':
                s += emir[4]
            elif emir[2] == '2':
                s = emir[4] + s
if is_normal == -1:
    s = s[::-1]

print(s)


### FIXED CODE ###

s = input()
q = int(input())
string = []
is_normal = 1
saq = ""
sol = ""
for i in range(q):
    emir = input()
    if emir[0] == '1':
        is_normal *= -1
    elif emir[0] == '2':
        if is_normal == 1:
            if emir[2] == '1':
                sol += emir[4]
            elif emir[2] == '2':
                saq += emir[4]
        else:
            if emir[2] == '1':
                saq += emir[4]
            elif emir[2] == '2':
                sol += emir[4]
s = sol[::-1] + s + saq
if is_normal == -1:
    s = s[::-1]

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

s = input()
j = []
k = []
for i in range(len(s)+1):
    left = s[0:i]
    right = s[i:]
    l = 0
    r = 0
    for i in range(len(left)-1,-1,-1):
        if left[i] != "<":
            break
        else:
            l += 1
    for i in range(len(right)):
        if right[i] != ">":
            break
        else:
            r += 1
    j.append(max(l,r))
print(sum(j))

### FIXED CODE ###

from itertools import *
s = input()
g = [[k,len(list(v))] for k,v in groupby(s)]
ans = 0
for command,length in g:
    ans += length*(length+1)//2
for i in range(len(g)-1):
    if g[i][0] == "<":
        ans -= min(g[i][1],g[i+1][1])
print(ans)
### BUGGY CODE ###

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

for i in range(k+1):
    tmp = 0
    for j in range(n):
        tmp += i ^ A[j]
    ans = max(tmp,ans)
print(ans)

### FIXED CODE ###

# 解説の手順
# 参考:kenseiQ さん
def XXOR(N,K,A):
    # 2**10=1024>1000=10**3を利用すると、K+1<10**12+1<2*40(計算されたし)がわかる
    # つまりKを二進表記しても高々40桁（0~39で扱う）しかない
    ans = 0

    # Aの各要素を二進表記した時、b番目のビットが立っているものは何個か
    bit_stand = [len([1 for a in A if (a & 1<<b) != 0]) for b in range(40)]

    # KとXを二進表記したものを上の桁から見て行って、初めて違う数字が出てきた桁がi
    for i in range(39,-2,-1):

        # K_iは1でないといけないのでその時はcontinue（解説参照）
        if i != -1 and (K & (1<<i)) == 0: # i=-1の時はX=Kの時を扱う（この時は前半部分で条件が弾かれるので1<<(-1)が実行されてエラーになることがない）
            continue

        tmp = 0
        for e in range(39,-1,-1): # 各ビットがf(x)に貢献する値を見ていく
            bit_mask = 1<<e
            num = bit_stand[e]

            if e>i: # この桁はKと同じ
                if (bit_mask & K) == 0: # Xのi桁のビットが立っていない時
                    tmp += bit_mask * num
                else:                   # Xのi桁のビットが立ってる時
                    tmp += bit_mask * (N-num) 
            elif e==i: # Xのi桁は必ず0である（解説参照）
                tmp += bit_mask * num
            else: # ここの桁は自由に決めていい
                tmp += bit_mask * max(num,N-num)
        
        ans = max(ans, tmp)
    
    return ans


N,K = map(int,input().split())
A = list(map(int,input().split()))
print(XXOR(N,K,A))
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

    
def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    c1i=list(range(N))
    def unneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,unneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)


def main2():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    cards.sort()
    mask=lambda c: (1<<(K))-(1<<c)
    def isunnec(i):
        c=cards[i]
        if c>=K:
            return False
        cards[i]=0
        ret=0
        for x in cards:
            if x!=0:
                ret=(((ret+1)<<x)|ret )&mask(0)
        cards[i]=c
        # print(i,bin(ret&mask(K-c)))
        if ret&mask(K-c)>0:
            return False
        else:
            return True
    nn=biser(list(range(N)),isunnec)
    print(nn+1)
    # for x in range(N):
    #     isunnec(x)
if __name__=='__main__':
    #main()
    main2()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [10**10] * (Q+1)
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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

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

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
print(ans)

### FIXED CODE ###

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

for x in range(k+1):
    for y in range(k+1):
        z = s - y - x
        if 0 <= z and z<= k:
            ans += 1
print(ans)
### BUGGY CODE ###

def f(n):
    fn =1
    if n < 2:
        return 1
    else:
        while n >= 2:
            fn *= n
            n -= 2
        return fn
        


n = int(input())
fn = str(f(n))
if int(fn) % 2 == 1:
    print(0)
    exit()
n = 0
for i in range(len(fn)):
    if fn[-i-1] == '0':
        n += 1
    else:
        break
print(n)


### FIXED CODE ###

N = int(input())

if N % 2 != 0:
    print(0)
    exit()
ans = 0
d = 10
while d <= N:
    ans += N // d
    d *= 5
print(ans)
### BUGGY CODE ###

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        if dist[i][j] < d:
            continue
        for di, dj in ((-1, 0),  (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((d + 1, nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

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

### FIXED CODE ###

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        #if dist[i][j] < d:
        #    continue
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

count = 0


for c in C:
    for b in B:
        if b >= c:
            continue
        else:
            saidan = filter(lambda x: x<b ,A)
            count+=len(list(saidan))
                
print(count)

### FIXED CODE ###

import bisect
 
def main():
    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 y in b:
        i = bisect.bisect_left(a, y)
        j = bisect.bisect_right(c, y)
        if i > 0 and j != len(c):
            ans += i * (n - j)
 
    print(ans)
 
main()
### BUGGY CODE ###

import numpy as np

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

grids = []
for _ in range(H):
    grids.append(input())

hr_scores = np.array([[-1] * W for _ in range(H)])
vr_scores = np.array([[-1] * W for _ in range(H)])

for h in range(H):
    cnt = 0
    start_w = 0
    for w in range(W):
        if grids[h][w] == '.':
            cnt += 1
        else:
            hr_scores[h, w] = 0
            hr_scores[h, start_w: w] = cnt
            start_w = w + 1
            cnt = 0
    if cnt:
        hr_scores[h, start_w: w + 1] = cnt

for w in range(W):
    cnt = 0
    start_h = 0
    for h in range(H):
        if grids[h][w] == '.':
            cnt += 1
        else:
            vr_scores[h, w] = 0
            vr_scores[start_h: h , w] = cnt
            start_h = h + 1
            cnt = 0
    if cnt:
        vr_scores[start_h: h + 1, w] = cnt

print(max((hr_scores + vr_scores).max() - 1, 0))

### FIXED CODE ###

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

grids = []
for _ in range(H):
    grids.append(input())

hr_scores = []
vr_scores = []


max_value = 0
for w in range(W):
    cnt = 0
    start_h = 0
    lis = []
    for h in range(H):    
        if grids[h][w] == '.':
            cnt += 1
        else:
            lis += [cnt] * (h - start_h) + [0]
            start_h = h + 1
            cnt = 0
    if cnt:
        lis += [cnt] * (h - start_h + 1)
    vr_scores.append(lis)
vr_scores = [[vr_scores[w][h] for w in range(W)] for h in range(H)]
for h in range(H):
    cnt = 0
    start_w = 0
    lis = []
    for w in range(W):
        if grids[h][w] == '.':
            cnt += 1
        else:
            lis += [cnt] * (w - start_w) + [0]
            if cnt:
                max_value = max(
                    max_value,
                    max(vr_scores[h][start_w: w]) + cnt
                )
            start_w = w + 1
            cnt = 0
    if cnt:
        max_value = max(
            max_value,
            max(vr_scores[h][start_w: w + 1]) + cnt
         )

print(max(max_value - 1, 0))
### BUGGY CODE ###

n = int(input())
seq = [int(e) for e in input().split(' ')]

count = 0
for i in seq:
  number_loop = len(seq[0:seq.index(i)+1])
  for idx, j in enumerate(seq[0:seq.index(i)+1]):
    if i > j:
      break
    if idx+1 == number_loop:
      count += 1
      
print(count)
      

### FIXED CODE ###

n = int(input())
seq = [int(e) for e in input().split(' ')]

count = 1

current_min = seq[0]

for idx, i in enumerate(seq[1:]):
  if i < current_min:
    current_min = i
    count += 1
print(count)
### BUGGY CODE ###

k = int(input())
cnt = 1
ans = 7
ans %= k
flags = [False] * k
flags[ans] = True
while ans != 0:
    ans += 7*pow(10,cnt,k)
    cnt += 1
    ans %= k
    if flags[ans]:
        cnt = -1
        break
    flags[ans] = True

print(cnt)


### FIXED CODE ###

k = int(input())
cnt = 1
ans = 7
mul = 70 % k
ans %= k
flags = [False] * k
flags[ans] = True
while ans != 0:
    ans += mul
    cnt += 1
    ans %= k
    mul *= 10
    mul %= k
    if flags[ans]:
        cnt = -1
        break
    flags[ans] = True

print(cnt)