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

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  dp=[[[0]*4 for j in range(w)] for i in range(h)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[r-1][c-1][0]=v
  if dp[0][0][0]!=0:
    dp[0][0][1]=dp[0][0][0]
    dp[0][0][0]=0
  for y in range(h):
    for x in range(w):
      v=dp[y][x][0]
      dp[y][x][0]=0
      for i in range(4):
        if 0<x:
          if dp[y][x][i]<dp[y][x-1][i]:
            dp[y][x][i]=dp[y][x-1][i]
          if 0<i and v!=0 and dp[y][x][i]<dp[y][x-1][i-1]+v:
            dp[y][x][i]=dp[y][x-1][i-1]+v
        if 0<y:
          if dp[y][x][0]<dp[y-1][x][i]:
            dp[y][x][0]=dp[y-1][x][i]
          if v!=0 and dp[y][x][1]<dp[y-1][x][i]+v:
            dp[y][x][1]=dp[y-1][x][i]+v
  print(max(dp[h-1][w-1]))
main()

### FIXED CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  H=range(h)
  W=range(w)
  dp=[[[0]*w for j in H] for i in range(4)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[0][r-1][c-1]=v
  if dp[0][0][0]!=0:
    dp[1][0][0]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[0][y][x]
      dp[0][y][x]=0
      for i in range(4):
        if 0<x:
          if dp[i][y][x]<dp[i][y][x-1]:
            dp[i][y][x]=dp[i][y][x-1]
          if 0<i and v!=0 and dp[i][y][x]<dp[i-1][y][x-1]+v:
            dp[i][y][x]=dp[i-1][y][x-1]+v
        if 0<y:
          if dp[0][y][x]<dp[i][y-1][x]:
            dp[0][y][x]=dp[i][y-1][x]
          if v!=0 and dp[1][y][x]<dp[i][y-1][x]+v:
            dp[1][y][x]=dp[i][y-1][x]+v
  print(max([dp[i][h-1][w-1] for i in range(4)]))
main()
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)
n=i1()
s=i2()
m=10**9+1
import heapq
import bisect
s.sort()
x=[s[-1]]
s[-1]=m
a="Yes"
for i in range(n):
 y=[]
 for j in range(1<<i):
   s.sort()
   z=bisect.bisect_left(s,x[j])-1
   if z<0:
     a="No"
   y.append(s[z])
   s[z]=m
 x+=y
 x.sort(reverse=True)
print(a)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
s=i2()
m=10**9+1
s.sort(reverse=True)
x=[s[0]]
s[0]=m
a="Yes"
for i in range(n):
 y=[]
 k=0
 for j in range(len(s)):
   if k>=len(x):
      break
   if s[j]<x[k]:
     y.append(s[j])
     s[j]=m
     k+=1
 x+=y
 x.sort(reverse=True)
if k==(1<<(n-1)):
   print("Yes")
else:
   print("No")
### BUGGY CODE ###

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

r=[]
g=[]
b=[]

for i in range(n):
    if s[i]=="R":
        r.append(i+1)
    elif s[i]=="G":
        g.append(i+1)
    else:
        b.append(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in r:
    for ig in g:
        if (ir+ig)/2 in b: 
            isum=isum+1
for ir in r:
    for ib in b:
        if (ir+ib)/2  in g: 
            isum=isum+1
for ig in g:
    for ib in b:
        if (ig+ib)/2  in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)


### FIXED CODE ###

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

r=set()
g=set()
b=set()

for i in range(n):
    if s[i]=="R":
        r.add(i+1)
    elif s[i]=="G":
        g.add(i+1)
    else:
        b.add(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in r:
    for ig in g:
        if (ir+ig)/2 in b: 
            isum=isum+1
for ir in r:
    for ib in b:
        if (ir+ib)/2  in g: 
            isum=isum+1
for ig in g:
    for ib in b:
        if (ig+ib)/2  in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)
### BUGGY CODE ###

import math
import sys
N=int(input())
a=sys.stdin.readline().split()
A=[int(b) for b in a]
numbers=[0]*N
for a in range(1,N+1):
    kosuu=A.count(a)
    if kosuu<=1:
        pass
    else:
        numbers.insert(a-1,kosuu)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
answers=[0]*N
for a in range(1,N+1):
    if numbers[a-1]>=2:
        b=combinations_count(numbers[a-1],2)
        answers[a-1]+=b
kotae=sum(answers)
for a in range(N):
    z=A[a]
    if kotae==0:
        print(0)
    else:
        answer=kotae-numbers[z-1]+1
        print(answer)


### FIXED CODE ###

import math
import sys
from collections import Counter
N=int(input())
a=sys.stdin.readline().split()
A=[int(b) for b in a]
numbers=[0]*N
count=Counter(A)
kotae=0
for a in range(N+1):
    b=count[a]
    kotae+=b*(b-1)//2
for a in A:
    print(kotae+1-count[a])
### BUGGY CODE ###

from collections import deque

N=int(input())
out=[set() for i in range(N+1)]
reached=[False for i in range(N+1)]
same=[[False for j in range(N+1)] for i in range(N+1)]

for i in range(N-1):
    u,v,w=map(int,input().split())
    out[u].add(v)
    out[v].add(u)
    same[u][v]=same[v][u]=w%2==0

q=deque()
q.append(1)
reached[1]=True
same1=[False for i in range(N+1)];same1[1]=True

while q:
    u=q.popleft()
    for v in [v for v in out[u] if not reached[v]]:
        same1[v]=same1[u]==same[u][v]
        reached[v]=True
        q.append(v)

for i in range(1,N+1):
    print(0 if same1[i] else 1)

### FIXED CODE ###

from collections import deque

N=int(input())
a=[set() for v in range(N)] # 0-initial
for e in range(1,N):
    u,v,w=map(int,input().split())
    a[u-1].add((v-1,w))
    a[v-1].add((u-1,w))

d=[-1 for v in range(N)] # distance from 0

q=deque()
q.append(0);d[0]=0
while q:
    u=q.popleft()
    for v,w in a[u]:
        if d[v]==-1:
            d[v]=d[u]+w
            q.append(v)

for di in d:
    print(di%2)
### BUGGY CODE ###

N = int(input())
 
l = []
for _ in range(N):
  a = int(input())
  if a in l:
    l.pop(l.index(a))
  else:
    l.append(a)

print(len(l))

### FIXED CODE ###

from collections import defaultdict

N = int(input())

dic = defaultdict(bool)
for _ in range(N):
  a = int(input())
  dic[a] = not dic[a]

print(sum(dic.values()))
### BUGGY CODE ###

#互いに素なa,bについて、a*x+b*y=1の一つの解
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def mod_inv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

import fractions
mod = (10**9)+ 7
n = int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(n):
    gcd =fractions.gcd(lcm, a[i])
    lcm *= a[i]
    lcm = lcm // gcd

ans = 0
for i in range(n):
    k = mod_inv(a[i], mod)
    ans += lcm * k
    ans %= mod
print(ans)

### FIXED CODE ###

#互いに素なa,bについて、a*x+b*y=1の一つの解
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def mod_inv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

import fractions
mod = (10**9)+ 7
n = int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(n):
    gcd = fractions.gcd(lcm, a[i])
    lcm *= a[i]
    lcm = lcm // gcd
lcm %= mod
ans = 0
for i in range(n):
    k = mod_inv(a[i], mod)
    ans += lcm * k
    ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

num_count = {i: A.count(i) for i in set(A)}
ans = 0

for i in num_count.values():
    if i % 2 == 1:
        ans += 1
        
print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = defaultdict(int)

for _ in range(N):
    a = int(input())
    if A[a] == 1:
        A[a] = 0
    else:
        A[a] = 1
        
print(sum(A.values()))
### BUGGY CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[0]*2019
flg2=[0]*2019
for i in range(L,R):
    idx=i%2019
    if flg[idx]==0:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if flg2[mod]==1:
                break
            flg2[mod]=1
            if min_mod > mod:
                min_mod=mod
        flg[idx]=1
print(min_mod)

### FIXED CODE ###

L, R = map(int, input().split())
min_mod = 2019
flg=[0]*2019
flg2=[0]*2019
for i in range(L,R):
    idx=i%2019
    if flg[idx]==1:
        break
    if flg[idx]==0:
        for j in range(i+1,R+1):
            mod  = (i*j)%2019
            if flg2[mod]==1:
                break
            flg2[mod]=1
            if min_mod > mod:
                min_mod=mod
        flg[idx]=1
print(min_mod)
### BUGGY CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [int(i) for i in input().split()]
    
    for i in range(1,10000000002):
        if i ==10000000001:
            print(-1)
            break
        if a[0]*i %a[1] >0:
            print(a[0]*i)



### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

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

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    for i in range(1,100000002):
        if a[0] % a[1]==0:
            print(-1)
            break

        if i ==10**9+1:
            print(-1)
            break
        if a[0]*i %a[1] >0:
            print(a[0]*i)
            break
        if a[0]*i >10**18 +1:
            print(-1)
            break
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
import bisect
ans = 0
for i in a:
    comb = 1
    index = bisect.bisect_right(b,i)
    for j in b[index:]:
        ans += n-bisect.bisect_right(c,j)
print(ans)

### FIXED CODE ###

n = int(input())
a,b,c = [sorted(list(map(int,input().split())),reverse=True) for i in range(3)]
comp1 = []
i,j = 0,0
cnt = 0
while i<n:
    while j<n and b[j]>a[i]:
        cnt+=1
        j+=1
    comp1.append(cnt)
    i+=1
comp2 = []
i,j = 0,0
cnt = 0
while i<n:
    while j<n and c[j]>b[i]:
        cnt+=1
        j+=1
    comp2.append(cnt)
    i+=1
x = [0]
for i in range(n):
    x.append(x[i]+comp2[i])
ans = 0
for i in comp1:
    ans += x[i]
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 10**18
ans = 1
for i in range(n):
    if 0 in a:
        print(0)
        exit()
    elif ans > x:
        print(-1)
        exit()
    ans = ans * a[i]

print(-1 if ans > x else ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 10**18
ans = 1

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

for i in range(n):
    ans = ans * a[i]
    if ans > x:
        print(-1)
        exit()

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

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)

count = 0
for l in S_li:
    while True:
        a = l.find('0')
        bc = l.rfind('1')
        if 0 <= a < bc:
            count += (bc-a)
            l = l[a+1:bc]
        else:
            break

print(str(count))

### FIXED CODE ###

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)
 
