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

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = defaultdict(lambda: -1)
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    print(stops[d+1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
### BUGGY CODE ###

from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(k):
    b = [0] * (n + 1)
    for j in range(n):
        b[max(0, j - a[j])] += 1
        b[min(n, j + a[j] + 1)] -= 1
    a = list(accumulate(b))
    if sum(a) == n ** 2:
        a.pop()
        print(*a)
        exit()

a.pop()
print(*a)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(k):
    b = [0] * (n + 1)
    for j in range(n):
        b[max(0, j - a[j])] += 1
        b[min(n, j + a[j] + 1)] -= 1
    a = list(accumulate(b))
    if sum(a) == n ** 2:
        a.pop()
        print(*a)
        exit()

a.pop()
print(*a)
### BUGGY CODE ###

N=int(input())
A_list = list(map(int, input().split()))
for i in range(N):
  print(A_list.count(i+1))


### FIXED CODE ###

import collections

N=int(input())
A_list = list(map(int, input().split()))
c = collections.Counter(A_list)
for i in range(N):
  print(c[i+1])
### BUGGY CODE ###

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

A = [list(map(lambda x: x == "#", input())) for i in range(H)]

lu = [[float("inf") for i in range(W + 2)] for j in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
        if A[i - 1][j - 1]:
            lu[i][j] = 0
        elif j < W and A[i - 1][j]:
            lu[i][j] = 1

for i in range(H, 0, -1):
    for j in range(W, 0, -1):
        lu[i][j] = min(lu[i + 1][j]+1, lu[i][j + 1]+1, lu[i][j])


dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


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

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = []
[dist.extend(l[1:-1]) for l in lu[1:-1]]
print(max(dist))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    list10 = range(0,10)
    list13 = range(0,13)
    keta =1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in list10:
                addmod = j*keta%13
                for k in list13:
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*keta)%13
            for k in list13:
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD
        keta*=10
        keta%=13
    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    list10 = range(0,10)
    list13 = range(0,13)
    keta =1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in list10:
                addmod = j*keta%13
                for k in list13:
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*keta)%13
            for k in list13:
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD
        keta*=10
        keta%=13
    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

if __name__ == '__main__':
    s = input()
    q = int(input())
    ans = s
    rev_count = 0
    leftList = []
    rightList =[]
    alist =[]

    for i in range(q):
        a = [i for i in input().split()]
        alist.append(a)
        if len(a) == 1:
            rev_count = rev_count +1

    if rev_count % 2 ==1:
        ans = ans[::-1]

    for i in alist:
        if len(i) == 1:
            rev_count = rev_count -1
        else:
            if int(i[1]) == 1:
                if rev_count % 2 == 1:
                    rightList.append(i[2])
                else:
                    leftList.insert(0,i[2])

            else:
                if rev_count % 2 == 1:
                    leftList.insert(0,i[2])
                else:
                    rightList.append(i[2])

    ans = ''.join(leftList)+ ans+''.join(rightList)

    print(ans)



### FIXED CODE ###

from collections import deque

if __name__ == '__main__':
    s = input()
    q = int(input())
    ans = s
    rev_count = 0
    leftList = deque()
    rightList =[]
    alist =[]

    for i in range(q):
        a = [i for i in input().split()]
        alist.append(a)
        if len(a) == 1:
            rev_count = rev_count +1

    if rev_count % 2 ==1:
        ans = ans[::-1]

    for i in alist:
        if len(i) == 1:
            rev_count = rev_count -1
        else:
            if int(i[1]) == 1:
                if rev_count % 2 == 1:
                    rightList.append(i[2])
                else:
                    leftList.appendleft(i[2])

            else:
                if rev_count % 2 == 1:
                    leftList.appendleft(i[2])
                else:
                    rightList.append(i[2])

    ans = ''.join(leftList)+ ans+''.join(rightList)

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



ais = [raw_input() for _ in range(int(raw_input()))]
ais.sort(key = len)
import collections
cc = collections.Counter()

def f(w):
	res = set()
	for i in range(len(w)):
		#keep i th
		res.add(w[i])
		for j in range(i+1,len(w)):
			res.add(w[i] + w[j:])
	
	return res

ans = 0
for w in ais:
	for g in f(w):
		ans += cc[g]
	cc[w] +=1
print ans

### FIXED CODE ###


class TN(object):
	def __init__(self):
		self.h = {}
		self.count = 0
		self.need = collections.Counter()


ais = [raw_input() for _ in range(int(raw_input()))]
ais.sort(key = len)
import collections
cc = collections.Counter()

ans = 0
root = TN()
for w in ais:
	
	###COUNT
	cur =  root
	for j in range(len(w)-1, -1, -1):
		for k in cur.need:
			if k in w[:j+1]:
				ans += cur.need[k]
		if w[j] in cur.h:
			cur = cur.h[w[j]]
		else:
			break
	###UPDATE
	cur = root
	for j in range(len(w) - 1, 0, -1):
		if w[j] not in cur.h:
			cur.h[w[j]] = TN()
		cur = cur.h[w[j]]
	cur.need[w[0]] += 1

print ans
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    ans += bisect_left(l[j+1:], l[j]+l[i])
    
print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    #print("i: "+str(i)+"  j: "+str(j))
    #print(max(l[i], l[j])-min(l[i], l[j]))
    #print(l[i]+l[j])
    #print(list(filter(lambda x: max(l[i], l[j])-min(l[i], l[j])<x<l[i]+l[j], l[j+1:])))
    #temp1 = bisect_left(l[j+1:], l[j]-l[i])
    #temp2 = bisect_left(l[j+1:], l[j]+l[i])
    #print(temp1)
    #print(temp2)
    ans += bisect_left(l[j+1:], l[j]+l[i])
    
print(ans)
### BUGGY CODE ###

import sys
imput =sys.stdin.readline
N, Q =map(int,input().split())
S =input()
for _ in range(Q):
  l,r = map(int,input().split())
  print(S[l-1:r].count("AC"))
  

### FIXED CODE ###

import sys
imput =sys.stdin.readline
N, Q =map(int,input().split())
S =[i for i in input()]
q = [[int(i) for i in input().split()] for _ in range(Q)]
num = 0
for i in range(N-1):
    if S[i]+S[i+1]=="AC":
        num += 1
    S[i] = num
S[-1] = num
S.append(0)
for lr in q:
  print(S[lr[1]-2] -S[lr[0]-2])
### BUGGY CODE ###

from collections import Counter

N=int(input())
A=[int(i) for i in input().split(" ")]
c=Counter(A)
c=dict(c)

for a in A:
    c[a]-=1
    retval=0
    for key in c:
        retval+=c[key]*(c[key]-1)//2
    print(retval)
    c[a]+=1


### FIXED CODE ###

from collections import Counter

N=int(input())
A=[int(i) for i in input().split(" ")]
c=Counter(A)
c=dict(c)
base=0
for key in c:
    base+=c[key]*(c[key]-1)//2


for a in A:
    _base=base
    ca=c[a]
    if ca>1:
        _base-=ca*(ca-1)//2
        _base+=(ca-1)*(ca-2)//2
    print(_base)
### BUGGY CODE ###

from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import string

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

n,k = get_tuple()
ls = get_list()
i = 0
prod = 1
j = 0
start = ls[j]
while i<k:
    prod *= ls[i]
    i += 1

while i<n:
    oldprod = prod
    prod = int(prod/ls[j])
    prod *= ls[i]
    if oldprod>=prod:
        print("No")
    else:
        print("Yes")

    i += 1
    j += 1



### FIXED CODE ###

from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import string

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

n,k = get_tuple()
ls = get_list()
j = 0
i = k
while i<n:
    if ls[j]>=ls[i]:
        print("No")
    else:
        print("Yes")
    i += 1
    j += 1
### BUGGY CODE ###

n = input().split()
N = int(n[0])
K = int(n[1])

lista = []
listb = [1]
C = 1
A = list(map(int, input().split()))

for i in range(N):
    lista.append(int(A[i]))
                 
for j in range(20000000):
    C = lista[C-1]
    if C not in listb:
        listb.append(C)
    else:
        listb.append(C)
        break

L = len(listb) -1
                 
for i in range(L):
    if listb[i] == C:
        D = i

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[D+M])

