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

import sys

sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
n, k, *ab = map(int, read().split())
m = iter(ab)
AB = zip(m, m)
graph = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
ans = 1

kaidan = [0] * (k + 1)
kaidan[0] = 1
for i in range(1, k + 1):
    kaidan[i] = i * kaidan[i - 1]


def perm(k, i):
    if i > k:
        return 0
    return kaidan[k] // kaidan[k - i]


def dfs(v, p):
    global ans
    if p == -1:
        ans *= k * perm(k - 1, cnt[v])
        ans %= mod
    else:
        ans *= perm(k - 2, cnt[v] - 1)
        ans %= mod
    for u in graph[v]:
        if u == p:
            continue
        dfs(u, v)


dfs(1, -1)
print(ans)


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, readline().split())


graph = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
ans = 1

mod = 10 ** 9 + 7
kaidan = [1] * (10 ** 5 + 1)
gyaku = [1] * (10 ** 5 + 1)

for i in range(1, 10 ** 5 + 1):
    kaidan[i] = i * kaidan[i - 1] % mod
    gyaku[i] = pow(kaidan[i], mod - 2, mod)


def perm(k, i):
    if i > k:
        return 0
    return kaidan[k] * gyaku[k - i]


# dfs

stack = [1]
used = [False] * (n + 1)
while stack:
    v = stack.pop()
    used[v] = True
    if v == 1:
        ans *= k * perm(k - 1, cnt[v])
        ans %= mod
    else:
        ans *= perm(k - 2, cnt[v] - 1)
        ans %= mod
    for u in graph[v]:
        if used[u] == True:
            continue
        stack.append(u)

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
cost = [[i - j for i in h ] for j in h]
#dp[i] をiまでの最小コスト
INF = 10**9
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        mini = dp[i] + abs(cost[i][i+k])
        if dp[i + k] > mini:
            dp[i + k] = mini # i => i+k でのコストの更新
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])
### BUGGY CODE ###

N = int(input())
An = list(map(int,input().split()))
c = 0
Bn = []
Cn = []
for k in range(N):    
    Bn.append(An[k]+k)
    Cn.append(k-An[k])
Bn_Cn = set(Bn) & set(Cn)
for i in Bn_Cn:
    c+= Bn.count(i) * Cn.count(i)
print(c)

### FIXED CODE ###

from collections import Counter
N = int(input())
An = list(map(int,input().split()))
c = 0
Bn = []
Cn = []
for k in range(N):    
    Bn.append(An[k]+k)
    Cn.append(k-An[k])
Cj = Counter(Cn)
for i in Bn:
    c+=Cj[i]
print(c)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*41
p=[1]*41
for i in range(40):
    p[i+1]=p[i]*2
for i in a:
    for j in range(41):
        if i&p[j]>0:
            b[j]+=1
ans=0
for i in range(k+1):
    kai=0
    for j in range(41):
        if i&p[j]==0:
            kai+=b[j]*p[j]
        else:
            kai+=(n-b[j])*p[j]
    ans=max(ans,kai)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
a=[0]*42
for i in range(n):
    p=l[i]
    j=0
    while p>0:
        a[j]+=p%2
        p=p//2
        j+=1