count = 0
for l in S_li:
    a = sum([i for i,x in enumerate(l) if '1' in x])
    su=sum([x for x in range(l.count('1'))])
    count += (a-su)
print(str(count))
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
A = np.array(list((map(int, input().split()))))
for _ in range(m):
    A.sort()
    A[-1] = A[-1] // 2
print(sum(A))

### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
A = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(A)
for _ in range(m):
    tmp = heapq.heappop(A)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(A, tmp)
print(-sum(A))
### BUGGY CODE ###

a=int(input())
sum=0
while(a>0):
  t=a%10
  sum=sum+t
  a=a//10
if(sum%9==0):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

a=input()
sum=0
for digit in str(a):
    sum=sum+int(digit)
if(sum%9==0):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
    exit()

x = 7 % K
i = 1
while True:
    if x == 0:
        print(i)
        exit()
    y = (x * 10 + 7) % K
    if x == y:
        print(-1)
        exit()
    x = y
    i += 1


### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
    exit()

x = 7 % K
i = 1
while True:
    if x == 0:
        print(i)
        exit()
    x = (x * 10 + 7) % K
    i += 1
    if i > 10**6:
        print(-1)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
c = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        c[j] += i - b[j] if a[i] >> j & 1 else b[j]
        b[j] += a[i] >> j & 1
