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

""" AtCoder """

A, B, K = map(int, input().split())

l = []
for i in range(A, B + 1):
    l.append(i)

ans = []

if B - A < K:
    ans = l
else:
    for i in range(K):
        ans.append(l[i])
        ans.append(l[-i-1])

ans = set(ans)

ans = sorted(ans)

for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

""" AtCoder """

A, B, K = map(int, input().split())

l = []
for i in range(A, A + K + 1):
    l.append(i)
for i in range(B - K, B + 1):
    l.append(i)

ans = []

if B - A < K:
    for i in range(A, B + 1):
        ans.append(i)
else:
    for i in range(A, A + K + 1):
        l.append(i)
    for i in range(B - K, B + 1):
        l.append(i)
    for i in range(K):
        ans.append(l[i])
        ans.append(l[-i-1])

ans = set(ans)

ans = sorted(ans)

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

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(1,N+1):
    B.append(A.index(i)+1)
print(*B)

### FIXED CODE ###

N=int(input())
A={i:a for (i, a) in enumerate(list(map(int, input().split())),1)}
B=sorted(A.items(), key=lambda A:A[1])
for i in range(N):
    print(B[i][0],end=" ")
### BUGGY CODE ###

import re
N = int(input())
S = input()
cnt = 0

for i in range(1000):
    str_i = '{:03}'.format(i)
    pattern = '.*'+str_i[0]+'.*'+str_i[1]+'.*'+str_i[2]
    if(re.match(pattern, S)!=None):
        cnt += 1

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(1000):
    str_i = '{:03}'.format(i)
    found = 0
    for s in S:
        if(s==str_i[found]):
            found += 1
            if(found == 3):
                cnt += 1
                break
print(cnt)
### BUGGY CODE ###

import bisect
import numpy as np
n = int(input())
a = list(map(int, input().split()))
q = int(input())
a.sort()
A = list(set(a))
CA = [0]*len(A)
for i,x in enumerate(A):
  l = bisect.bisect_left(a,x)
  r = bisect.bisect_right(a,x)
  CA[i] = r-l

def trans(A,b,c):
  for i,x in enumerate(A):
    if x == b:
      A[i] = c
  return A

A = np.array(A)
CA = np.array(CA) 
for i in range(q):
  b,c = list(map(int, input().split()))
  A = trans(A,b,c)
  ans = A * CA
  print(sum(ans))

### FIXED CODE ###

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

A = [0] * 100001
for i in a:
  A[i] += 1

ans  = 0
for i in range(len(A)):
  ans += i * A[i]  

for n in range(q):
  b,c = list(map(int, input().split()))
  ans += (c * A[b]) - (b * A[b])
  A[c] += A[b]
  A[b] = 0
  print(ans)
### BUGGY CODE ###

N = input()

S = input()
len_S = len(S)

key_list = range(0, 1000)

key_list = tuple(map(lambda key: '0' * (3 - len(str(key))) + str(key), key_list))

ans_list = []

for key in key_list:
    target_num = 0
    for s in S:
        if key[target_num] == s:
            target_num += 1
        if target_num == 3:
            ans_list.append(key)
            break

print(len(ans_list))


### FIXED CODE ###

import copy

N = input()
S = input()

key_list = range(0, 1000)
key_list = tuple(map(lambda key: '0' * (3 - len(str(key))) + str(key), key_list))

ans_list = []
for key in key_list:
    flg = True
    cS = copy.copy(S)
    for i in key:
        index = cS.find(i)
        if index == -1:
            flg = False
            break
        cS = cS[index+1:]
    if flg:
        ans_list.append(key)
        
print(len(ans_list))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
a,b,n = map(int,input().split())
li = []

for x in range(n+1):
    li.append(int((a*(x))/b) - a * int(x/b))
print(max(li))

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
 
ans1 = 0
 
