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

N, M, K = map(int, input().split())
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans_x = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, N+1):
    ans_x += N*(N+1)//2-i*(i+1)//2-i*(N-i)
    #for j in range(i+1, N+1):
    #    ans_x += j-i
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, M+1):
    ans_y += M*(M+1)//2-i*(i+1)//2-i*(M-i)
    #for j in range(i+1, M+1):
    #    ans_y += j-i
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)

### FIXED CODE ###

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

import math

from operator import mul
from functools import reduce
def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans_x = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, N+1):
#    ans_x += N*(N+1)//2-i*(i+1)//2-i*(N-i)
    #for j in range(i+1, N+1):
    #    ans_x += j-i
ans_x = (N*N*(N+1) + N*(N+1)*(2*N+1)//6 - (2*N+1)*N*(N+1)//2)//2
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, M+1):
#    ans_y += M*(M+1)//2-i*(i+1)//2-i*(M-i)
    #for j in range(i+1, M+1):
    #    ans_y += j-i
ans_y = (M*M*(M+1) + M*(M+1)*(2*M+1)//6 - (2*M+1)*M*(M+1)//2)//2
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

import math
n=int(input())
i = list(map(int, input().split()))
s=[]
cnt=0
x=math.inf
for j in range(n):
    if min(x,i[j])==i[j]:
        x=i[j]
        cnt+=1
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str, input().split())) for i in range(Q)]
for i in range(Q):
    if Query[i][0] == "1":
        S = S[::-1]
    elif Query[i][1] == "1":
        S = Query[i][2] + S

    else:
        S = S + Query[i][2]
print(S)


### FIXED CODE ###

import collections
S = input()
Q = int(input())
q = collections.deque()
q.append(S)
inversion = True
for i in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        inversion = not(inversion)
    elif Query[1] == "1":
        if inversion:
            q.appendleft(Query[2])
        else:
            q.append(Query[2])
    else:
        if inversion:
            q.append(Query[2])
        else:
            q.appendleft(Query[2])

if inversion:
    print("".join(q))
else:
    print("".join(q)[::-1])
### BUGGY CODE ###

def main2():
    N = int(input().strip())
    r_stack=[]
    stack=[]
    for n in input().split():
        n = int(n)
        if len(r_stack)%2!=0:
            stack.append(n)
            r_stack.insert(0,n)
        else:
            stack.insert(0,n)
            r_stack.append(n)
    if N % 2 ==0:
        print(*r_stack)
    else:
        print(*stack)

if __name__ == "__main__":
    main2()

### FIXED CODE ###

from collections import deque
def main3():
    d = deque()
    rd= deque()
    N = int(input().strip())
    for n in input().split():
        if len(rd)%2!=0:
            d.append(n)
            rd.appendleft(n)
        else:
            rd.append(n)
            d.appendleft(n)
    if N % 2 ==0:
        print(*rd)
    else:
        print(*d)

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

H,W,K = map(int, input().split())
S = [list(map(str,input())) for _ in range(H)]

ans = [[-1]*W for _ in range(H)]

cnt = 1
cnt_max = 0
for i in range(H):
	ichigo = S[i].count("#")
	if ichigo == 0:
		ans[i].clear()
		continue
	cnt_max = cnt + ichigo - 1
	for j in range(W):
		if S[i][j] == ".":
			ans[i][j] = min(cnt,cnt_max)
		else:
			ans[i][j] = min(cnt,cnt_max)
			cnt += 1
	cnt = cnt_max+1
cond = 1
while cond:
	cond = 0
	for i in range(H):
		if ans[i] == []:
			cond = 1
			if i == H-1:
				ans[i] = ans[i-1]
			else:
				ans[i] = ans[i+1]

for i in range(H):
	for j in range(W):
		if j == W-1:
			print(ans[i][j])
		else:
			print(ans[i][j], end = " ")

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'#')

A = np.zeros((H,W), np.int32)
A[X,Y] = np.arange(1,K+1)

np.maximum.accumulate(A, axis = 1, out = A)

for w in range(W-2, -1, -1):
	A[:,w] += A[:,w+1] * (A[:,w] == 0)

for h in range(1,H):
	if A[h,-1] == 0:
		A[h] += A[h-1]
for h in range(H-1,-1,-1):
	if A[h,-1] == 0:
		A[h] += A[h+1]

print('\n'.join(' '.join(row) for row in A.astype(str)))
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [[] for i in range(31)]
b.sort()
for i in range(30):
    mod = 2**(i+1)
    for j in b:
        l[i].append(j%mod)
    l[i].sort()