for j in range(60):
    ans += c[j] << j
print(ans % (10**9 + 7))


### FIXED CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        ans += (i - b[j] if a[i] >> j & 1 else b[j]) << j
    ans %= 10**9 + 7
    for j in range(60):
        b[j] += a[i] >> j & 1
print(ans)
### BUGGY CODE ###

import sys
n = int(input())

R = [0] * n
for i in range(n):
    R[i] = int(input())

# Naive Algorithm
max_gap = R[1] - R[0]
for i in range(n):
    for j in range(i+1, n):
        if R[j]-R[i] > max_gap:
            max_gap = R[j]-R[i]

print(max_gap)

### FIXED CODE ###

import sys
n = int(input())

R = [0] * n
for i in range(n):
    R[i] = int(input())

# Naive Algorithm
# mx = R[1] - R[0]
# for i in range(n):
#     for j in range(i+1, n):
#         if mx < A[j] - A[i]:
#             mx = A[j] - A[i]

# O(N) Algorithm
mx = R[1] - R[0]
mn = min(R[:2])

for r in R[2:]:
    if mx < r-mn:
        mx = r-mn
    elif mn > r:
        mn = r

print(mx)
### BUGGY CODE ###

N = int(input())
pas = [0]*5
for i in range(5):
  pas[i] = int(input())
city = [0]*6
city[0] = N
temp = [0]*6
times = 0
while city[-1] < N:
  for i in range(len(city)-1):
    if city[i] == 0:
      continue
    temp[i+1] += min(city[i], pas[i])
    city[i] = max(0, city[i]-pas[i])
  for i in range(1,len(city)):
    city[i] += temp[i]
    temp[i] = 0
  times += 1
print(times)

### FIXED CODE ###

N = int(input())
pas = [0]*5
for i in range(5):
  pas[i] = int(input())