ans=0
for i in range(41,-1,-1):
    if a[i]<n-a[i]:
        if k>=2**i:
            k-=2**i
            ans+=(2**i)*(n-a[i])
        else:
            ans+=(2**i)*a[i]
    else:
        ans+=(2**i)*a[i]
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = [list(input()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
s = np.array(T)
for A in range(N):
    for B in range(N):
        tmp = s[A:A+N, B:B+N]

        if (tmp == tmp.T).all():
            ans += 1
print(ans)


### FIXED CODE ###

import collections
import sys
import numpy as np
input = sys.stdin.readline
table = collections.defaultdict(set)
N = int(input())
S = [list(input().rstrip()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
table2 = [[set() for j in range(N)] for i in range(N)]

for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
T = np.array(T)
for i in range(N):
    tmp = T[i:i+N, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N - (N // 2)

    tmp = T[i+1:i+N+1, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N // 2
print(ans)
### BUGGY CODE ###

def ehand(n,a):
    for i in range(n):
        print max(a[:i]+a[(i+1):])

if __name__ == '__main__':
    n = int(raw_input())
    a = []

    for i in range(n):
        a.append(int(raw_input()))

    ehand(n,a)

### FIXED CODE ###

import copy
def calcmax(a,b,fst,scd,n):
    for i in xrange(n):
        if fst == a[i]:
            count = i

    for i in xrange(n):
        if count == i:
            print scd
        else:
            print fst

if __name__ == '__main__':
    n = int(raw_input())
    a = [int(raw_input()) for i in xrange(n)]
    print("")

    fst = max(a)

    b = copy.deepcopy(a)
    b.remove(fst)

    scd = max(b)

    calcmax(a,b,fst,scd,n)
### BUGGY CODE ###

n, k, q = list(map(int, input().split()))
a = [int(input()) for _ in range(q)]
s = k - q
if k <= q:
    for i in range(1, n + 1):
        if s + a.count(i) > 0:
            print('Yes')
        else:
            print('No')
else:
    for _ in range(n):
        print('Yes')

### FIXED CODE ###

n, k, q = list(map(int, input().split()))
a = [int(input()) for _ in range(q)]
l = [0] * n
s = k - q
for i in a:
    l[i - 1] += 1
if s <= 0:
    for i in range(n):
        if s + l[i] > 0:
            print('Yes')
        else:
            print('No')
else:
    for _ in range(n):
        print('Yes')
### BUGGY CODE ###

k = int(input())
for i in range(1,k+1):
    if int('7'*i) % k == 0:
        print(i)
        exit(0)
print(-1)

### FIXED CODE ###

k = int(input())
l = []
if 7 % k == 0:
    print(1)
    exit(0)
l.append(7 % k)
for i in range(1,k):
    a = (10 * l[i-1] + 7)
    if a % k == 0:
        print(i+1)
        exit(0)
    else:
        l.append(a % k)
print(-1)
### BUGGY CODE ###

N=int(input())
S=input()

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  j=0
  while(i<N):
    while(i+j<N and k+j < i):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    if j == 0:
      i+=1
      continue
    else:
      l = 1
      while(i+l < N and l + s[k][l] < j):
        s[k][i+l]=s[k][l]
        l+=1
      i += l
      j -= l
  k+=1
ans=0
for i in range(N):
  ans=max(ans,max(s[i]))
print(ans)
      
 


### FIXED CODE ###

N=int(input())
S=input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

s=[[0]*N for i in range(N)]
k=0
for k in range(N):
  s[k]= [0]*k + z_algo(S[k:])

ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i > j:
      ans = max(ans,j - i)
    else:
      ans=max(s[i][j],ans)
    
print(ans)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
answer = int(0)

for i in range(n+1):
    c = len(make_divisors(i))
    answer += int(c * i)


print(answer)

### FIXED CODE ###

def g(x,n):
    y = n // x
    s = int(y * (y+1) * x / 2)
    return s

n = int(input())

answer = 0
for i in range(1,n+1):
    answer += int(g(i,n))

print(answer)
### BUGGY CODE ###

from sys import stdin
import itertools

n, m, x = [int(x) for x in stdin.readline().rstrip().split()]
c = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
mi = -1

for i in itertools.permutations(c, n):
    cnt = [0]*m
    mon = 0
    for j in i:
        cnt = [cnt[k]+j[k+1] for k in range(len(cnt))]
        mon += j[0]
        if sum(1 for k in cnt if k >= x) == m:
            if mi > mon or mi == -1:
                mi = mon
            break

print(mi)


### FIXED CODE ###

from sys import stdin
import itertools

n, m, x = [int(x) for x in stdin.readline().rstrip().split()]
c = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
c.sort()
mi = -1
r = 0

for j in range(1, m + 1):
    li = [x[j] for x in c]
    li.sort(reverse=True)
    for i in range(1, len(li) + 1):
        if sum(li[:i]) >= x:
            r = max(r, i)
            break

for h in range(r, n + 1):
    for i in itertools.combinations(c, h):
        cnt = [0] * m
        mon = 0
        for j in i:
            cnt = [cnt[k]+j[k+1] for k in range(len(cnt))]
            mon += j[0]
            if sum(1 for k in cnt if k >= x) == m:
                if mi > mon or mi == -1:

                    mi = mon
                break

print(mi)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
b = []
for i in range (n):
    b = a[:i+1]
    if a[i] == min(b):
        cnt += 1
print (cnt)

### FIXED CODE ###

from sys import stdin

def main():
    n = int(stdin.readline().strip())
    l = list(map(int,stdin.readline().split()))
    ar = [-1 for _ in range(n)]
    ar[0] = l[0]
    ans = 1
    for i in range(1,n):
        if(l[i] <= ar[i-1]):
            ans+=1
            ar[i] = l[i]
        else:
            ar[i] = ar[i-1]
    print(ans)
        
main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
 
for a in A:
  result *= a

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

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
 
if 0 in A:
  print(0)
  exit()

for a in A:
  result *= a
  if result > 10**18:
    print(-1)
    exit()

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

import sys
import bisect
input = sys.stdin.readline

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    
    ans = 0
    for i, v in enumerate(odd):
        ans += bisect.bisect(even[i:], v)
    
    print(ans)
    

    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [[int(input()), i] for i in range(n)]
    a.sort()
    
    ans = 0
    for i in range(n):
        if i%2 != a[i][1]%2:
            ans += 1
    
    print(ans//2)


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

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

while flag == 0:

    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

    if flag == 0:
        for q in range(N):
            if D[q] == "1":
                for s in range(N):
                    if D[N-s-1] =="0" :
                        if q < N-s-1:
                            change(q,N-s-1)
                        break
            else:
                continue
            break
print(ans)


### FIXED CODE ###

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0
keisan = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

zero = D.count("0")
ichi = D.count("1")

for p in range(zero):
    if D[p] == "1":
        ans += 1


"""
while flag == 0:

    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

    if flag == 0:
        for q in range(N):
            if D[q] == "1":
                for s in range(N):
                    keisan += 1
                    if D[N-s-1] =="0" :
                        if q < N-s-1:
                            change(q,N-s-1)
                        break
            else:
                continue
            break
"""
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
k=0
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    ans+=1
    IsMatch=False
    done=set()
    #print('Day',ans,IsMatch,nx)
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            #print('Day',ans,'Match',c1,'vs',c2)
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
            #print('i,t,d',i,t,'done=',done,'nx=',nx,n_i,n_n_i)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

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

N,K,Q=[int(e) for e in input().split(' ')]
lA=[int(input()) for _ in range(Q)]

for i in range(N):
    if Q-lA.count(i+1) >= K:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q=[int(e) for e in input().split(' ')]

c=[0]*N
for _ in range(Q):
    c[int(input())-1]+=1

for i in range(N):
    if Q-c[i] >= K:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
result = 0
size = B - A + 1
for i in range(size):
    if((A + i)%C == 0):
        pass
    elif((A + i)%D ==0):
        pass
    else:
        result += 1

print(result)


### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    A = LI()
    B = LI()
    mb = B[-1]
    for i in range(N):
        if A[i] == B[i]:
            if B[i] < mb:
                p = bisect.bisect_left(B[i+1:],B[i]+1) + i+1
                if p > N-1:
                    print('No')
                    return
            else:
                p = N-1 - i
            B[i],B[p] = B[p],B[i]
            if A[i] == B[i]:
                print('No')
                return
    print('Yes')
    print(*B,sep=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    B = LI()

    c = collections.Counter()
    for x in A:
        c[x] += 1
    for x in B:
        c[x] += 1
        if c[x] > N:
            print('No')
            return

    s = 0
    for i in range(N):
        if A[i] == B[i]:

            p = bisect.bisect_left(B,B[i]+1,i+1)
            if p > N-1:
                p = s
                s += 1
                while B[i] == B[s]:
                    s+=1

            B[i],B[p] = B[p],B[i]
    print('Yes')
    print(*B,sep=' ')

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

N,K,Q=map(int, input().split())
A=[]
for i in range(0,Q):
    A.append(int(input()))
for i in range(0,N):
    if K+A.count(i+1)-Q>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int, input().split())
M=K-Q
A=[M]*N
for i in range(Q):
    B=int(input())
    A[B-1]+=1
for i in range(N):
    if A[i]<1:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N = int(input())
A = []
P = 1000000000
for i in range(N):
    tmp = input().split(".")
    if len(tmp) == 2:
        a = int(tmp[1])
        for j in range(9-len(tmp[1])):
            a *= 10
        A.append(int(tmp[0]) * P + a)
    else:
        A.append(int(tmp[0]) * P)

div2 = [0 for i in range(N)]
div5 = [0 for i in range(N)]

for i in range(N):
    tmp = A[i]
    while tmp % 2 == 0:
        div2[i] += 1
        tmp = tmp//2
    while tmp % 5 == 0:
        div5[i] += 1
        tmp = tmp//5

cnt = [[0 for i in range(19)] for i in range(19)]

for i in range(N):
    d2 = div2[i]
    d5 = div5[i]
    if d2 > 18:
        d2 = 18
    if d5 > 18:
        d5 = 18
    cnt[d2][d5] += 1

ans = 0

for i in range(N):
    lower2 = 18 - div2[i]
    lower5 = 18 - div5[i]

    if lower2 < 0:
        lower2 = 0
    if lower5 < 0:
        lower5 = 0

    for j in range(lower2, 19):
        for k in range(lower5, 19):
            ans += cnt[j][k]

for a in A:
    if a % P == 0:
        ans -= 1

print(ans//2)


### FIXED CODE ###

N = int(input())
A = []
P = 1000000000
for i in range(N):
    tmp = input().split(".")
    if len(tmp) == 2:
        a = int(tmp[1])
        for j in range(9-len(tmp[1])):
            a *= 10
        A.append(int(tmp[0]) * P + a)
    else:
        A.append(int(tmp[0]) * P)

div2 = [0 for i in range(N)]
div5 = [0 for i in range(N)]

for i in range(N):
    tmp = A[i]
    while tmp % 2 == 0:
        div2[i] += 1
        tmp = tmp//2
    while tmp % 5 == 0:
        div5[i] += 1
        tmp = tmp//5

cnt = [[0 for i in range(19)] for i in range(19)]

for i in range(N):
    d2 = div2[i]
    d5 = div5[i]
    if d2 > 18:
        d2 = 18
    if d5 > 18:
        d5 = 18
    cnt[d2][d5] += 1

ans = 0

for i in range(N):
    lower2 = 18 - div2[i]
    lower5 = 18 - div5[i]

    if lower2 < 0:
        lower2 = 0
    if lower5 < 0:
        lower5 = 0

    for j in range(lower2, 19):
        for k in range(lower5, 19):
            ans += cnt[j][k]

for a in A:
    if a % P == 0:
        ans -= 1

print(ans//2)
### BUGGY CODE ###

r,b,g,m = map(int,input().split())
ans = 0
for i in range(3001):
  for j in range(3001):
    if m >= r*i+b*j and (m-r*i-b*j)%g == 0:
      ans += 1
print(ans)

### FIXED CODE ###

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

n,m = map(int,input().split())
a = sorted(map(int,input().split()))

for i in range(m):
    a[-1] //= 2
    
    if 1 < len(a) and a[-2] > a[-1]:
        a = sorted(a)
    
print(sum(a))

### FIXED CODE ###

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

import heapq
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

for i in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a,-(-b//2))
    
print(sum(a)*(-1))
### BUGGY CODE ###

k=int(input())
ans=0
from fractions import gcd
import functools 
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            @functools.lru_cache(None) 
            def gc(x,y):
                if x>y:
                    x,y=y,x
                return gcd(x,y)

            ans+=gcd(a,gcd(b,c))
print(ans)



### FIXED CODE ###

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

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
cnt=0
x=[]
i=0
b__=b.copy()
rev=0
while(b__):
     b_=b__.pop()
     while(1):
          try:
               c_=c.pop()
          except:
               rev+=cnt
               x.append(rev)
               cnt=0
               break
          if c_>b_:
               cnt+=1
          else:
               rev+=cnt
               x.append(rev)
               cnt=0
               c.append(c_)
               break
cnt=0
i=n-1
rev=0
while(a):
     a_=a.pop()
     for i in range(1,n+1):
          idx=n-i
          b_=b[idx]
          if b_>a_:
               cnt+=x[i-1]
          else:
               break
print(cnt)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
cnt=0
x=[]
i=0
b__=b.copy()
rev=0
while(b__):
     b_=b__.pop()
     while(1):
          try:
               c_=c.pop()
          except:
               rev+=cnt
               x.append(rev)
               cnt=0
               break
          if c_>b_:
               cnt+=1
          else:
               rev+=cnt
               x.append(rev)
               cnt=0
               c.append(c_)
               break
cnt=0
i=n-1
rev=0
ans=0
while(a):
     a_=a.pop()
     while(1):
          try:
               b_=b.pop()
          except:
               rev+=cnt
               ans+=rev
               cnt=0
               break
          if b_>a_:
               cnt+=x.pop(0)
          else:
               rev+=cnt
               ans+=rev
               cnt=0
               b.append(b_)
               break
print(ans)