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

S = list(input())
rest = [0] * (len(S) + 1)
rest[0] = 0
rd = 1
for i in range(len(S)):
    rest[i+1] = (rest[i] + int(S[-(i+1)]) * rd) % 2019
    rd *= 10
    # print(i, rest[i+1], rest[i], int(S[-(i+2)]), int(S[-(i+2)]) * 10 ** (i+1))
# print(rest)
cnt = [0] * (2019 + 1)
for i in rest: cnt[i] += 1
ans = 0
for i in range(2020):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

### FIXED CODE ###

S = list(input())
rest = [0] * (len(S) + 1)
rest[0] = 0
rd = 1
for i in range(len(S)):
    rest[i+1] = (rest[i] + int(S[-(i+1)]) * rd) % 2019
    rd *= 10
    rd %= 2019
    # print(i, rest[i+1], rest[i], int(S[-(i+2)]), int(S[-(i+2)]) * 10 ** (i+1))
# print(rest)
cnt = [0] * (2019 + 1)
for i in rest: cnt[i] += 1
ans = 0
for i in range(2020):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mods = {0: 0}
ans = 0
for a in aa:
    new_mods = {}
    for mod, cnt in mods.items():
        new_mods[(mod + a) % m] = cnt
    new_mods.setdefault(a, 0)
    new_mods[a] += 1
    mods = new_mods
    ans += mods.get(0, 0)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = {}
ans = 0
zi = 0
for a in aa:
    zi = (zi - a) % m
    ai = (zi + a) % m
    mod.setdefault(ai,0)
    mod[ai] += 1
    ans += mod.get(zi,0)
print(ans)
### BUGGY CODE ###

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

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

route = [10 ** 9] * N
route[0] = 0

for i in range(N):
    if i >= 1:
        k = 1
        while i - k >= 0 and k <= K:
            count = abs(blocks[i] - blocks[i-k]) + route[i-k]
            route[i] = min(count, route[i])
            k += 1

print(route[N-1])

### FIXED CODE ###

# inputを高速化する。
import sys
import numpy as np

input = sys.stdin.readline

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

route = np.zeros(N, dtype=int)

blocks = np.array(blocks)

for i in range(1, N):
    count = max(0, i-K)
    route[i] = min(route[count:i] + np.abs(blocks[count:i] - blocks[i]))

print(route[-1])
### BUGGY CODE ###

import re
n = int(input())
s = input()

ans=0
for i in range(1000):
    reg = '{}.*{}.*{}'.format(i//100, i%100//10, i%10)
    if re.search(reg, s):
        ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict
import bisect
from itertools import product

n = int(input())
s = input()

# {文字:その文字の出現位置}の辞書を構築
d = defaultdict(list)
for i in range(n):
    d[s[i]].append(i)

def canCreate(x,y,z):
    pos = 0
    for c in map(str, [x,y,z]):
        pos = bisect.bisect_left(d[c], pos)
        if pos == len(d[c]):
            return False
        pos = d[c][pos] + 1
    return True

ans = sum([canCreate(x, y, z) for x,y,z in product(range(10), repeat=3)])

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

# -*- coding: utf-8 -*-

import sys

outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    factorList = [[0], [1]]
    # LCM
    LCM = 1
    for i in xrange(2, max(a, b)):
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def isprime(n):
    for i in xrange(2, int(n ** 0.5)+1 ):
        if n % i == 0: return False
    return True


outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    # LCM
    LCM = 1
    i = 1
    while( i <= min(a, b) ):
        i += 1
        if not isprime(i): continue
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD
### BUGGY CODE ###

n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

L=[list(map(int,input().split())) for i in range(q)]
ctL=[0]*n
for i in range(q):
  ctL[L[i][0]-1]+=L[i][1]

def bfs(v):
  distance=[-1]*n
  distance[v]=ctL[v]
  next=connection[v]
  for i in range(len(next)):
    next[i]=(next[i],v)
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i][0]]==-1:
        distance[next[i][0]]=distance[next[i][1]]+ctL[next[i][0]]
        visited[next[i][0]]=1
        visitct+=1
        for j in range(len(connection[next[i][0]])):
          if visited[connection[next[i][0]][j]]==-1:
            next2.add((connection[next[i][0]][j],next[i][0]))
    next=list(next2)
    next2=set()
  return distance

