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

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans=1
n=int(f.readline().strip())
prime=[]
# Start from where n is equal to 2
for _ in range(1,n):
    number_of_multiply=[]
    num_of_divisor=1
    tmp=_+1
    for __ in prime:
        cnt=0
        if tmp<=1:
            break
        while (tmp%__)==0:
            cnt+=1;tmp=tmp//__;
        if cnt>0:
            num_of_divisor*=cnt+1
    if num_of_divisor==1:
        prime.append(_+1)
        ans+=(_+1)*2
    else:
        ans+=(_+1)*num_of_divisor
print(ans)

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans_sum=0
n=int(f.readline().strip())
for _ in range(1,n+1):
    num=n//_
    ans_sum+=_*((num*(num+1))//2)
print(ans_sum)
### BUGGY CODE ###

from sys import stdin, stdout
def knapsack(weights,values,capacity,n,memo):
    if(memo[n][capacity]!=-1):
        return memo[n][capacity]
    if(n==0 or capacity==0):
        return 0
    val=0
    if(weights[n-1]<=capacity):
        memo[n][capacity]=max(values[n-1]+knapsack(weights,values,capacity-weights[n-1],n-1,memo),knapsack(weights,values,capacity,n-1,memo))
        return memo[n][capacity]
    memo[n][capacity]=knapsack(weights,values,capacity,n-1,memo)
    return memo[n][capacity]

n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
memo=[[-1]*(capacity+1) for i in range(n+1)]
stdout.write(str(knapsack(weights,values,capacity,n,memo)))

### FIXED CODE ###

# from sys import stdin, stdout
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,capacity+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k] and j-i != k-j:
                ans += 1
print(ans)


### FIXED CODE ###

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

U = S.count('R') * S.count('G') * S.count('B')

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if k >= N:
            break
        elif S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            U -= 1
print(U)
### BUGGY CODE ###

N,P=map(int,input().split())
ans=1
for i in range(2,round(P**(1/N))+1):
    if P%(i**N)==0:
        ans=i
print(ans)

### FIXED CODE ###

N,P=map(int,input().split())
ans=1
pf={}
if N==1:
    print(P)
else:
    M=P
    for p in range(2,round(M**0.5)+1):
        pf[p]=0
        while P%p==0:
            P//=p
            pf[p]+=1
        if P==1:
            break
    for p in pf:
        if pf[p]>=N:
            ans*=p**(pf[p]//N)
    print(ans)
### BUGGY CODE ###

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

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))


### FIXED CODE ###

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

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
C = []
Q = deque()
dist = [[-1]*W for i in range(H)]

for i in range(H):
  s = list(input())
  yxidx = [(i,x) for x,v in enumerate(s) if v == "#"]
  for (y, x) in yxidx:
    Q.append((y,x))
    dist[y][x] = 0
  C.append(s)
X = [1,0,-1,0]
Y = [0,-1,0,1]


while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dist[ny][nx] == -1):
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

from collections import deque
from sys import exit

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        break

max_books = 0
for a_count, a in enumerate(a_book):
    for b_count, b in enumerate(b_book):
        if a + b <= K:
            max_books = max(max_books, a_count+b_count)

print(max_books)


### FIXED CODE ###

from bisect import bisect_right
from time import time

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        N = index - 1
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        M = index - 1
        break

check = {}

max_books = 0

for i, a in enumerate(a_book):
    b_pos = bisect_right(b_book, K - a)

    if max_books < b_pos - 1 + i:
        max_books = b_pos - 1 + i

print(max_books)
### BUGGY CODE ###

import itertools

n, m = map(int, input().split())
d = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d.append((a - 1, b - 1, c))

wf = [[float('inf')] * n for _ in range(n)]
for a, b, c in d:
    wf[a][b] = wf[b][a] = c
