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

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [[start_x, start_y, 0]] \
       + [list(map(int, input().split())) for i in range(n)] \
       + [[goal_x, goal_y, 0]]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[] for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2 )**(0.5) - sum_radius) 
        graph[i].append([j, cost])
        if i != j:
            graph[j].append([i, cost])

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
q = []
q.append([0,0])
distance[0] = 0
while q:
    here, c = heapq.heappop(q)
    if distance[here] < c:
        continue
    for t, cost in graph[here]:
        if distance[here] + cost < distance[t]:
            distance[t] = distance[here] + cost
            heapq.heappush(q, [t, distance[t]])
            
print(distance[n+1])

### FIXED CODE ###

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost
        graph = tuple(graph)

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
used = [False]*(n+2)
distance[0] = 0

while True:
    v = -1
    for u in range(n+2):
        if not used[u] and (v == -1 or distance[u] < distance[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    for u in range(n+2):
        distance[u] = min(distance[u], distance[v] + graph[v][u])
            
print(distance[n+1])
### BUGGY CODE ###

from fractions import gcd
A, B = map(int, input().split())



saidai_kouyaku = gcd(A,B)
kouyaku = [0 for _ in range(saidai_kouyaku+1)]
kouyaku[1] = 1

for i in range(2,saidai_kouyaku+1):
    while saidai_kouyaku%i==0:
        kouyaku[i]+=1
        saidai_kouyaku = saidai_kouyaku/i

answer = 0
for i in range(len(kouyaku)):
    if kouyaku[i] > 0:
        answer += 1
print(answer)

### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())

saidai_kouyaku = gcd(A,B)

#%%
kouyaku = [0 for _ in range(int(saidai_kouyaku**0.5)+2)]
kouyaku[1] = 1


for i in range(2,len(kouyaku)):
    while saidai_kouyaku%i==0:
        kouyaku[i]+=1
        saidai_kouyaku = saidai_kouyaku/i

answer = 0
for i in range(len(kouyaku)):
    if kouyaku[i] > 0:
        answer += 1

if saidai_kouyaku > 1:
    print(answer+1)
else:
    print(answer)
### BUGGY CODE ###

n = int(input())
li_a = input().split()

result = 0
for i in set(li_a):
    cnt = li_a.count(i)
    if cnt > int(i):
        result += cnt - int(i)
    elif cnt < int(i):
        result += cnt

print(result)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
li_a = input().split()

ndict = defaultdict(int)

for i in li_a:
    ndict[i] += 1

result = 0
for k in ndict.keys():
    if ndict[k] > int(k):
        result += ndict[k] - int(k)
    elif ndict[k] < int(k):
        result += ndict[k]

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n=int(input())
s=[input().strip("\n") for _ in range(n)]
p=[];m=[]
for si in s:
    cnt=0;a=0;b=0
    for i in range(len(si)):
        if si[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(si)-1,-1,-1):
        if si[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,si))
    else:
        m.append((-b,si))
p.sort();m.sort()
ss=""

for _,si in p:
    ss+=si
for _,si in m:
    ss+=si
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")



### FIXED CODE ###

import sys
input = sys.stdin.readline

n=int(input())
s=[input().strip("\n") for _ in range(n)]
p=[];m=[]
for si in s:
    cnt=0;a=0;b=0
    for i in range(len(si)):
        if si[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(si)-1,-1,-1):
        if si[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,si))
    else:
        m.append((-b,si))
p.sort();m.sort()
ss=""

for _,si in p:
    ss+=si
for _,si in m:
    ss+=si
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

import bisect

s=input()
t=input()

#print(index)
condition=0
t2=list(set(t))
#print(t2)

for i in range(len(t2)):
 if s.count(t2[i])==0:
   condition=1
   break

if condition==1:
  print(-1)