x=bfs(0)
for i in range(n):
  x[i]=str(x[i])
print(' '.join(x))

### FIXED CODE ###

import copy
n,q=map(int,input().split())
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        XST.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [INF] * len(D)
    for s, t, x in XST:
        s0 = bisect_left(D, s - x)
        t0 = bisect_left(D, t - x)
        for i in range(s0, t0):
            ans[i] = min(ans[i], x)
    for y in ans:
        print(-1 if y == INF else y)
    return

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###


n = int(input())
s = []
for _ in range(n):
    s.append(input())

t = list(set(s))
dd = len(t)
cnt = [0 for _ in range(dd)]
for i in range(dd):
    for y in s:
        if t[i] == y: cnt[i]+=1
ans = []
for i in range(dd):
    if cnt[i] == max(cnt):
        ans.append(t[i])
ans.sort()
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n = int(input())
cnt = {}
for _ in range(n):
    s = input()
    if not s in cnt:
        cnt[s] = 1
    else:
        cnt[s] = cnt[s] + 1

maxv = max(cnt.values())
ans = []
for x, c in cnt.items():
    if c == maxv: ans.append(x)
ans.sort()
for x in ans:
    print(x)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
dp=np.zeros((N+1,3))

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = list(str(input()))
    s.reverse()
    for i in range(len(s)):
        s[i] = int(s[i])
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

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

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = [0] + list(map(int,readline().split()))

c = 1
while K:
  if K&1:
    c = A[c]
  na = [0] * (N+1)
  for i in range(N+1):
    na[i] = A[A[i]]
  na,A = A,na
  K >>= 1
print(c)

### FIXED CODE ###

# A_1からスタートして、同じA_iに戻ってくるまでの[移動回数][到着場所]をリスト化

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))

route = [0]
visited = {0}
while True:
  nex = A[route[-1]] - 1
#  print(route[-1]," -> ",nex)
  if nex in visited:
#    print(nex,"is already visited")
    loopstart = route.index(nex)
#    print("loopstart =",loopstart)
    break
  else:
    visited.add(nex)
    route += [nex]
    
#print("route",route)

before_loop,one_loop = route[:loopstart],route[loopstart:]
#print("before_loop",before_loop)
#print("one_loop",one_loop)

if K <= len(before_loop) - 1:
  print(before_loop[K] + 1)
else:
  K -= len(before_loop)
  K %= len(one_loop)
  print(one_loop[K] + 1)
### BUGGY CODE ###

n = int(input())
xy = [[]] * n
cnt = 0

for i in range(n):
    xy[i] = [list(map(int, input().split())) for j in range(int(input()))]

bit = '0' + str(n) + 'b'
for k in range(2**n):
  cnt_current = 0
  flg = True
  katei = format(k, bit)
  
  for l in range(len(xy)):
    if katei[l] == '0':
      continue
    else:
      for m in range(len(xy[l])):
        if int(xy[l][m][1]) != int(katei[xy[l][m][0]-1]):
          flg = False
  if flg == True:
    cnt_current = katei.count('1')
  if cnt_current > cnt:
    cnt = cnt_current
    
print(cnt)

### FIXED CODE ###

n = int(input())
xy = [[]] * n
cnt = 0

for i in range(n):
    xy[i] = [list(map(int, input().split())) for j in range(int(input()))]

bit = '0' + str(n) + 'b'
for k in range(2**n):
  cnt_current = 0
  flg = True
  katei = format(k, bit)
  
  for l in range(len(xy)):
    if flg == False:
      break
    if katei[l] == '0':
      continue
    else:
      for m in range(len(xy[l])):
        if int(xy[l][m][1]) != int(katei[xy[l][m][0]-1]):
          flg = False
          break
  if flg == True:
    cnt_current = katei.count('1')
  if cnt_current > cnt:
    cnt = cnt_current
    
print(cnt)
### BUGGY CODE ###

