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

from itertools import permutations

##def permutation(lst):
##    if len(lst) < 2:
##        return[lst]
##    l = []
##    for i in range(len(lst)):
##        m = lst[i]
##        remLst = lst[:i] + lst[i+1:]
##        for p in permutation(remLst):
##            l.append([m] + p)
##    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1]*(N+1) for x in range(N+1)]

for i in range(M):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)


### FIXED CODE ###

from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
res = 0

for i in range(3, len(S)):
  last = S[i]
  for j in range(i-3):
    product = int(S[j:i+1])

    if product % 2019 == 0:
      res += 1

print(res)

### FIXED CODE ###

from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

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

import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)


### FIXED CODE ###

import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}
results[0] = (0, 0)
used = set()

while queue:
    cost, cur = queue.pop()
    if cur in used:
        continue
    used.add(cur)
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.appendleft((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
Ad = {}
for a_set in A_set:
    Ad[a_set] = A.count(a_set)

score_sum = 0
for x in list(Ad.values()):
    score_sum += (x > 1) * x * (x - 1) / 2

for a in A:
    print(int(score_sum - (Ad[a] - 1)))


### FIXED CODE ###

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

# A_set = list(set(A))
# Ad = {a_set:A.count(a_set) for a_set in A_set}
Ad = {}
for i in A:
  if not i in Ad:
    Ad[i]=0
  Ad[i] += 1

score_sum = sum([x*(x-1)/2 for x in list(Ad.values())])

for a in A:
    print(int(score_sum - (Ad[a] - 1)))
### BUGGY CODE ###

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

#S.sort(key=lambda x:x[0])
S.sort()

first = []

for tmp in S:
    if tmp[0]!=1:
        break
    first.append(tmp[1])

for tmp in S:
    if tmp[0] in first:
        if tmp[1] == N:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

### FIXED CODE ###

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

set1=set()
set2=set()

for tmp in S:
    if tmp[0]==1:
        set1.add(tmp[1])
    if tmp[1]==N:
        set2.add(tmp[0])

if len(set1&set2) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

n=int(input())
a = list(map(lambda x:format(x,'b'),map(int,input().split())))
b = list(map(len,a))

p = 10**9+7
s = 0
for i in range(max(b)):
    zero = 0
    one = 0
    for j in range(n):
        if len(a[j]) < i+1:
            zero += 1
            continue
        if a[j][-(1+i)]=='1':
            one += 1
        else:
            zero += 1
    cnt = one*zero%p
    s += (cnt*pow(2,i,p))%p

print(s%p)


### FIXED CODE ###

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

p = 10**9+7
ans = 0
for i in range(60):
    x = 1<<i
    one = sum(1 for j in a if j&x)
    ans += pow(2,i,p)*one*(n-one)

print(ans%p)
### BUGGY CODE ###

s = str(input())
t = str(input())

if set(t).issubset(set(s)):
    p = -1
    r = 0
    
    for i in t:
        p = s.find(i, p+1)
        if p == -1:
            r += 1
            p = s.find(i)
        
    print(p + 1 + len(s)*r)
    
else:
    print(-1)

### FIXED CODE ###

s = str(input())
t = str(input())

if set(t).issubset(set(s)):
    p = -1
    r = 0
    
    for i in t:
        p = s.find(i, p+1)
        if p == -1:
            r += 1
            p = s.find(i)
        
    print(p + 1 + len(s)*r)
    
else:
    print(-1)
### BUGGY CODE ###

k = int(input())
x = 7%k
s = set()
i = 1
while list(s).count(x) == 0:
  if x == 0:
    print(i)
    exit()
  s.add(x)
  x = (x*10+7)%k
  i += 1
print(-1)


### FIXED CODE ###

k = int(input())
x = 7%k
s = set()
#i = 1
#while len(s) == 0:
for i in range(1, k+1):
  if x == 0:
    print(i)
    exit()
  #s.add(x)
  x = (x*10+7)%k
  #i += 1
print(-1)
### BUGGY CODE ###

A = int(input())
L = map(int,input().split())

res = 1

for n in L:
    res *= n

if res > 10**18:
    res = -1
print(res)

### FIXED CODE ###

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

if 0 in L:
    print(0)
    exit()

res = 1

for n in L:
    res *= n
    if res > 10**18:
        print(-1)
        exit()
    
print(res)
### BUGGY CODE ###

from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
lcm=A[0]
for i in range(1,N):
    lcm=lcm*A[i]//(gcd(lcm,A[i]))

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


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    input=sys.stdin.readline
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for a in A:
        lcm=lcm*a//(gcd(lcm,a))

    ans=0
    for a in A:
        ans=ans+(lcm//a)
    print(ans%(10**9+7))

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

h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(input())

u = [[0 for i in range(w)] for j in range(h)]
d = [[0 for i in range(w)] for j in range(h)]
l = [[0 for i in range(w)] for j in range(h)]
r = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            u[i][j] = 0
        else:
            if i == 0:
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            l[i][j] = 0
        else:
            if j == 0:
                l[i][j] = 1
            else:
                l[i][j] = l[i][j-1] + 1

for i in range(h-1,-1,-1):
    for j in range(w):
        if s[i][j] == "#":
            d[i][j] = 0
        else:
            if i == h-1:
                d[i][j] = 1
            else:
                d[i][j] = d[i+1][j] + 1

for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j] == "#":
            r[i][j] = 0
        else:
            if j == w-1:
                r[i][j] = 1
            else:
                r[i][j] = r[i][j+1] + 1

s = [[0 for i in range(w)] for j in range(h)] 
maxs = 0
for i in range(h):
    for j in range(w):
        s[i][j] = u[i][j] + l[i][j] + d[i][j] + r[i][j] - 3
        maxs = max(maxs,s[i][j])

print(maxs)

### FIXED CODE ###



h,w = map(int,input().split())
s = []
for i in range(h):
    s.append(input())

u = [[0 for i in range(w)] for j in range(h)]
d = [[0 for i in range(w)] for j in range(h)]
l = [[0 for i in range(w)] for j in range(h)]
r = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            u[i][j] = 0
        else:
            if i == 0:
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            l[i][j] = 0
        else:
            if j == 0:
                l[i][j] = 1
            else:
                l[i][j] = l[i][j-1] + 1

for i in range(h-1,-1,-1):
    for j in range(w):
        if s[i][j] == "#":
            d[i][j] = 0
        else:
            if i == h-1:
                d[i][j] = 1
            else:
                d[i][j] = d[i+1][j] + 1

for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j] == "#":
            r[i][j] = 0
        else:
            if j == w-1:
                r[i][j] = 1
            else:
                r[i][j] = r[i][j+1] + 1

s = [[0 for i in range(w)] for j in range(h)] 
maxs = 0
for i in range(h):
    for j in range(w):
        s[i][j] = u[i][j] + l[i][j] + d[i][j] + r[i][j] - 3
        maxs = max(maxs,s[i][j])
print(maxs)
### BUGGY CODE ###

k = int(input())
a = list(map(int, input().split()))
l, r = 0, 10 ** 100
while r - l > 1:
    m = (l + r) // 2
    t = m
    for x in a:
        m = m // x * x
    if m <= 2:
        l = t
    else:
        r = t
l2, r2 = 0, 10 ** 100
while r2 - l2 > 1:
    m = (l2 + r2) // 2
    t = m
    for x in a:
        m = m // x * x
    if m < 2:
        l2 = t
    else:
        r2 = t
if l < r2:
    print(-1)
else:
    print(r2, l)


### FIXED CODE ###

k = int(input())
a = list(map(int, input().split()))
l, r = 0, 10 ** 15
while r - l > 1:
    m = (l + r) // 2
    t = m
    for x in a:
        m = m // x * x
    if m <= 2:
        l = t
    else:
        r = t
l2, r2 = 0, 10 ** 15
while r2 - l2 > 1:
    m = (l2 + r2) // 2
    t = m
    for x in a:
        m = m // x * x
    if m < 2:
        l2 = t
    else:
        r2 = t
if l < r2:
    print(-1)
else:
    print(r2, l)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


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


visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]


INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))


### FIXED CODE ###

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

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))
### BUGGY CODE ###

a, b, n = map(int, input().split())
p = 10**9+7
ans = 0
for x in range(n+1):
 c = (int((a*x)%p/b))%p
 d = (int(x/b))%p
 e = (c - a*d)%p
 ans = max(ans, e)
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
c = min(b-1, n)
print(int(a*c/b))
### BUGGY CODE ###

import queue
N, Q = map(int, input().split())

edges = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

points = [0]*N
PX = [list(map(int, input().split())) for _ in range(Q)]
for px in PX:
    points[px[0]-1] += px[1]

res = [0]*N
res[0] = points[0]

color = [0]*N
color[0] = 1

#print(edges)
#print(points)
#print(color)
#print(res)

q = queue.Queue()
q.put(0)

while not q.empty():
    current_node = q.get() # 0
#    print(' current:', current_node)
    children_nodes = edges[current_node]
    for node in children_nodes:
        if color[node] == 1: continue
        color[node] = 1
        points[node] += points[current_node]
        q.put(node)
#        print('  color', color)
print(*points)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for a in A:
  B = []
  for b in A:
    B.append(a%b)
  if B.count(0) == 1:
    count += 1
print(count)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)
### BUGGY CODE ###

a, b, k= map(int, input().split())
for i in range(a, b+1):
    if i < a+k or b-i+1 <= k:
        print(i)    