else:
  index=list()
  for a in range(len(t)):
   index.append([i for i, x in enumerate(s) if x == t[a]])
  
  #print(index)
  b=index[0][0]
  j=1
  loop=0
  count=0
  if len(t)==1:
    print(b+1)
  else:
   while j <= len(t)-1:
     c=bisect.bisect_left(index[j],b)
     #print(j,index[j],b,c,loop)
     if c < len(index[j]) and c != index[j][len(index[j])-1]:
        b=index[j][c]
        #print(j,b,loop)
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
     else:
        loop=loop+len(s)
        b=index[j][0]
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
        if loop == len(s)*(10**100):
           print(-1)
           break
        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

S = input()
L = len(S)
while 1:
    old = S
    S = S.replace('01', '').replace('10', '')
    if old==S:
        break
print(L-len(S))

### FIXED CODE ###

S = list(input())
L = len(S)
from collections import Counter
c = Counter(S)
one = c['1']
zero = c['0']

print(L-abs(one-zero))
### BUGGY CODE ###

a,b,n = map(int, input().split())
print(max([int(a*x/b)-a*int(x/b) for x in range(1,n+1)]))

### FIXED CODE ###

import math
a,b,n = map(int, input().split())
if n >= b-1:
    print(math.floor(a*(b-1)/b) - a*math.floor((b-1)/b))
else:
    print(math.floor(a*n/b) - a*math.floor(n/b))
### BUGGY CODE ###


class SegmentTree:
    def __init__(self, n):
        # 0-indexed.
        x = 1
        while x < n:
            x *= 2

        self.n = x
        self.base = 0
        self.dat = [self.base] * (2 * x - 1)

    def update(self, k, v):
        # Update dat[k] to v.
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.dat[k * 2 + 1] + self.dat[k * 2 + 2]

    def query(self, a, b, k=0, l=0, r=0):
        # Returns value in [a, b).
        if l >= r:
            r = self.n

        if b <= l or r <= a:
            return self.base

        if a <= l and r <= b:
            return self.dat[k]

        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return vl + vr


N = int(input())
S = list(input())
Q = int(input())

trees = [SegmentTree(N + 1) for _ in range(26)]
for i in range(N):
    trees[ord(S[i]) - ord("a")].update(i, 1)

for _ in range(Q):
    s, *x = input().split()
    if s == "1":
        i = int(x[0]) - 1
        c = x[1]
        trees[ord(S[i]) - ord("a")].update(i, 0)
        trees[ord(c) - ord("a")].update(i, 1)
        S[i] = c
    else:
        l, r = map(int, x)
        cnt = 0
        for i in range(26):
            cnt += int(trees[i].query(l - 1, r) > 0)
        print(cnt)


### FIXED CODE ###

N = int(input())
S = list(input())
Q = int(input())
X = [input().split() for _ in range(Q)]


class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        
    def sum(self, i):
        if i == 0:
            return 0
        
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MAX = 5 * 10 ** 5 + 2
d = dict()

for c in range(ord("a"), ord("z") + 1):
    s = chr(c)
    d[s] = BIT(MAX)
    for i, v in enumerate(S):
        if v == s:
            d[s].add(i + 1, 1)


for t, i, c in X:
    if t == "1":
        i = int(i)
        
        if S[i - 1] != c:
            # Delete index
            d[S[i - 1]].add(i, -1)
            
            # Insert index
            d[c].add(i, 1)
            S[i - 1] = c
    else:
        l = int(i)
        r = int(c)
        
        res = 0
        for c in range(ord("a"), ord("z") + 1):
            s = chr(c)
            res += int(d[s].sum(r) - d[s].sum(l - 1) > 0)

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

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        l = abs(L[i] - L[j])
        r = L[i] + L[j]
        li = bisect.bisect(L,l)
        ri = bisect.bisect_left(L,r)
        for k in range(li, ri):
            if k == i or k == j: continue
            if k < i:
                ans.add((L[k], L[i], L[j]))
            elif k < j:
                ans.add((L[i], L[k], L[j]))
            else:
                ans.add((L[i], L[j], L[k]))

print(len(ans))


### FIXED CODE ###

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j)
        ans += ri - j - 1

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