min_pas = min(pas)
if N==min_pas:
  times = 0
elif min_pas == 1:
  times = N-1
else:
  times = N//min_pas
times += 5
print(times)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

if n % 2 == 1:
    for i in range(1,m+1):
        print(i,n-i+1)
    sys.exit()

else:
    a = [0]*n
    i = 0
    j = 1
    while True:
        if a[i % n] == 0 and a[(i+j) % n] == 0:
            a[i % n] = 1
            a[(i+j) % n] = 1
            print((i % n) + 1, ((i+j) % n) +1)
            j = j + 1
        else:
            i = i + 1




### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

p = m // 2
for i in range(p):
    print(p-i,p+2+i)

q = m // 2 + 1
if m % 2 == 1:
    for i in range(q):
        print(m+q-i,m+q+i+1)
else:
    for i in range(q-1):
        print(m+q-i,m+q+i+1)
### BUGGY CODE ###

import copy
N = int(input())
l = []
for i in range(N):
  l.append(input())
for i in range(N):
  a = copy.copy(l)
  del a[i]
  print(max(a))
  


### FIXED CODE ###

import copy

N = int(input())
l = []
for i in range(N):
  l.append(int(input()))

mcnt = 0
mv = max(l)
for i in range(N):
  if l[i] == mv and mcnt == 0:
    a = copy.copy(l)
    del a[i]
    print(max(a))
    mcnt = mcnt + 1
  else:
    print(mv)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#
#すぬけ君は、犬を N 匹と猿を M 匹飼っています。
#すぬけ君は、この N+M 匹を一列に並べようと思っています。
#文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、
#犬同士、または猿同士が隣り合うところができないように並べようと思っています。
#このような並べ方は何通りあるでしょうか。
#犬と猿は 109+7 以上の数を理解できないので、
#並べ方の個数を 109+7 で割ったあまりを求めてください。 
#ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

Data = input().split()
N = int(Data[0])
M = int(Data[1])


if abs(N - M) >= 2:
    print(0)
    
else:
    A = 1
    B = 1
    for i in range(N):
        A = A * (i + 1)

    for i in range(M):
        B = B * (i + 1)

    if N == M:
        ans1 = A * B * 2
    else:
        ans1 = A * B
    
    ans2 = ans1 % (1000000000 + 7)
    
    print(ans2)




### FIXED CODE ###

# -*- coding: utf-8 -*-
#
#すぬけ君は、犬を N 匹と猿を M 匹飼っています。
#すぬけ君は、この N+M 匹を一列に並べようと思っています。
#文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、
#犬同士、または猿同士が隣り合うところができないように並べようと思っています。
#このような並べ方は何通りあるでしょうか。
#犬と猿は 109+7 以上の数を理解できないので、
#並べ方の個数を 109+7 で割ったあまりを求めてください。 
#ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

import math

Data = input().split()
N = int(Data[0])
M = int(Data[1])

if abs(N - M) >= 2:
    print(0)
    
else:
    
    A = math.factorial(N)
    B = math.factorial(M)

    if N == M:
        ans1 = A * B * 2
    else:
        ans1 = A * B
    
    ans2 = ans1 % (1000000000 + 7)
    
    print(ans2)
### BUGGY CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

### FIXED CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))
### BUGGY CODE ###

k,s=map(int,input().split())

true=0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                true=true+1

print(true)

### FIXED CODE ###

k,s=map(int,input().split())

true=0

for x in range(k+1):
    for y in range(k+1):
        if 0<=s-x-y<=k:
            true=true+1

print(true)
### BUGGY CODE ###

n=int(input())
ans=len(str(n))
from math import floor,sqrt
s=floor(sqrt(n))
f=[]
for i in range(2,s+1):
    if n%i==0:
        while True:
            f.append(i)
            n//=i
            if n%i!=0:
                break
if n!=1:
    f.append(n)
l=len(f)
iter=2**l-1
for i in range(2**l):
    iter+=1
    liter=str(bin(iter))[3:]
    a,b=1,1
    for j in range(l):
        if liter[j]=="0":
            a*=f[j]
        else:
            b*=f[j]
    t=max(len(str(a)),len(str(b)))
    if t<ans:
        ans=t
print(ans)


### FIXED CODE ###

#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
import math
#li=input().split()
#S=input()
#lis=list(map(int,input().split()))

n=int(input())

A=[0]
i=1
while i<=math.sqrt(n):
    if n%i==0:
        A.append(i)
    i+=1
B=[0]
s=[]
for i in range(len(A)-1):
    j=int(n/A[i+1])
    B.append(j)
    a=len(str(A[i+1]))
    b=len(str(B[i+1]))
    s.append(max(a,b))