for i in range(n):
    wf[i][i] = 0

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for a, b, c in d:
    used = False
    for i, j in itertools.product(range(n), repeat=2):
        if wf[i][a] + c + wf[b][j] == wf[i][j] or wf[i][b] + c + wf[a][j] == wf[i][j]:
            used = True
    
    if not used:
        ans += 1

print(ans)

### FIXED CODE ###

import itertools

n, m = map(int, input().split())
d = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d.append((a - 1, b - 1, c))

wf = [[float('inf')] * n for _ in range(n)]
for a, b, c in d:
    wf[a][b] = wf[b][a] = c
for i in range(n):
    wf[i][i] = 0

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for a, b, c in d:
    used = False
    for i in range(n):
        for j in range(i + 1, n):
            if wf[i][a] + c + wf[b][j] == wf[i][j] \
                    or wf[i][b] + c + wf[a][j] == wf[i][j] \
                    or wf[j][a] + c + wf[b][i] == wf[j][i] \
                    or wf[j][b] + c + wf[a][i] == wf[j][i]:
                used = True
            
    if not used:
        ans += 1

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

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input()))) 
    tmp.append(new_str)
    counter += tmp.count(new_str)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1

print(counter-len(tmp))

### FIXED CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input())))
    
    #if i != 0:
    #    counter += tmp.count(new_str)
    tmp.append(new_str)

import collections
c = collections.Counter(tmp)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1
value = list(c.values())
#print(value)

for j in value:
    for k in range(j):
        counter += k

print(counter)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
for i in range(N):
    temp = a[0:i] + a[i + 1:]
    print(max(temp))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
max_A = max(A)
max_num = 0
for i in range(N):
    if A[i] == max_A:
        # 最大値が複数ある場合の計算削減
        max_num += 1
        if max_num > 1:
            print(max_A)
        else:
            print(max(A[:i] + A[i + 1:]))
    else:
        print(max_A)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx]+S[sidx+1] == 'AC':
        ACs.append(sidx)

#  print(ACs)
#  LR = []
#  for i in range(Q):
#      LR.append(LI())
#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for _ in range(Q):
    l,r = LI()
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    res = len(ACs[start:end])
    result.append(res)
for i in result:
    print(i)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(end-start)
### BUGGY CODE ###

n = int(input())
ans = 0

def gcd(a,b):
    if a % b == 0:
      return b
    return gcd(b, a%b)

for i in range(1, n+1):
    for j in range(1, n+1):
        x = gcd(i, j)
        for k in range(1, n+1):
            ans += gcd(x, k)
print(ans)


### FIXED CODE ###

import math
k = int(input())
a = []
for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            y = math.gcd(l, x)
            a.append(y)
print(sum(a))
### BUGGY CODE ###

import math
def anahist(str1):
    dic = {}
    while str1 != '':
        s = str1[0]
        dic[s] = str1.count(s)
        str1 = str1.replace(s,'')
    return dic

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


N = int(input())
lsdic = []
ii = 0
for i in range(N):
    s1 = str(input())
    dic1 = anahist(s1)
    lsdic.append(dic1)
countls = []
while lsdic != []:
    dic2 = lsdic[0]
    countls.append(lsdic.count(dic2))
    while dic2 in lsdic:
        lsdic.remove(dic2)

count = 0
for i in countls:
    if i == 1:
        count += 0
    else:
        count += combinations_count(i, 2)
print(count)

### FIXED CODE ###

import collections
N = int(input())
lsS = []
for i in range(N):
    lsS.append(''.join(sorted(input())))

counter = collections.Counter(lsS)
n=0
for i in counter.values():
    n+= (i*(i-1))//2
print(n)
### BUGGY CODE ###

from collections import deque
h, w, k = map(int, input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*w for j in range(h)]
for i in range(h):
    if 'S' in maze[i]:
        sy, sx = i, maze[i].index('S')