ans = [0]*31

for i in a:
    
    for j in range(30):
        mod = pow(2,j)
        x = i%(mod*2)
        count = bisect.bisect_right(l[j],2*mod-x-1)-bisect.bisect_left(l[j],mod-x)
        count += bisect.bisect_right(l[j],4*mod-x-1)-bisect.bisect_left(l[j],3*mod-x)
        ans[j] += count
count = 0
for i in range(31):
    count += pow(2,i)*(ans[i]%2)
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [[] for i in range(29)]
for i in range(29):
    mod = 2**(i+1)
    for j in b:
        l[i].append(j%mod)
    l[i].sort()

ans = 0
for i in range(29):
    al = []
    count = 0
    mod = 2**i
    for j in a:
        al.append(j%(2*mod))
    al.sort(reverse = True)
    r1 = r2 = r3 = 0
    for j in al:
        while r1 < n and l[i][r1]+j < mod:
            r1 += 1
        while r2 < n and l[i][r2]+j < 2*mod:
            r2 += 1
        while r3 < n and l[i][r3]+j < 3*mod:
            r3 += 1
        count += n-r3+r2-r1
    ans += (count%2) << i
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
k = list(map(int,input().split()))

D_list=[]
M_list=[]
C_list=[]

for i in range(N):
  if S[i] == "D":
    D_list.append(i)
  if S[i] == "M":
    M_list.append(i)
  if S[i] == "C":
    C_list.append(i)
    
k_list=[0]*Q
  
M_sum=[0]*N  
for i in range(1,N):
  if i in M_list:
    M_sum[i]=M_sum[i-1]+1
  else:
    M_sum[i]=M_sum[i-1] 

num=0
c_start=0
for d in D_list:
  time=0
  c_loc=c_start
  while C_list[c_loc] <= d+max(k):
   # print(d,C_list[c_loc])
    if C_list[c_loc] > d:
      if time==0:
        c_start=c_loc
        time+=1
      num=M_sum[C_list[c_loc]]-M_sum[d]
      #print(M_sum[C_list[c_loc]],M_sum[d])
      for q in range(Q):
        if k[q] > C_list[c_loc] - d:
          k_list[q]+=num
    c_loc+=1
    if c_loc >= len(C_list):
        break

for i in range(Q):
  print(k_list[i])
            
            
        
  
  

### FIXED CODE ###


import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

DM_total = [(0,0,0)]
C_list = []

for i in range(N):
	if S[i] == "D":
		DM_total.append((DM_total[-1][0] + 1, DM_total[-1][1], DM_total[-1][2]))
	elif S[i] == "M":
		DM_total.append((DM_total[-1][0], DM_total[-1][1] + 1, DM_total[-1][2] + DM_total[-1][0]))
	else:
		DM_total.append(DM_total[-1])
	if S[i] == "C":
		C_list.append(i)

ans_list = [0]*Q

for c in C_list:
	for q in range(Q):
		if k[q] > c:
			ans_list[q] += DM_total[c + 1][2]
		else:
			ans_list[q] += DM_total[c + 1][2] - DM_total[c + 1 - k[q]][2]
			ans_list[q] -= DM_total[c + 1 - k[q]][0] * (DM_total[c + 1][1] - DM_total[c + 1 - k[q]][1])

for q in range(Q):
	print(ans_list[q])
### BUGGY CODE ###

import numpy as np

N=int(input())
S=input()
r = len([x for x in S if x == "R"])
g = len([x for x in S if x == "G"])
b = len([x for x in S if x == "B"])
 
ans = r * g * b
 
for i in range(N):
  for k in [N - k_ - 1 for k_ in range(N)]:
    tar_j = i + k
    if (tar_j > 2 * i) & (tar_j < 2 * k):
      if np.mod(tar_j, 2) == 0:
        j = int(tar_j / 2)
        s = S[i] + S[j] + S[k]
        if ("R" in s) & ("G" in s) & ("B" in s):
          ans -= 1
    else:
      break
print(ans)


### FIXED CODE ###


#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"# * 1000
#N = len(S)

N=int(input())
S=input()
r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
b = N - r - g
 
ans = r * g * b
 
is_break = False
for i in range(N):
    for j in range(i, int((N+i)/2 + 1)):
        k = 2 * j - i
        if k < N:
            s = S[i] + S[j] + S[k]
            if ("R" in s) & ("G" in s) & ("B" in s):
                    ans -= 1

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