ans=min(s)
print(ans)
### BUGGY CODE ###

# abc139_d.py
N = int(input())
A = [N-i for i in range(N)]
print(sum(A)-N)

### FIXED CODE ###

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

a, b, x = map(int, input().split())
count = 0
for i in range(a, b+1):
    if i % x == 0:
        count += 1
print(count)


### FIXED CODE ###

a,b,x = map(int,input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

import sys
def main():
    st = input()
    q = int(input())

    for _ in range(q):
        t = sys.stdin.read(1)
        if t == '2':
            f, a = input().split()
            if f == '1':
                st = a + st
            else:
                st = st + a
        else:
            t = sys.stdin.read(1)
            st = st[::-1]

    print(st)

main()

### FIXED CODE ###

"""
    Author: _YL_
"""
s = input()
n = int(input())

flip = 0
left = 0
right = 1
strs = ["", ""]

i = 0
while i < n:
    lst = input().split()

    if lst[0] == "1":
        flip += 1
        left = 0 if left == 1 else 1
        right = 0 if right == 1 else 1
    elif lst[1] == "1":
        strs[left] += lst[2]
    else:
        strs[right] += lst[2]
    i += 1

if flip % 2 == 1:
    s = s[::-1]
    
s = strs[left][::-1] + s + strs[right]

print(s)
### BUGGY CODE ###

s = input()

ans = 0

while "ABC" in s:
    s = s.replace("ABC","BCA",1)
    ans += 1
    
print(ans)

### FIXED CODE ###

s = input()
 
ans = 0
s = s.replace("BC","D")
cnt_A = 0
 

for i in s:
    if i == "A":
        cnt_A += 1
    elif i == "D":
        ans += cnt_A
    else:
        cnt_A = 0

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

N, K, Q = map(int, input().split())
Ai = list(map(int, [input() for i in range(Q)]))

final = [K-Q for i in range(N)]
add = [Ai.count(i+1) for i in range(N)]

scores = list(map(lambda x, y: x+y, final, add))

for k in range(len(scores)):
    if scores[k] > 0 :
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
Ai = list(map(int, [input() for i in range(Q)]))

scores = [K-Q for i in range(N)]

for i in range(Q):
    scores[Ai[i] - 1] += 1
    scores = scores


for k in range(len(scores)):
    if scores[k] > 0 :
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
def gcd_l(a):
  tmp=a[0]
  for i in range(len(a)):
    tmp=gcd(tmp,a[i])
  return tmp
tmp=gcd_l(a)
for i in range(n):
  b=[a[j] for j in range(len(a)) if i!=j]
  tmp=max(gcd_l(b),tmp)
print(tmp)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
def gcd_l(a):
  tmp=a[0]
  for i in range(len(a)):
    tmp=gcd(tmp,a[i])
  return tmp
tmp=gcd_l(a[1:])
p=set()
for i in range(1,int(a[0]**0.5)+1):
  if a[0]%i==0:
    if i>tmp:
      p.add(i)
    if a[0]//i>tmp:
      p.add(a[0]//i)
if len(p)==0:
  print(tmp)
  exit()
p=sorted(list(p),reverse=True)
for x in p:
  b=[not a[i]%x for i in range(n)]
  if sum(b)==n-1:
    print(x)
    exit()
print(tmp)
### BUGGY CODE ###

import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    s = int(s)
    dp = np.roll(dp, s)
  
print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

from collections import deque
n , m = map(int, input().split())
g = [[0]*n for i in range(n)]
v = [0]*n
v[0]=1
f = [0]*n
for i in range(m):
    a , b = map(int, input().split())
    a-=1
    b-=1
    g[a][b]=1
    g[b][a]=1

d=deque()
d.append(0)

while d:
    room = d.popleft()
    for i in range(n):
        if v[i]==1:
            continue
        if g[room][i]==1:
            d.append(i)
            v[i]=1
            f[i]=room

for i in range(n):
    if v[i]==0:
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(f[i]+1)


### FIXED CODE ###

from collections import deque
n , m = map(int, input().split())
g = [[] for i in range(n)]
v = [0]*n
v[0]=1
f = [0]*n
for i in range(m):
    a , b = map(int, input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

d=deque()
d.append(0)

while d:
    room = d.popleft()
    for i in g[room]:
        if v[i]==1:
            continue

        d.append(i)
        v[i]=1
        f[i]=room

for i in range(n):
    if v[i]==0:
        print('No')
        exit()
print('Yes')
for i in range(1,n):
    print(f[i]+1)