### FIXED CODE ###

n = input().split()
N = int(n[0])
K = int(n[1])

listb = [1]
listc = [0]*N
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if listc[C-1] == 0:
        listb.append(C)
        listc[C-1] = 1
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[(D+M)%L])
### BUGGY CODE ###

def gost(lis,ky):
    
    lens=len(lis)
    
    if lens <= 5:
        
        if ky in lis:
            return True
        else:
            return False
    
    if ky <= lis[(lens//2)-1]:
        return gost(lis[:(lens//2)],ky)
    else:
        return gost(lis[(lens//2):],ky)
    

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

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


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

### FIXED CODE ###

def gost(lis,ky,r,l):
    
    lens=l-r+1
    
    if lens <= 5:
        if ky in lis[r:l+1]:
            return True
        else:
            return False
    
    if ky <= lis[r+(lens//2)-1]:
        return gost(lis,ky,r,r+(lens//2)-1)
    else:
        return gost(lis,ky,r+(lens//2),l)
    

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

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


i = 0
for it in t:
    if gost(s,it,0,n-1):
        i = i+1
print(i)
### BUGGY CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	MAX=[0]*(len(A))
	for i in range(len(A)):
		for j in range(i,len(A)+1):
			if MAX[i]<sum(A[i:j]):
				MAX[i]=sum(A[i:j])
	MAX.sort(reverse=True)
	print(MAX[0])

### FIXED CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		x=int(input())
		A.append(x)

	B=[int()]*n
	B[0]=A[0]
	for i in range(1,n):
		if A[i]>=A[i]+B[i-1]:
			B[i]=A[i]
		else:
			B[i]=A[i]+B[i-1]
	print(max(B))
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)


dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

dp[0] = [0] * (K + 1)
for i in range(N + 1):
    dp[i][0] = 0

for sum_w in range(K + 1):
    for i, (w, v) in enumerate(zip(W, V)):
        if sum_w - W[i] > -1:
            dp[i + 1][sum_w] = max(
                dp[i][sum_w],
                dp[i][sum_w - w] + v
            )
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[-1][-1])


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N =  int(sys.stdin.readline())

print(sum(x - 1 for x in range(N, 0, -1)))

### FIXED CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N =  int(sys.stdin.readline())

print((N - 1) * N // 2)
### BUGGY CODE ###

from math import floor
N = int(input())


def g(X):
    Y = floor(N / X)
    return Y * (Y + 1) * X // 2


ans = 0
for i in range(1, N + 1):
    ans += g(i)

print(ans)


### FIXED CODE ###

from math import floor
N = int(input())


def g(X):
    Y = floor(N / X)
    return Y * (Y + 1) * X // 2


ans = 0
for i in range(1, N + 1):
    ans += g(i)

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

N = int(input())
List = []
for i in range(N):
    S = input()
    List.append(S)
New_List = []
for j in List:
    if j not in New_List:
        New_List.append(j)
print(len(New_List))

### FIXED CODE ###

N = int(input())
List = []
for i in range(N):
    S = input()
    List.append(S)
print(len(set(List)))
### BUGGY CODE ###

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

def main():
    N=int(input())  #数値入力 「N」だけの入力のとき
    H=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
    D=list()
    for i in range(1, N):
        if H[i-1] >= H[i]:
            D.append(1)
        else:
            D.append(0)
    #print("D")
    #print(D)

    ans = 0
    a = 0
    for i in range(len(D)):
        a = 0
        for j in range(i, len(D)):            
            if D[j] == 1:
                a += 1
                if a > ans:
                    ans = a
            else:
                if a > ans:
                    ans = a
                break
            #print("i j")
            #print(str(i) +" "+str(j) +" "+str(ans))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
ans = 0
cnt = 0
for ind,i in enumerate(H[:-1]):
    if(i>=H[ind+1]):
        cnt += 1
    else:
        cnt = 0
    ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    if i + a[i] + 1 < n:
        for j in range(i + a[i] + 1, n):
            if j - i == a[i] + a[j]:
                count += 1
print(count)

### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (10 ** 6)
    ans = 0
    for i in range(n):
        if i - a[i] > 0:
            ans += b[i - a[i]]
        if i + a[i] < 10 ** 6:
            b[i + a[i]] += 1
    print(ans)


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

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

position = 2**(n+2)-3
result = 0
while x > 0:
    n -= 1
    if x <= (position-1)//2:
        x -= 1
    else:
        x -= (position-1)//2 + 1 
        result += (position+3)//4
    position = (position-3)//2
print(result)

### FIXED CODE ###

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

position = 2**(n+2)-3
result = 0
while x > 0:
    position = (position-1)//2
    if x == position*2+1:
        result += position + 1
        x = 0
    elif x == position+1:
        result += position//2 + 1
        x = 0
    elif x > position:
        x -= position
        result += position//2+1
    x -= 1
    position -= 1
print(result)
### BUGGY CODE ###

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
value=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        lastw=j-wv[i][0]
        if lastw>=0:
            value[i+1][j]=max(value[i][j],value[i][lastw]+wv[i][1])
        else:
            value[i+1][j]=value[i][j]

print(value[n][w])


### FIXED CODE ###


import numpy as np
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
value=np.zeros((n+1,w+1),dtype=int)
for i in range(n):
    wei=wv[i][0]
    value[i+1][:wei]=value[i][:wei]
    # np.maximum([1,-3,2],0) == [1,0,2]
    value[i+1][wei:]=np.maximum(value[i][wei:],value[i][:-wei]+wv[i][1])
# print(value)
print(value[n][w])
### BUGGY 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 a in range(N):
    for b in range(bisect.bisect_right(B,A[a]),N):
        for c in range(bisect.bisect_right(C,B[b]),N):
            ans+=1
print(ans)

### 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 b in range(N):
    a=bisect.bisect_left(A,B[b])
    c=N-bisect.bisect_right(C,B[b])
    ans+=a*c
print(ans)
### BUGGY CODE ###

import sys
import math
def sieve (n):
	ms_prime = [0,0,0,0,0,0]
	ms_prime += [1 for i in range(n-5)]
	ub = math.sqrt(n) + 1
	d = 6
	while d <= ub:
		if ms_prime[d] == 0:
			d += 1
			continue
		if d % 7 != 1 and d % 7 != 6:
			ms_prime[d] = 0
			d += 1
			continue
		prod = 2
		while d * prod <= n:
			ms_prime[d*prod] = 0
			prod += 1
		d += 1
	return ms_prime
ms_prime = sieve(300000)
while 1:
	n = int(raw_input())
	if n == 1:
		break
	sys.stdout.write("%d:" % n)
	msp_factor = set()
	for i in range(6, n+1):
		tmp_factor = 0
		if ms_prime[i] == 1 and n % i == 0 and ((n / i) % 7 == 1 or (n / i) % 7 == 6): 
			sys.stdout.write(" %d" % i)
	else :
		print ""

### FIXED CODE ###

import sys
def sieve (n):
	ms_sieve = [0,0,0,0,0,0]
	ms_sieve += [1 for i in range(n-5)]
	ms_prime = []
	d = 6
	while d <= n:
		if ms_sieve[d] == 0:
			d += 1
			continue
		if d % 7 != 1 and d % 7 != 6:
			ms_sieve[d] = 0
			d += 1
			continue
		ms_prime.append(d)
		prod = 2
		while d * prod <= n:
			ms_sieve[d*prod] = 0
			prod += 1
		d += 1
	return ms_prime
ms_prime = sieve(300000)
while 1:
	n = int(raw_input())
	if n == 1:
		break
	sys.stdout.write("%d:" % n)
	for msp in ms_prime:
		if msp > n:
			break
		quot, rem = divmod(n,msp)
		if rem != 0:
			continue 
		rem2 = quot % 7
		if rem2 == 1 or rem2 == 6: 
			sys.stdout.write(" %d" % msp)
	print ""