import itertools
n = int(input())
l = list(map(int,input().split()))
cnt = 0

for x,y,z in itertools.combinations(l,3):
  lt = sorted([x,y,z])
  if lt[2] < lt[0] + lt[1]:
    cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
cnt = 0

for i in range(n):
  for j in range(1+i,n):
    a,b = l[i],l[j]
    cnt += bisect.bisect_left(l,a+b)-(j+1)
    
print(cnt)
### BUGGY CODE ###

S = input().rstrip()
Q = int(input().rstrip())
a = -1
for _ in range(Q):
    stdin = input().rstrip()
    if int(stdin[0]) == 1:
        a = ~a
    else:
        T,F,C = stdin.split()
        if int(F) == 2+a:
            S = C + S
        else:
            S = S + C
if a == 0:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input().rstrip()
Q = int(input().rstrip())
a = -1
before =[]
after =[]
for _ in range(Q):
    stdin = input().rstrip()
    if int(stdin[0]) == 1:
        a = ~a
    else:
        T,F,C = stdin.split()
        if int(F) == 2+a:
            before.append(C)
        else:
            after.append(C)
S = ''.join(before)[::-1] + S + ''.join(after)
if a == 0:
    S = S[::-1]
print(S)
### BUGGY CODE ###

import math
H, W, A, B = map(int,input().split())
def f(a,b):
    p = math.factorial(a+b-2)
    q = math.factorial(a-1)
    r = math.factorial(b-1)
    S = p // (q*r)
    return S
T = 0
for i in range(1,B+1):
    P = f(H-A,i)
    Q = f(A,W-i+1)
    T = T + P*Q
R = f(H,W) - T
ans = R % (10**9+7)
print(ans)

### FIXED CODE ###

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N= [0]*(H+W)
N[H+W-1] = power(M[H+W-1], e-2)
for i in range(H+W-2, -1, -1):
    N[i] = N[i+1] * (i+1) % e

def c(a,b):
    return M[a]*N[b]*N[a-b]%e

T = 0
for i in range(W-B):
    P = c(H+W-A-i-2,H-A-1)
    Q = c(A+i-1,i)
    T = (T + P*Q)
print(T%e)
### BUGGY CODE ###

n=int(input())
ss=input()
l=[["R","G","B"],["R","B","G"],["G","R","B"],["G","B","R"],["B","R","G"],["B","G","R"]]
ans=0
for v in l:
    for i in range(n-2):
        if ss[i]==v[0]:
            for k in range(i+1,n-1):
                if ss[k]==v[1]:
                    ans+=ss[k+1:].count(v[2])
                    if (k+k-i <=n-1) and ss[k+k-i]==v[2]:
                        ans-=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=s.count("R")*s.count("G")*s.count("B")  # 第１条件の全事象
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+j-i
        if k<n and s[k]!=s[i] and s[k]!=s[j] and s[i]!=s[j]: # 第1条件 かつ not第２条件
            ans-=1
print(ans)
### BUGGY CODE ###

import bisect
n,m = map(int,input().split())