### FIXED CODE ###

a, b, k= map(int, input().split())
if a+k >= b-k:
    for i in range(a, b+1):
        if i < a+k or b-i+1 <= k:
            print(i)
else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def checkABC(x):
    if s[x]=='A' and s[x+1]=='B' and s[x+2]=='C':
        s[x],s[x+1],s[x+2]='B','C','A'
        return True
    else:
        return False

def main():
    global s
    s=list(input())
    N=len(s)
    i=0
    ans=0
    while True:
        if i >= N-2:
            break
        if checkABC(i) == True:
            i=min(i-2,-1)
            ans+=1
        i+=1
    print(ans)
        
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    s=input()
    s2=list(s.replace('BC','D'))
    N=len(s2)
    ans=0
    c=0
    for i in range(N):
        if s2[i]=='A':
            c+=1
        elif c!=0 and s2[i]=='D':
            ans+=c
        else:
            c=0
    print(ans)

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

N=int(input())
import numpy as np
A=np.zeros(N,dtype=int)
B=np.zeros(N,dtype=int)
for i in range(N):
  a,b=map(int,input().split())
  A[i]=a
  B[i]=b

ans=0

for i in range(N-1,-1,-1):
  plus=0
  if B[i]==1:
    plus=0
  elif A[i]<B[i]:
    plus=B[i]%A[i]
  elif A[i]>B[i]:
    plus=B[i]-A[i]%B[i]
  ans+=plus
  A[:i+1]=A[:i+1]+plus
  
print(ans)

### FIXED CODE ###

n=int(input())
a=[0]*n
b=[0]*n
for i in range(n):
  x,y=map(int,input().split())
  a[i]=x
  b[i]=y

cur=0
for j in range(n-1,-1,-1):
  if (a[j]+cur)%b[j]!=0:
    cur+=b[j]-(a[j]+cur)%b[j]

print(cur)
### BUGGY CODE ###

N,K = list(map(int,input().rstrip().split()))
A = list(map(int,input().rstrip().split()))
sum =0
while len(A)>=2:
    sum+=1
    A.insert(0,min(A[:K]))
    del A[0:K]
print(sum)

### FIXED CODE ###

import math
N,K = map(int,input().rstrip().split())
print(math.ceil((N-1)/(K-1)))
### BUGGY CODE ###

#!python3.8
# -*- coding: utf-8 -*-
# abc174/abc174_c
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    K = i2n()

    #while K % 7 == 0:
    #    K = K // 7
    x = 10 % K
    a = 0
    for i in range(1, K + 10):
        a = a * 10 + 7
        if a % K == 0:
            print(i)
            return
    else:
        print('-1')
    return

main()


### FIXED CODE ###

#!python3.8
# -*- coding: utf-8 -*-
# abc174/abc174_c
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    K = i2n()
    a = 0
    if K % 7:
        L = 9 * K
    else:
        L = 9 * K // 7
    a = 1
    for i in range(1, K + 10):
        a = (a * 10) % L
        if a == 1:
            print(i)
            return
    print('-1')
    return
 
main()
### BUGGY CODE ###

k,s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)


### FIXED CODE ###

k,s = map(int, input().split())
ans = 0
for p in range(min(k+1,s+1)):
    for q in range(p, s+1):
        if q-p > k or s - q > k:
            continue
        else:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    neighbor[x-1].append(y-1)
    neighbor[y-1].append(x-1)

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1] += y-1,
    neighbor[y-1] += x-1,

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)
### BUGGY CODE ###

def solve(n, m, s, t):
    dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    ans = ''
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            ans = s[n - 1] + ans
            n -= 1
            m -= 1
    print(ans)
    return

s = input()
t = input()

solve(len(s), len(t), s, t)

### FIXED CODE ###

def solve(n, m, s, t):
    dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    ans = ''
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            ans = s[n - 1] + ans
            n -= 1
            m -= 1
    print(ans)
    return

s = input()
t = input()

solve(len(s), len(t), s, t)
### BUGGY CODE ###

n = int(input())
p = []
#p.append(n)

for i in range(2, n+1):
    p.append(i)
p.append(1)

#print(p)
ans = 0

for i in range(1, n+1):
    # print("\n #i: " + str(i))
    # print("#p[i-1]: " + str(p[i-1]))
#    print(i % p[i-1])
    ans += i % p[i-1]

print(ans)


### FIXED CODE ###

import sys

n = int(input())

if n == 2:
    print(1)
    sys.exit()

# temp1 = (n-1) // 2
# temp2 = 2 + n - 2
#ans = ((n-1) / 2) * (2 + (n - 2))
ans = (n-1) * (2 + (n - 2))
ans = ans // 2
#ans = temp1 * temp2

#print(ans)
print(int(ans))