if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  t = {}
  t[w] = 0
  for i in range(n):
    keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
    tw, tv = d[i]
    for j in keys:
      nw = j - tw
      if nw < 0:
        continue
      nv = t[j] + tv
      if nw in t:
        if nv > t[nw]:
          t[nw] = nv
      else:
        t[nw] = nv
  print(max(t.values()))
main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for i in range(M):
  B = A.pop()
  bisect.insort_right(A,B//2)
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(lambda x: int(x)*(-1),input().split()))
import heapq
heapq.heapify(A)
for i in range(M):
  B = heapq.heappop(A)
  heapq.heappush(A,-1*((-B)//2))
print(-sum(A))
### BUGGY CODE ###

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

for i in range(1, N+1):
    ans.append(A.index(i)+1)
print(' '.join(map(str, ans)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

for i, a in enumerate(A):
    ans[int(a-1)] = str(i+1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys

k = int(input())
result = -1
count = 0
seven = 0
remainder = 0
aryRemainder = []

if k%2 == 0:
  print(result)
  sys.exit()

while not(remainder in aryRemainder):
  aryRemainder.append(remainder)
  seven = seven*10+7
  count += 1
  remainder = seven % k
  if remainder == 0:
    result = count
    break
  

print(result)

### FIXED CODE ###

k = int(input())
cnt = 1
num = 7

if k%2 == 0 or k%5 == 0:
  print(-1)
  exit()

while 1:
  num %= k
  if num == 0:
    break
  num = num*10+7
  cnt += 1
  
print(cnt)
### BUGGY CODE ###

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

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(c, r):
    return mod_pow(fc[c] * fc[r] % m, m - 2, m)

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * rev(c, r) % m

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)

### FIXED CODE ###

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

m = 10**9 + 7

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * ic[c] * ic[r] % m

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m
ic = [pow(x, m-2, m) for x in fc]

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)
### BUGGY CODE ###

n,a,b,c,d,e=[int(input()) for i in range(6)]
dist=[n,0,0,0,0,0]
move=[a,b,c,d,e]
t=0
while dist[5]<n:
  dist[0]=max(0,dist[0]-move[0])
  dist[5]=dist[5]+min(dist[4],move[4])
  for j in range(1,5):
    dist[j]=max(0,dist[j]-move[j])+min(dist[j-1],move[j-1])
  t=t+1
print(t)
    


### FIXED CODE ###

n=int(input())
A=[int(input()) for i in range(5)]
print(5+(n-1)//min(A))
### BUGGY CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        diff=0
        #seki*=special.perm(calc,num-diff)
        for i in range(calc,calc-(num-diff),-1):
            seki*=i%1000000007
        
    else:
        calc=K-2
        diff=1
        for i in range(calc,calc-(num-diff),-1):
            seki*=i%1000000007
    #seki*=math.factorial(calc)/math.factorial(calc-(num-diff))
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%1000000007
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%1000000007)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)
### BUGGY CODE ###

n=int(input())
s=input()

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0
for i in range(n-2):
    if s[i] == "R":
        for j in range(i+1, n):
            if s[j] == "G":
                total += remain[-j-1][2]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
            elif s[j] == "B":
                total += remain[-j-1][1]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
    elif s[i] == "G":
        for j in range(i+1, n):
            if s[j] == "B":
                total += remain[-j-1][0]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
            elif s[j] == "R":
                total += remain[-j-1][2]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
    elif s[i] == "B":
        for j in range(i+1, n):

            if s[j] == "R":
                total += remain[-j-1][1]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
            elif s[j] == "G":
                total += remain[-j-1][0]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
print(total)

### FIXED CODE ###


n=int(input())
s=input()

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0

rgb="RGB"
for i in range(n-2):
    first = s[i]
    search = []
    for j in range(3):
        if j==rgb.find(first):
            continue
        else:
            search.append(j)
    total = total + (remain[-i-2][search[0]]*remain[-i-2][search[1]])
    try:
        for j in range(1,n):
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j]:
                total -= 1
    except:
        pass


print(total)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i, a in enumerate(L[:N-2]):
  for j, b in enumerate(L[i+1:N-1]):
    over_index = bisect_left(L[i+j+2:],a+b)
    ans += over_index
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):
    ans += bisect_left(L, L[i]+L[j]) - (j + 1)

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

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [set() for _ in range(n)]
visited = [False for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].add(b - 1)
    edges[b - 1].add(a - 1)