N = int(input())
flag = False
for i in range(1,3501):
    for j in range(1,3501):
        if((4*i*j - N*i - N*j)==0):
            break
        w = (N*i*j)/(4*i*j - N*i - N*j)
        if(w == int(w) and w > 0):
            
            w = int(w)
            h = i
            n = j
            flag = True
            break
    
    if flag:
        break

print(h,n,w)

### FIXED CODE ###

N = int(input())
flag = False
for i in range(1,3500):
    for j in range(1,3500):
        if((4*i*j - N*i - N*j) > 0 and (N*i*j)%(4*i*j - N*i - N*j) == 0):
            w = int((N*i*j)/(4*i*j - N*i - N*j))
            h = i
            n = j
            flag = True
            break
    if flag:
        break

print(h,n,w)
### BUGGY CODE ###

N=int(input())
S_dict={}

for s_idx in range(N):
    s = input()
    
    if s not in S_dict.keys():
        S_dict[s]=1
    else:
        S_dict[s]+=1
        
s_max=max(S_dict.values())

ans = []    
 
for a,b in S_dict.items():
    if b == s_max:
        ans.append(a)
    
ans.sort()
 
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
 
counter = {}
 
for i in range(N):
    temp = input()
    if temp not in counter:
        counter.update({temp : 1})
    else:
        counter.update({temp : counter[temp] + 1})
 
m = max(counter.values())
        
ans = []    
 
for a,b in counter.items():
    if b == m:
        ans.append(a)
    
ans.sort()
 
for i in ans:
    print(i)
### BUGGY CODE ###


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def main():
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    u=UnionFind(h*w)

    for i in range(h):
        for j in range(w):
            if j !=0:
                if s[i][j-1] != s[i][j]:
                    u.union(i*w+j-1,i*w+j)
            if i !=0:
                if s[i-1][j] != s[i][j]:
                    u.union((i-1)*w+j,i*w+j)
    res = 0
    gd=u.all_group_members()
    ns = "".join(s)
    for ld in gd.values():
        black = 0
        white = 0
        for sd in ld:
            if ns[sd]=="#":
                black += 1
            else:
                white += 1
        res += black * white

    print(res)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

h,w=map(int,input().split())
s=[input() for _ in range(h)]
flag = [[0]*w for _ in range(h)]

def dfs(th,tw):
    global flag,h,w,s
    flag[th][tw] = True
    tblack = 0
    twhite = 0
    if s[th][tw] == "#":
        tblack += 1
    else:
        twhite += 1 
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        nth = th + x
        ntw = tw + y
        if nth >= 0 and nth < h and ntw >= 0 and ntw < w:
            if not flag[nth][ntw] and s[th][tw] != s[nth][ntw]:
                ttb,ttw = dfs(nth,ntw)
                tblack += ttb
                twhite += ttw
    return [tblack,twhite]
                
def main():
    global flag,h,w,s
    res = 0
    for i in range(h):
        for j in range(w):
            if not flag[i][j]:
                black,white = dfs(i,j)
                res += black * white 

    return res
print(main())
### BUGGY CODE ###

from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].add(v)
s, t = list(map(int, input().split()))
dist = [[-1 for i in range(3)] for i in range(10**5+10)]

def bfs():
  que = [(s, 0, 0)] #(x, cost, kenkenpa)
  while len(que) > 0:
    p = que.pop(0)
    if dist[p[0]][p[2]] != -1:
      continue
    dist[p[0]][p[2]] = p[1]
    for nx in graph[p[0]]:
      que.append((nx, p[1]+1, (p[2]+1)%3))

bfs()
print(dist[t][0]//3)

### FIXED CODE ###

from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = deque([s])
  dist[s] = 0
  while len(que) > 0:
    cur = que.popleft()
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)