g = [[ ] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    if a == 1 or a == n or b == 1 or b == n:
        bisect.insort(g[a],b)
        bisect.insort(g[b],a)

    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

if len(g[n]) == 0:
    print('IMPOSSIBLE')
    exit()

for i in g[n]:
    if g[i][0] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

### FIXED CODE ###

import bisect
n,m = map(int,input().split())

g = [[ ] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    if a == 1 or a == n or b == 1 or b == n:
        g[a].append(b)
        g[b].append(a)

    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

#g[4].sort()

#print(g[4])

if len(g[n]) == 0:
    print('IMPOSSIBLE')
    exit()

for i in g[n]:
    g[i].sort()
    if g[i][0] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

import itertools
import math

N = int(input())

for i in range(N):
    count = 0
    a = list(range(1, int(math.sqrt(i) + 1)))
    b = list(itertools.combinations_with_replacement(a, 3))
    for k in range(len(b)):
        f = b[k][0] ** 2 + b[k][1] ** 2 + b[k][2] ** 2 + b[k][0] * b[k][1] + b[k][1] * b[k][2] + b[k][2] * b[k][0]
        if f == i + 1:
            count += len(sorted(set(itertools.permutations(b[k]))))
    print(count)


### FIXED CODE ###

import math

N = int(input())

ans = [0] * (N + 1)

for i in range(1, int(math.sqrt(N)) + 1):
    for j in range(1, int(math.sqrt(N)) + 1):
        for k in range(1, int(math.sqrt(N)) + 1):
            v = i * i + j * j + k * k + i * j + j * k + k * i
            if v <= N:
                ans[v] += 1

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

s = input()

c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
d = 1
t = 0
x = 0
for i,j in enumerate(s[::-1]):
	x = (x + int(j)*pow(10,i))%mod
	c[x] += 1

ans = 0
for i in range(2019):
	ans += (c[i]*(c[i]-1))//2
print (ans)


### FIXED CODE ###

s = input()

c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
d = 1
x = 0
for i,j in enumerate(s[::-1]):
	x = (x + int(j)*pow(10,i,mod))%mod
	c[x] += 1

ans = 0
for i in range(2019):
	ans += (c[i]*(c[i]-1))//2
print (ans)
### BUGGY CODE ###

from sys import stdin

gets = stdin.readline


def main():
    n = int(gets())
    h, w = 0, 0
    flag = False
    for _ in range(3500):
        h += 1
        w = 0
        for _ in range(3500):
            w += 1
            x = (n * h * w)
            y = (4 * h * w - n * h - n * w)
            if x >= y > 0 == x % y:
                print(h, w, x // y)
                flag = True
                break
        if flag:
            break
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin

gets = stdin.readline


def main():
    n = int(gets())
    h, w = 0, 0
    flag = False
    for _ in range(3500):
        h += 1
        w = 0
        for _ in range(3500):
            w += 1
            y = (4 * h * w - n * (h + w))
            if y > 0:
                modulo = n % y * h % y * w % y
                if modulo % y == 0:
                    print(h, w, (n*h*w)//y)
                    flag = True
                    break
        if flag:
            break
    return


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

n = int(input())
l = []
cnt = 0
for i in range(n):
    x = int(input())
    l.append(x)

x = set()
for i in l:
    if i in x:
        continue
    else:
        x.add(i)
        if l.count(i)%2 ==1:
            #print(i, l.count(i))
            cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
l = []
cnt = 0
for i in range(n):
    x = int(input())
    l.append(x)


x = sorted(l)
i=1
same=1
while i<n:
    if x[i]==x[i-1]:
        same += 1
    else:
        if same%2 == 1:
            cnt += 1
        same = 1
    i += 1

cnt += same%2
print(cnt)
### BUGGY CODE ###

N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[k] < L[i] + L[j]:
                ans += 1
print(ans)


### FIXED CODE ###

import bisect

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

N = int(input())
A = [int(a) for a in input().split()]
B = []
for n in range(N):
    B.append(A[n])
    B = B[::-1]
print(*B)

### FIXED CODE ###

from collections import deque

N = int(input())
A = [int(a) for a in input().split()]
B = deque([])
for n in range(N):
    if n % 2 == 0:
        B.append(A[n])
    else:
        B.appendleft(A[n])
if N % 2 == 0:
    print(*B)
else:
    print(*list(B)[::-1])
### BUGGY CODE ###

import math
n=int(input())
l=list(map(int,input().split()))
d={}
for i in l:
    if i in d:
        d[i]+=1 
    else:
        d[i]=1 
count=0
for k in d.keys():
        x=d[k]
        if x<2:
            count+=0
        else:
            count+=math.factorial(x)/(math.factorial(x-2)*2)

for i in l:
    x=d[i]
    #print(i, x)
    if x>=2:
        val=math.factorial(x)/(math.factorial(x-2)*2)
        ans=count-val
        if x>=3:
            val1=math.factorial(x-1)/(math.factorial(x-3)*2)
        else:
            val1=0
        ans+=val1
    else:
        if x==2:
            ans=count-1 
        else:
            ans=count 
    print(int(ans))
            


### FIXED CODE ###

import math
n=int(input())
l=list(map(int,input().split()))
d={}
for i in l:
    if i in d:
        d[i]+=1 
    else:
        d[i]=1 
count=0
for k in d.keys():
        x=d[k]
        if x<2:
            count+=0
        else:
            count+=x*(x-1)//2

for i in l:
    x=d[i]
    #print(i, x)
    if x>=2:
        val=x*(x-1)//2
        ans=count-val
        if x>=3:
            x-=1
            val1=x*(x-1)//2
        else:
            val1=0
        ans+=val1
    else:
        if x==2:
            ans=count-1 
        else:
            ans=count 
    print(int(ans))
### BUGGY CODE ###

N,M = map(int,input().split())
array = []
array2 = [[] for i in range(N)]
for i in range(M):
    array.append(list(map(int,input().split())))
    array2[array[i][0]-1].append(array[i][1])

for i in range(N):
    array2[i] = sorted(array2[i])

for i in range(M):
    pnum = str(array[i][0])
    cnum = str(array2[array[i][0]-1].index(array[i][1])+1)
    print('0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum)


### FIXED CODE ###

N,M = map(int,input().split())
PY = []
for i in range(M):
    P,Y = map(int,input().split())
    PY.append([P,Y,i])

PY.sort()
ans = [0 for i in range(M)]
count = 0
old = 0
for j in range(M):
    p,y,inum = PY[j]
    if old == p:
        pnum = p
        cnum = count
    else:
        old = p
        count = 1
        pnum = p
        cnum = 1

    count += 1
    pnum = str(pnum)
    cnum = str(cnum)
    ans[inum] = '0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum

for i in range(M):
    print(ans[i])
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
for i in t:
  if i in d:
    del d[d.index(i)]
  else:
    print("NO")
    exit()
print("YES")

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
d.sort()
t.sort()
i,j=0,0
while i<m:
  if t[i]<d[j]:
    print("NO")
    exit()
  elif t[i]==d[j]:
    i+=1
    j+=1
  else:
    j+=1
  if j==n and i<m:
    print("NO")
    exit()
print("YES")
### BUGGY CODE ###

import math
K = int(input())
m = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      m += math.gcd(math.gcd(i, j), k)
print(m)

### FIXED CODE ###

from math import gcd
K = int(input())
m = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    w = gcd(i, j)
    if w==1:
      m += K
    else:
      for k in range(1, K+1):
        m += gcd(w, k)
print(m)
### BUGGY CODE ###

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()
count=0
import bisect
for i in range(0,n):
  tempb=bisect.bisect_right(b,a[i])
  if tempb!=len(b):
    for j in range(tempb,n):
      tempc=bisect.bisect_right(c,b[j])
      tempcl=n-tempc
      count=count+tempcl
print(count)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  temp1=bisect.bisect_left(a,b[i])
  temp2=bisect.bisect(c,b[i])
  ans=ans+temp1*(n-temp2)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
R = 1
Top = []
Bot = []
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Bot += [c]
    else:
      Top = [c] + Top
S = ''.join(Top+[S]+Bot)
S = S if R==1 else S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * N

for i in range(N):
    if (i + 1) in a:
        dp[i] = 0
    elif i == 0:
        dp[i] = 1
    elif i == 1 and dp[0] == 1:
        dp[i] = 2
    elif i == 1 and dp[0] == 0:
        dp[i] = 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N-1] % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * (N + 1)

for i in a:
    dp[i] = 0

for i in range(2, N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[N] % MOD)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
if n%2==1:
    for i in a:
        if int(i)%2==1: b.insert(0,i)
        else:  b.append(i)
else:
    for i in a:
        if int(i)%2==0: b.insert(0,i)
        else:  b.append(i)
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = list(input().split())
b = []
if n%2==1:
    b = a[::-2]+a[1::2]
else:
    b = a[::-2]+a[::2]
print(" ".join(b))
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

def is_lunlun(n):
  nn = [int(_) for _ in str(n)]

  last = 0
  for i in range(len(nn)):
    if i > 0:
      if abs(nn[i] - last) > 1:
        return False
    last = nn[i]
  return True

cnt = 0

for i in range(1,10**10):
  if(is_lunlun(i)):
    if cnt == k-1:
      print(i)
      exit()
    cnt+=1

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

luns = []


def make_lunlun(l):
    if l > 3234566667:
        return
    luns.append(l)

    last = l-l//10*10

    if last!=0:
        make_lunlun(l*10 + last-1)
    make_lunlun(l*10+last)
    if last!=9:
        make_lunlun(l*10 + last+1)


for i in range(1,10):
    make_lunlun(i)

print(sorted(luns)[k-1])
### BUGGY CODE ###

N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    result.append(sum(abs_c[n:n+K]))

idx = result.index(min(result))
route = candles[idx:idx+K]

r1 = abs(route[0]) + abs(route[-1]-route[0])
r2 = abs(route[-1]) + abs(route[0]-route[-1])
print(min(r1, r2))

### FIXED CODE ###

N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    r1 = abs(candles[n]) + abs(candles[n+K-1]-candles[n])
    r2 = abs(candles[n+K-1]) + abs(candles[n]-candles[n+K-1])
    result.append(min(r1, r2))

print(min(result))