def dfs(p, v):
    if visited[v]:
        return
    visited[v] = True
    vi = list(edges[v])
    for i in vi:
        if i != p:
            dfs(v, i)
    count = 0
    for i in edges[v]:
        if i != p:
            print(v + 1, i + 1)
            edges[i].remove(v)
            count += 1
    if count % 2 == 1:
        print(v + 1, p + 1)
        edges[p].remove(v)

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i

  def comb(n,k):
    return factorial[n]//(factorial[n-k]*factorial[k])

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
    ans %= mod

  print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod
  
  def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
  ans %= mod

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

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = dic[str(now_node)]
        for tgt in target:
            if uf[tgt-1] == -1:
                q.put(tgt)
                uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(1,N+1):
    if uf[i-1] == -1:
        # 連結判定
        leng = BFS(var, dic, i)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)


### FIXED CODE ###

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)
### BUGGY CODE ###

K, S = map(int, input().split())
K = K + 1
count = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i + j + k == S:
                count += 1
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count = count + 1

print(count)
### BUGGY CODE ###

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

### FIXED CODE ###

from math import gcd

k = int(input())
sum = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            sum += gcd(c, gcd(a, b))
print(sum)
### BUGGY CODE ###

import numpy as np
#from numba import njit


#@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
from numba import njit


@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

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

def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    if (0, 0) in d:
        dp[0][0][1] = d[(0, 0)]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if x != r-1:
                    if (x+1, y) in d:
                        dp[x+1][y][1] = max(dp[x+1][y][1],
                                            dp[x][y][z]+d[(x+1, y)])
                    dp[x+1][y][0] = max(dp[x+1][y][0], dp[x][y][z])
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[x][y+1][z+1] = max(dp[x][y+1]
                                                  [z+1], dp[x][y][z]+d[(x, y+1)])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
    print(max(dp[r-1][c-1]))


main()


### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
### BUGGY CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    for j, b1 in enumerate(bitcnt(A[i])):
        b0 = (b1 + 1) % 2
        ans += pow2[j] * (a0[j] * b1 % M) % M
        ans += pow2[j] * (a1[j] * b0 % M) % M
        ans %= M
        a1[j] = (a1[j] + b1) % M
        a0[j] = (a0[j] + b0) % M

print(ans)


### FIXED CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    a = A[i]
    for j in range(60):
        b1 = a & 1
        a >>= 1
        if b1:
            ans += pow2[j] * a0[j] % M
            a1[j] += 1
        else:
            ans += pow2[j] * a1[j] % M
            a0[j] += 1
        ans %= M

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

import math
from functools import reduce

# reduce(function, iterable, initializer)
def gcd(*number):
    return reduce(math.gcd, number)

def gcd_list(number):
    return reduce(math.gcd, number)

sum = 0
K = int(input()) + 1
for i in range(1,K):
    for j in range(1,K):
        for k in range(1,K):
            sum += gcd(i, j, k)
print(sum)

### FIXED CODE ###

import math
from functools import reduce

# reduce(function, iterable, initializer)
def gcd(*number):
    return reduce(math.gcd, number)

def gcd_list(number):
    return reduce(math.gcd, number)

def main():
    sum = 0
    K = int(input())
    for i in range(1,K+1):
        for j in range(1,K+1):
            tmp = math.gcd(i, j)
            for k in range(1,K+1):
                sum += math.gcd(tmp, k)
    print(sum)

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

n=int(input())
count=0
for i in range(n):
  count=count+i
print(count)

### FIXED CODE ###

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