bfs()
print(dist[t]//3)
### BUGGY CODE ###

n, a, b = map(int, input().split())
denom = 10 ** 9 + 7

total = 0
cur = 1
for r in range(1, n + 1):
    cur = cur * (n - r + 1) // r
    if a == r or b == r:
        continue
    total += cur
print(total % denom)


### FIXED CODE ###

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

mod = 10 ** 9 + 7


def comb(n, r):
    bunshi = 1
    for i in range(n-r+1, n+1):
        bunshi = bunshi * i % mod
    bunbo = 1
    for i in range(1, r + 1):
        bunbo = bunbo * i % mod
    return bunshi * pow(bunbo, mod - 2, mod) % mod


ans = (pow(2, n, mod) - 1 - comb(n, a) - comb(n, b) + 2 * mod) % mod
print(ans)
### BUGGY CODE ###

x,y = map(int,input().split())

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

hani = []

for i in range(x-y+1):
    hani.append(t[i:i+y])
ans = 1000000000000000000000000000000
for i in range(len(hani)):
    if hani[i][0] <= 0 and 0 <= hani[i][-1]:
        ans = min(ans, abs(hani[i][-1]*2)+abs(hani[i][0]), abs(hani[i][-1])+abs(hani[i][0]*2))
    elif hani[i][-1] <= 0:
        ans = min(ans, abs(hani[i][0]))
    elif 0 <= hani[i][0]:
        ans = min(ans, abs(hani[i][-1]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = float("inf")
for left in range(0, N-K+1):
    right = left+K
    minus = 0
    plus = 0
    if X[left] < 0:
        minus = min(minus, X[left])
    if X[right-1] > 0:
        plus = max(plus, X[right-1])
    ans = min(ans, 2*abs(minus)+plus, abs(minus)+2*plus)
 
print(ans)
### BUGGY CODE ###

import sys
import copy

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
ind_prev_each_letter = [0 for _ in range(26)]
hoge = [0 for _ in range(26)]
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = copy.deepcopy(hoge)
        loop += 1

    for i in range(ind_prev_each_letter[ord(x) - 97], len(letter)):
        y = letter[i]
        if y > ind_prev:
            ind_prev = y
            ind_prev_each_letter[ord(x) - 97] += 1
            break

if flag:
    print(loop * len(s) + ind_prev + 1)



### FIXED CODE ###

import numpy as np
from bisect import bisect_right

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    ind = bisect_right(letter, ind_prev)
    ind_prev = letter[ind]

if flag:
    print(loop * len(s) + ind_prev + 1)
### BUGGY CODE ###

H, W = map(int, input().split())
a = [list(map(int, input().split())) for i in range(H)]
c = 0
N = 0
ans = []
for i in range(H):
  for j in range(W):
    if a[i][j]%2==1:
      c+=1
      
while c>1:
  if a[i][j]%2==1:
    if i-1>=0 and a[i-1][j]%2==1:
      ans.append([i+1,j+1,i,j+1])
      c-=2
      a[i][j] -= 1
      a[i-1][j] += 1
      
    elif j-1>=0 and a[i][j-1]%2==1:
      ans.append([i+1,j+1,i+1,j])
      c-=2
      a[i][j] -= 1
      a[i][j-1] += 1
        
    elif j+1<W and a[i][j+1]%2==1:
      ans.append([i+1,j+1,i+1,j+2])
      c-=2
      a[i][j] -= 1
      a[i][j+1] += 1
      
    elif i+1<H and a[i+1][j]%2==1:
      ans.append([i+1,j+1,i+2,j+1])
      c-=2
      a[i][j] -= 1
      a[i+1][j] += 1
        
    elif i-1>=0:
      ans.append([i+1,j+1,i,j+1])
      a[i][j] -= 1
      a[i-1][j] += 1
      
    elif j-1>=0:
      ans.append([i+1,j+1,i+1,j])
      a[i][j] -= 1
      a[i][j-1] += 1
      
    elif j+1<W:
      ans.append([i+1,j+1,i+1,j+2])
      a[i][j] -= 1
      a[i][j+1] += 1
      
    elif i+1<H:
      ans.append([i+1,j+1,i+2,j+1])
      a[i][j] -= 1
      a[i+1][j] += 1
      
    N += 1
  if j+1==W:
    if i+1 == H:
      i = 0
      j = 0
    else:
      i +=1
  else:
    j+=1
    
        
print(N)
for i in range(N):
  L=[str(x) for x in ans[i]]
  L=" ".join(L)
  print(L)
  


### FIXED CODE ###

H, W = map(int, input().split())
a = [list(map(int, input().split())) for i in range(H)]
c = 0
N = 0
ans = []
for i in range(H):
  for j in range(W):
    if a[i][j]%2==1:
      if j+1<W:
        ans.append([i+1,j+1,i+1,j+2])
        a[i][j]-=1
        a[i][j+1]+=1
        N += 1
      elif i+1<H:
        a[i][j]-=1
        a[i+1][j]+=1
        ans.append([i+1,j+1,i+2,j+1])
        N += 1
    
        
print(N)
for i in range(N):
  L=[str(x) for x in ans[i]]
  L=" ".join(L)
  print(L)
### BUGGY CODE ###

import bisect

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

comb = 0
top_start = 0

while top_start < N:
    top_value = A[top_start]
    top_end = bisect.bisect_right(A,top_value)
    top_num = top_end - top_start
    mid_start = bisect.bisect_right(B,top_value)
    while mid_start < N:
        mid_value = B[mid_start]
        mid_end = bisect.bisect_right(B,mid_value)
        mid_num = mid_end - mid_start
        bottom_end = bisect.bisect_right(C,mid_value)
        bottom_num = N - bottom_end

        if bottom_num == 0: break

        comb += top_num * mid_num * bottom_num
        mid_start = mid_end
    top_start = top_end

print(comb)

### FIXED CODE ###

import bisect

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

comb = 0
mid_start = 0

while mid_start < N:
    mid_value = B[mid_start]
    mid_end = bisect.bisect_right(B,mid_value)
    mid_num = mid_end - mid_start
    top_end = bisect.bisect_left(A,mid_value)
    top_num = top_end
    bottom_start = bisect.bisect_right(C,mid_value)
    bottom_num = N - bottom_start
    comb += top_num * mid_num * bottom_num
    mid_start = mid_end

print(comb)
### BUGGY CODE ###

import bisect

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

for i in range(M):
    a = A.pop(-1)//2
    bisect.insort_left(A,a)

print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x:x*(-1), A))

heapq.heapify(A)

for _ in range(M):
    A_max = heapq.heappop(A)*(-1)
    heapq.heappush(A, (A_max//2)*(-1))

print(sum(A)*(-1))
### BUGGY CODE ###

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

### FIXED CODE ###

s = input()[::-1]
l = [0 for i in range(2019)]
l[0] = 1
a, b = 0, 1
ans = 0
for i in s:
    a += int(i) * b
    a %= 2019
    b *= 10
    b %= 2019
    l[a] += 1
for i in l:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

from math import factorial as f
from collections import Counter as co
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
d=co(a)
keys=[k for k,v in d.items() if v==2]
dbl=keys[0]
ll=[i for i,x in enumerate(a) if x==dbl]
b=ll[1]-ll[0]-1
m=n-1-b
def pf(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=pf(a,b//2,p)
    return d*d%p
  if b%2==1:
    return (a*pf(a,b-1,p))%p
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=f(n)%p
  b=f(k)%p
  c=f(n-k)%p
  return (a*pf(b,p-2,p)*pf(c,p-2,p))%p
for k in range(1,n+2):
  print(comb(n+1,k,mod)-comb(m,k-1,mod))

### FIXED CODE ###

from math import factorial as f
from collections import Counter as co
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
d=co(a)
keys=[k for k,v in d.items() if v==2]
dbl=keys[0]
ll=[i for i,x in enumerate(a) if x==dbl]
b=ll[1]-ll[0]
m=n-b

def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p

facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)

def comb(x,k,p):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod

for k in range(1,n+2):
  print((comb(n+1,k,mod)-comb(m,k-1,mod))%mod)