import math
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=True)
B.sort(reverse=True)
C.sort(reverse=True)
l=[]
stat=int(math.sqrt(10**7//X))
for i in range(X):
    for j in range(min(stat,Y)):
        for k in range(min(stat,Z)):
            l.append(A[i] + B[j] + C[k])
end1=stat
stat2=int(math.sqrt(10**7//Y))
for i in range(min(stat,X),min(stat+stat2,X)):
    for j in range(Y):
        for k in range(min(stat,Z),min(stat+stat2,Z)):
            l.append(A[i] + B[j] + C[k])
end2=stat+stat2
stat3=int(math.sqrt(10**7//Z))
for i in range(min(stat+stat2,X),min(stat+stat2+stat3,X)):
    for j in range(min(stat+stat2,Y),min(stat+stat2+stat3,Y)):
        for k in range(Z):
            l.append(A[i] + B[j] + C[k])

l.sort(reverse=True)
#print(l)
for i in range(K):
    print(l[i])



### FIXED CODE ###

import math
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=True)
B.sort(reverse=True)
C.sort(reverse=True)
l=[]
#まずX+Yを求め、上から順にソート
#10^6相当の計算
for i in range(X):
    for j in range(Y):
        l.append(A[i] + B[j])
l.sort(reverse=True)
ans=[]
#(X+Y)+Zより、全体の上位を求めるが、Zが何であれ、X+Yの和が上からK番目以下のものは考慮しなくて良い
#(X+YにおいてK+i番目のもの(X+Y)_K+i+Zjが全体でK番以内に食い込めるということは、1~K番目のX+Yにて(X+Y)_1~K+Zj>(X+Y)_K+i+Zjが成立することと矛盾する)
#これで高々10^7相当までのソートでよくなる
for i in range(min(K,len(l))):
    for j in range(Z):
        ans.append(l[i]+C[j])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import itertools
import re
#from itertools import permutations, combinations,combinations_with_replacement,product

t = input()
#print(len(t))
t_re = t.replace('?', '.')
pattern = re.compile(t_re)
#print(t_re)
count_prev = 0
ans = ''
for v in itertools.product('PD', repeat=len(t)):
  count = 0
  s = ''.join(v)
  if re.match(pattern, s):
    count += s.count('D')
    count += s.count('PD')
    if count_prev < count:
      count_prev = count
      ans = s

print(ans)

### FIXED CODE ###

import itertools
import re
#from itertools import permutations, combinations,combinations_with_replacement,product

t = input()
#print(len(t))
print(t.replace('?', 'D'))
### BUGGY CODE ###

import math
import itertools
from functools import reduce

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

k = int(input())

ans = 0 
comb_list  = itertools.product(range(1,k + 1), repeat=3)

for a,b,c in comb_list:
    s = gcd(a,b,c)
    ans += s
print(ans)

### FIXED CODE ###

import math
 
k = int(input()) + 1
ans = 0
 
for a in range(1, k):
    for b in range(1, k):
        d = math.gcd(a, b)
        for c in range(1, k):
            ans += math.gcd(d, c)
 
print(ans)
### BUGGY CODE ###

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

def check(tisiki):
    cnt = 0
    for t in tisiki:
        if t<X:
            return False
    return True

ans = 10**9
for v in permutations(list(range(N))):
    tisiki = [0] * M
    cost = 0
    for i in v:
        b = book[i]
        cost += b[0]
        for t in range(M):
            tisiki[t] += b[t+1]
        
        if check(tisiki):
            ans = min(ans, cost)

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

### FIXED CODE ###

import numpy as np

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for i in range(1<<N):
    cost = 0
    tisiki = np.array([0]*M)
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    
    for k in range(N):
        if cond[k]==1:
            b = book[k]
            cost += b[0]
            tisiki += np.array(b[1:])
    
    if np.all(tisiki>=X):
        ans = min(ans, cost)

if ans < 10**9:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

X = int(input())

def notco(x, lst):
  for i in range(len(lst)):
    if x % lst[i] == 0:
      return False
  return True

def minp(x):
  primes = [2]
  i = 3
  while(primes[len(primes)-1] < x):
    if notco(i, primes):
      primes.append(i)
    i += 1
  return primes[len(primes)-1]

print(minp(X))

### FIXED CODE ###

X = int(input())

def isprime(x):
  for i in range(2, x//2+1):
    if x % i == 0:
      return False
  return True

def minp(x):
  res = x
  while True:
    if isprime(res):
      return res
    res += 1

print(minp(X))
### BUGGY CODE ###

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

G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append(v-1)

S, T = map(int, input().split())


par = [i for i in range(3*N)]
rank = [0 for i in range(3*N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

ans = 0
start = [S-1]
frag = 1
g = -1
while frag:
    frag = 0
    ans += 1
    g += 1
    g %= 3
    l = len(start)
    for i in range(l):
        s = start.pop(0)
        for j in range(len(G[s])):
            start.append(G[s][j])
            if g == 2:
                if same(s + 2 * N, G[s][j]):
                    continue
                else:
                    frag = 1
                    unite(s + 2 * N, G[s][j])

            else:
                if same(s + g * N, G[s][j] + (g+1) * N):
                    continue
                else:
                    frag = 1
                unite(s+ g * N, G[s][j] + (g+1) * N)

        if same(S-1, T-1) and par[S-1] != -1:
            print(ans//3)
            sys.exit()
print(-1)

### FIXED CODE ###

import sys
import heapq
N, M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append([v-1 + N, 1])
    G[u-1 + N].append([v-1 + 2*N, 1])
    G[u-1 + 2*N].append([v-1, 1])

S, T = map(int, input().split())

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

if d[T-1] == INF:
    print(-1)
else:
    print(d[T-1]//3)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
X, Y, A, B, C = (int(i) for i in input().split())
p = [[int(x), "A"] for x in input().split()]
q = [[int(x), "B"] for x in input().split()]
r = [[int(x), "C"] for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
apples = p+q+r


apples.sort(reverse=True)
#print(apples)
ans = 0
pend = 0


for i in range(len(apples)):
    if apples[0][1] == "C":
        pend += 1
        ans += apples[0][0]
        apples.pop(0)
    elif apples[0][1] == "A":
        if X > 0:
            ans += apples[0][0]
            apples.pop(0)
            X -= 1
        else:
            apples.pop(0)
    elif apples[0][1] == "B":
        if Y>0:
            ans += apples[0][0]
            apples.pop(0)
            Y -= 1
        else:
            apples.pop(0)
    if (X < 1 and Y < 1) or X+Y == pend:
        break
    #print(ans)
    #print("XY", X, Y, pend)
#print("XY", X, Y, pend)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
X, Y, A, B, C = (int(i) for i in input().split())
p = [[int(x), "A"] for x in input().split()]
q = [[int(x), "B"] for x in input().split()]
r = [[int(x), "C"] for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
apples = p+q+r


apples.sort(reverse=True)
#print(apples)
ans = 0
pend = 0


for hapi, col in apples:
    if col == "C":
        pend += 1
        ans += hapi
    elif col == "A":
        if X > 0:
            ans += hapi
            X -= 1

    elif col == "B":
        if Y>0:
            ans += hapi
            Y -= 1

    if (X < 1 and Y < 1) or X+Y == pend:
        break
    #print(ans)
    #print("XY", X, Y, pend)
#print("XY", X, Y, pend)
print(ans)
### BUGGY CODE ###

def bisect(lst, isok, ok, ng):
    while(abs(ok-ng)>1):
        mid = (ok+ng)//2
        if isok(lst[mid]):
            ok = mid
        else:
            ng = mid
    return [ok, ng]

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()

ans = 0

for i in a:
    ind = bisect(b, lambda x:x > i, n, -1)[0]
    if ind == n:
        break
    for j in range(ind, n):
        ans += n - bisect(c, lambda x:x > b[j], n, -1)[0]

print(ans)

### FIXED CODE ###

def bisect(lst, isok, ok, ng):
    while(abs(ok-ng)>1):
        mid = (ok+ng)//2
        if isok(lst[mid]):
            ok = mid
        else:
            ng = mid
    return [ok, ng]

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort()
b.sort()
c.sort()

ans = 0

for i in b:
    x = bisect(a, lambda x:x < i, -1, n)[0]
    y = bisect(c, lambda x:x > i, n, -1)[0]
    ans += (x+1)*(n-y)

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

def main():
	n=int(input())
	a=list(map(int, input().split()))
	count = 0
	while count==0:
		for i in range(n):
			if  a.count(a[i])> 1:
				count+=1
				break
			else:
				continue
	if count==0:
		print('YES')
	else:
		print('NO')
main()

### FIXED CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	a.sort()
	c=0
	for i in range(n-1):
		if a[i] == a[i+1]:
			print('NO')
			c+=1
			break
	if c==0:
		print('YES')
main()
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted([int(input()) for _ in range(M)])
mod = 10**9+7
dp=[0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])