queue = deque([[sy, sx]])
visited[sy][sx] = 0
r = 10**18
while queue:
    y, x = queue.popleft()
    r = min(r, y, x, h-1-y, w-1-x)
    if visited[y][x] == k: continue
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+i, x+j
        if new_y < 0 or new_y >= h: continue
        if new_x < 0 or new_x >= w: continue
        if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            visited[new_y][new_x] = visited[y][x] + 1
            queue.append([new_y, new_x])
print(1 -(-r // k))

### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*w for j in range(h)]
for i in range(h):
    if 'S' in maze[i]:
        sy, sx = i, maze[i].index('S')
queue = deque([[sy, sx]])
visited[sy][sx] = 0
r = 10**18
while queue:
    y, x = queue.popleft()
    r = min(r, y, x, h-1-y, w-1-x)
    if visited[y][x] == k: continue
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+i, x+j
        if new_y < 0 or new_y >= h: continue
        if new_x < 0 or new_x >= w: continue
        if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            visited[new_y][new_x] = visited[y][x] + 1
            queue.append([new_y, new_x])
print(1 -(-r // k))
### BUGGY CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=1<<~-k
for i in r(min(n-1,k)):a-=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)

### FIXED CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=0
for i in r(n-1,k):a+=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
while True:
  t = b&(-b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  #print(i,t,b)
  if (s+1)//2 <= t.bit_length()-1 <= s:
    print(t.bit_length()-1)
    break
  b ^= t
### BUGGY CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    a = top = g[input()]
    i = 1
    while a != 0:
        print(i)
        a = g[input()]
        if a != top:
            i *= 2
        else:
            l = i //2 + 1
            r = i
            while a != 0 and a != top:
                print((l+r)//2)
                a = g[input()]




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

N = int(input())
a = [int(i) for i in input().split()] 
num = 0
j = 0
while j < N:
    c = 0
    k = j 
    while k < N:
        c = c + a[k]
        if c == 0:
            num = num+1
        k = k+1
    j = j+1
print(num)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()] 
b =[0]*(N+1)
for i in range(N):
    b[i+1]= b[i] + a[i]
b.sort()
j = 0
num = 0
v = 0
while j < N:
    if b[j+1] == b[j]:
        v = v+1
    else:
        num = num + (v*(v+1))//2
        v = 0
    j = j +1
num = num + (v*(v+1))//2
print(num)
### BUGGY CODE ###

def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    nx = max(A, max(X)) * N
    dp = [[[0 for _ in [0] * (nx + 1)] for _ in [0] * (N + 1)] for _ in [0] * (N + 1)]

    for i in range(N + 1):
        for j in range(N + 1):
            for k in range(nx + 1):
                if j == 0 and k == 0:
                    dp[i][j][k] = 1
                elif i >= 1 and k < X[i-1]:
                    dp[i][j][k] = dp[i-1][j][k]
                elif i >= 1 and j >= 1 and k >= X[i-1]:
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

    ans = 0
    for k in range(1, N + 1):
        ans += dp[N][k][k*A]
    print(ans)

main()


### FIXED CODE ###

def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    x = [i - A for i in X]
    nx = max(X) * N
    dp = [[0] * (2 * nx + 1) for _ in [0] * (N + 1)]
    for i in range(N + 1):
        for j in range(2 * nx + 1):
            if not i:
                if j == nx:
                    dp[i][j] = 1
            elif j - x[i-1] < 0 or j - x[i-1] > 2 * nx:
                dp[i][j] = dp[i-1][j]
            elif 0 <= j - x[i-1] <= 2 * nx:
                dp[i][j] = dp[i-1][j] + dp[i-1][j - x[i-1]]
    print(dp[N][nx] - 1)

main()
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i]-=1
#print(P)
C = list(map(int,input().split()))
Flag = True
for c in C:
  if c >= 0:
    Flag = False
    break
if Flag:
  print(max(C))
  exit()
L = []
for i in range(N):
  visited = set([])
  now = i
  temp = []
  while now not in visited:
    nxt = P[now]
    visited.add(now)
    temp.append(C[nxt])
    now = nxt
  L.append(temp)
#print(L)
ans = 0
S = []
for X in L:
  start = [0]
  for i in range(len(X)):
    temp = start[-1]+X[i]
    start.append(temp)
  S.append(start)
#print(S)
for X,SS in zip(L,S):
  n = len(X)
  cycle_sum = SS[-1]
  if K <= n:
    kouho = max(SS[:K+1])
  elif cycle_sum < 0:
    kouho = max(SS)
  else:
    amari = K%n
    loop = K//n
    first = 0 #余りよりも後で最大
    second = 0 #余りよりも前で最大
    first = (loop-1)*cycle_sum + max(SS)
    second = loop*cycle_sum + max(SS[:amari+1])
    kouho = max(first,second)
  ans = max(ans,kouho)
print(ans)
  
    
  


### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i]-=1
#print(P)
C = list(map(int,input().split()))
Flag = True
for c in C:
  if c >= 0:
    Flag = False
    break
if Flag:
  print(max(C))
  exit()
L = []
for i in range(N):
  visited = set([])
  now = i
  temp = []
  while now not in visited:
    nxt = P[now]
    visited.add(now)
    temp.append(C[nxt])
    now = nxt
  L.append(temp)
#print(L)
ans = 0
S = []
for X in L:
  start = [0]
  for i in range(len(X)):
    temp = start[-1]+X[i]
    start.append(temp)
  S.append(start)
#print(S)
for X,SS in zip(L,S):
  n = len(X)
  cycle_sum = SS[-1]
  if K <= n:
    kouho = max(SS[:K+1])
  elif cycle_sum < 0:
    kouho = max(SS)
  else:
    amari = K%n
    loop = K//n
    first = 0 #余りよりも後で最大
    second = 0 #余りよりも前で最大
    first = (loop-1)*cycle_sum + max(SS)
    second = loop*cycle_sum + max(SS[:amari+1])
    kouho = max(first,second)
  ans = max(ans,kouho)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

    LCM = lcm(*A)
    MOD = 10 ** 9 + 7
    ans = 0
    for i in range(N):
        ans = (ans + LCM // A[i]) % MOD
    print(ans)

if __name__ == '__main__':
    main()




### FIXED CODE ###

import math
from functools import reduce
from collections import defaultdict

#素因数分解O(√n)
def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] += 1
    return res

    

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

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

MOD = 10**9+7
GCD = gcd(*A)

P = defaultdict(lambda: 0)

for i in range(N):
    factors = primeFactor(A[i])
    for k, v in factors.items():
        if v > P[k]:
            P[k] = v


P_mod = 1
for k in P.keys():
    P_mod = P_mod*(k**P[k])%MOD

ans = 0
for i in range(N):
    b = A[i]
    mod_inv = pow(b, MOD-2, MOD)
    ans = (ans + P_mod * mod_inv) % MOD

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

input()
aa = list(map(int, input().split()))
uu = list(set(aa))
cc = []
for u in list(uu):
    cc += [aa.count(u)]
dic = dict(zip(uu,cc))
total = 0
for v in list(cc):
    total += v * (v-1) / 2

#if aa.ndim == 0:
#    aa = [aa]    
    
for a in aa:
    print(int(total - dic[a] + 1))

### FIXED CODE ###

input()
from collections import Counter
aa = list(map(int, input().split()))
dic = Counter(aa)

total = 0
for v in dic.values():
    total += v * (v-1) / 2

for a in aa:
    print(int(total - dic[a] + 1))
### BUGGY CODE ###

n = int(input())
a = [x+1 for x in range(n)]
b = [x+1 for x in range(1,n)]+[1]
ans = 0
for x,y in zip(a,b):
    ans += x%y
    
print(ans)

### FIXED CODE ###

n = int(input())
print((n*(n-1)//2))