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

import sys
from collections import Counter

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())


for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        x = int(x)
        if x == 1:
            S = y + S[1:]
        elif x == N:
            S = S[:-1] + y
        else:
            S = S[:x - 1] + y + S[x:]
    else:
        print(len(Counter(S[int(x) - 1:int(y)]).keys()))


### FIXED CODE ###

import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    # i文字目を、変化点があった文字として探索する
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)
### BUGGY CODE ###

# coding:utf-8                                                                  

from collections import defaultdict

N, K = map(int, raw_input().split())
As = map(int, raw_input().split())

dic = defaultdict(lambda: 0)

for a in As:
    dic[a] += 1

count = 0
while True:
    if len(dic) <= K:
        break
    dekey = min(dic, key=(lambda x: dic[x]))
    count += dic[dekey]
    del dic[dekey]

print count


### FIXED CODE ###

# coding:utf-8                                                                  

from collections import defaultdict

N, K = map(int, raw_input().split())
As = map(int, raw_input().split())

dic = defaultdict(lambda: 0)

for a in As:
    dic[a] += 1

tar = len(dic) - K

count = 0
if tar <= 0:
    print count
else:
    for i, (k, v) in enumerate(sorted(dic.items(), key=lambda x: x[1])):
        count += v
        if i+1 == tar:
            print count
            break
### BUGGY CODE ###

n=int(input())
a=list(enumerate(map(int,input().split())))
a.sort(key=lambda x: -x[1])
dp=[[0]*(n+1) for i in range(n+1)]
for idx,ix in enumerate(a):
    i,x=ix
    for j in range(idx+1):
        dp[j+1][idx-j]=max(dp[j+1][idx-j],dp[j][idx-j]+(i-j)*x)
        dp[j][idx-j+1]=max(dp[j][idx-j+1],dp[j][idx-j]+((n-1-(idx-j))-i)*x)
print(max([dp[i][n-i] for i in range(n+1)]))

### FIXED CODE ###

n=int(input())
a=list(enumerate(map(int,input().split())))
a.sort(key=lambda x: -x[1])
dp=[[0]*(n+1) for i in range(n+1)]
for idx,ix in enumerate(a):
    i,x=ix
    for j in range(idx+1):
        dp[j+1][idx-j]=max(dp[j+1][idx-j],dp[j][idx-j]+(i-j)*x)
        dp[j][idx-j+1]=max(dp[j][idx-j+1],dp[j][idx-j]+((n-1-(idx-j))-i)*x)
print(max([dp[i][n-i] for i in range(n+1)]))
### BUGGY CODE ###

import sys

def bsearch(target, min_i, max_i, func):
    # func(index) < target <= func(index+1) となるindexを返す
    if func(max_i) < target:
        return max_i
    if target <= func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) < target:
            if target <= func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

n=int(input())
xs = sorted(list(map(int,input().split())))
bs = [xs.pop()]
cs = xs
for _ in range(n):
    for bi in range(len(bs)):
        ci = bsearch(bs[bi], 0, len(cs)-1, lambda x : cs[x])
        if ci == None:
            print("No")
            sys.exit()
        bs.append(cs[ci])
        del cs[ci]
print("Yes")




### FIXED CODE ###

import sys
def b(bs, cs):
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    ncs = []
    while True:
      if bs[bi] > cs[ci]:
        bs.append(cs[ci])
        bi += 1
      else:
        ncs.append(cs[ci])
      ci += 1
      if bi == bl or ci == cl:
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, ncs + cs[ci:]

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")
### BUGGY CODE ###

S = input()


def calculate(s):
    length = len(s)

    rs = reversed(s)

    sss = 0
    dict = {0: 1}
    for index, c in enumerate(rs):
        sss = sss + int(c) * 10 ** index
        mod = sss % 2019

        if dict.get(mod) == None:
            dict.__setitem__(mod, 1)
        else:
            dict.__setitem__(mod, dict.get(mod) + 1)


    res = 0
    for d in dict.values():
        if d > 1:
            res = res + d -1

    print(res)


calculate(S)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

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

dp = [[0]*(W+1) for _ in range(N+1)]
    
def npsk_1(N, W):
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(W+1):
            if j - w >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
            else:
                dp[i+1][j] = dp[i][j]
    
    print(dp[N][W])

npsk_1(N, W)

### FIXED CODE ###

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

w, v = [0] * N, [0] * N

for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
		else:
		    dp[i + 1][j] = dp[i][j] 

print(dp[N][W])
### BUGGY CODE ###

N, A = map(int, input().split())
x = list(map(int, input().split()))
sum_x = sum(x)
X = max(x + [A])

dp = [[[0] * (N * X + 1) for _ in range(N + 1)] for _ in range(N + 1)]

for j in range(len(dp)):
    for k in range(len(dp[j])):
        for s in range(len(dp[j][k])):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
            else:
                dp[j][k][s] = 0

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

print(answer)


### FIXED CODE ###

from functools import lru_cache

N, A = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(lambda i: i - A, x))
X = max(max(x), A)

@lru_cache(maxsize=None)
def solve(j, t):
    global y
    if j == 0 and t == 0:
        return 1
    elif j >= 1 and (t < y[j - 1] - N * X or t > y[j - 1] + N * X):
        return solve(j - 1, t)
    elif j >= 1 and t >= y[j - 1] - N * X and t <= y[j - 1] + N * X:
        return solve(j - 1, t) + solve(j - 1, t - y[j - 1])
    else:
        return 0

print(solve(N, 0) - 1)
### BUGGY CODE ###

N, M, L = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b, c = map(int, input().split())
    V[a].append((b, c))
    V[b].append((a, c))
INF = float('inf')
VD = {i: {i: INF for i in range(1,N+1)} for i in range(1,N+1)}
for i, e in V.items():
    for (j, c) in e:
        VD[i][j] = c
        VD[j][i] = c
for i in range(1,N+1):
    VD[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if VD[i][j] > VD[i][k] + VD[k][j]:
                VD[i][j] = VD[i][k] + VD[k][j]

W = {i: [] for i in range(1,N+1)}
for i, v in VD.items():
    for j, d in v.items():
        if d <= L:
            W[i].append(j)
            W[j].append(i)

WD = {i: {i: INF for i in range(1,N+1)} for i in range(1,N+1)}
for i, e in W.items():
    for j in e:
        WD[i][j] = 1
        WD[j][i] = 1
for i in range(1,N+1):
    WD[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if WD[i][j] > WD[i][k] + WD[k][j]:
                WD[i][j] = WD[i][k] + WD[k][j]

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(WD[s][t]-1 if WD[s][t] < INF else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, L = map(int, input().split())
INF = float('inf')
VD = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    VD[a][b] = c
    VD[b][a] = c
for i in range(N):
    VD[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if VD[i][j] > VD[i][k] + VD[k][j]:
                VD[i][j] = VD[i][k] + VD[k][j]

WD = [[INF] * N for _ in range(N)]
for i in range(N):
    WD[i][i] = 0
    for j in range(i+1,N):
        d = VD[i][j]
        if d <= L:
            WD[i][j] = 1
            WD[j][i] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if WD[i][j] > WD[i][k] + WD[k][j]:
                WD[i][j] = WD[i][k] + WD[k][j]

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(WD[s-1][t-1]-1 if WD[s-1][t-1] < INF else -1)
### BUGGY CODE ###

# B - Frog 2
N, K = map(int,input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N

dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,N):
    for k in range(1,K+1):
        dp1 = dp[i - k]+ abs(h[i] - h[i - k])
        if dp[i] >= dp1:
            dp[i] = dp1
            if dp[i] == 0:
                break
        else:
            pass

print(dp[N-1])

### FIXED CODE ###

#B - Frog 2
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 9] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,N):
    for j in range(K,0,-1):
        dp[i] = min(dp[i],dp[i-j] + abs(h[i] - h[i-j]))

#print(dp)
print(dp[N-1])
### BUGGY CODE ###

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

MOD=10**9+7
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

print(ans)

### FIXED CODE ###

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

MOD=10**9+7
def gcd(a,b):
    while b: a,b=b,a%b
    return a
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]%MOD
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

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

import numpy as np

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

left = [[0] * W for i in range(H)]
for i in range(H):
    c = -1
    for j in range(W):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        left[i][j] = c

right = [[0] * W for i in range(H)]
for i in range(H):
    c = -1
    for j in range(W-1, -1, -1):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        right[i][j] = c

up = [[0] * W for i in range(H)]
for j in range(W):
    c = -1
    for i in range(H):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        up[i][j] = c

down = [[0] * W for i in range(H)]
for j in range(W):
    c = -1
    for i in range(H-1, -1, -1):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        down[i][j] = c

n_right = np.array(right)
n_left = np.array(left)
n_up = np.array(up)
n_down = np.array(down)

n_all = n_right+n_left+n_up+n_down
print(np.max(n_all)+1)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == "."

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1]+1)*S[i]
    D[-i - 1] = (D[-i] + 1) * S[-i - 1]

for i in range(W):
    L[:, i] = (L[:, i - 1] + 1) * S[:, i]
    R[:, -i - 1] = (R[:, -i] + 1) * S[:, -i - 1]

print(np.max(D + U + R + L) - 3)
### BUGGY CODE ###

S = input()[::-1]

res = 0
tmp = [0] * 2019
tmp[0] = 1
sum_of_digits = 0
d = 1

for c in S:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    # d %= 2019
    tmp[sum_of_digits] += 1

for t in tmp:
    res += (t * (t - 1)) // 2

print(res)

### FIXED CODE ###

S = input()[::-1]

res = 0
tmp = [0] * 2019
tmp[0] = 1
sum_of_digits = 0
d = 1

for c in S:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    tmp[sum_of_digits] += 1

for t in tmp:
    res += (t * (t - 1)) // 2

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

from bisect import bisect_left as bl
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()
    M = max(A)
    E = list(map(lambda x:abs(x-K),A))
    E = set(E)
    C = [A[i+1]-A[i] for i in range(N-1)]
    C = set(C)
    D = set(A)
    if E&D:
        print("POSSIBLE")
        exit()
    for i in range(2,int(M**0.5)+10):
        B = set(map(lambda x:x%i,A))
        if len(B) == 1:
            print("IMPOSSIBLE")
            exit()
    print("IMPOSIBLE")
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    if K > max(A):
        print("IMPOSSIBLE")
        exit()
    if K in A:
        print("POSSIBLE")
        exit()

    E = list(map(lambda x:abs(x-K),A))
    E = set(E)
    C = [A[i+1]-A[i] for i in range(N-1)]
    C = set(C)
    D = set(A)
    if E&D:
        print("POSSIBLE")
        exit()

    print("IMPOSSIBLE")
    

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

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

res=[]

res.append((sum(range(1,p[0]+1)))/p[0])

for i in range(1,N):
    res.append(res[i-1]+(sum(range(1,p[i]+1)))/p[i])
ans=res[K-1]

for i in range(1,N-K+1):
    ans=max(ans,res[i+K-1]-res[i-1])
print(ans)

### FIXED CODE ###

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

res=[]

res.append((sum(range(1,p[0]+1)))/p[0])

for i in range(1,N):
    res.append(res[i-1]+1+0.5*(p[i]-1))
ans=res[K-1]

for i in range(1,N-K+1):
    ans=max(ans,res[i+K-1]-res[i-1])
print(ans)
### BUGGY CODE ###

N=int(input())
S = [input() for i in range(N)]
result=[]
max=0
name=[]

for i in range(N):
    C=S.count(S[i])
    result.append(C)
    if C>max:
        max=C
for i in range(N):
    if max==result[i]:
        name.append(S[i])
name_set=set(name)
name_list=sorted(list(name_set))

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

### FIXED CODE ###

from collections import Counter

N=int(input())
S = [input() for i in range(N)]
result=[]

counter = Counter(S)
m = max(counter.values())

for name in counter.keys():
    if m==counter[name]:
        result.append(name)

result_sort=sorted(result)

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

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

for i in range(Q):
    B, C = map(int, input().split())

    for i in range(A.count(B)):
        A[A.index(B)] = C

    print(sum(A))

### FIXED CODE ###

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

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

for i in A:
    data[i] += 1

sum_val = my_sum(data)

for i in range(Q):
    B, C = map(int,input().split())

    sum_val = sum_val - (data[B] * B) + (data[B] * C)

    data[C] += data[B]
    data[B] = 0

    print(sum_val)
### BUGGY CODE ###

p = int(input())
aaa = list(map(int, input().split()))

coefs = [0] * p
coefs[0] = sum(aaa)
invs = [pow(x, p - 2, p) for x in range(p + 1)]
for i, a in enumerate(aaa):
    if a == 0:
        continue
    b = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b) % p
        b = -b * i * j * invs[p - j] % p

print(*coefs)


### FIXED CODE ###

p = int(input())
aaa = list(map(int, input().split()))

coefs = [0] * p
coefs[0] = sum(aaa)
invs = [pow(x, p - 2, p) for x in range(p + 1)]
for i, a in enumerate(aaa):
    if a == 0:
        continue

    b = 1
    c = 1
    for j in range(p - 1, -1, -1):
        coefs[j] = (coefs[j] - b * c) % p
        b = -b * i % p
        c = c * j * invs[p - j] % p

print(*coefs)
### BUGGY CODE ###

h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            if 2<=x+j-1<=h-1 and 2<=y+k-1<=w-1: 
                p.append([x+j-1,y+k-1])
p.sort()
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    #if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
    if p[i]==p[i+1]:
        f+=1
    else:
        ans[f]+=1
        f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            p.append([x+j-1,y+k-1])
p.sort(key=lambda x:(10**10)*x[0]+x[1])
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
        if p[i]==p[i+1]:
            f+=1
        else:
            ans[f]+=1
            f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
A = [int(j) for j in input().split()]
from collections import Counter

A_C =Counter(A)
A_C = sorted(A_C.items(),key=lambda x:x[0])

result = 1
for a in A_C:
    if a[0]==0:
        print(0)
        exit()
    result*=(a[0]**a[1])

if result >10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = [int(j) for j in input().split()]
from collections import Counter

A_C =Counter(A)
A_C = sorted(A_C.items(),key=lambda x:-x[0])

if 0 == A_C[-1][0]:
    print(0)
    exit()
    
result = 1
for a in A_C:
    result*=(a[0]**a[1])

    if result >10**18:
        print(-1)
        exit()

print(result)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
for j in range(0, k-1):
  p[j]=(p[j]+1)*p[j]/(p[j]*2)#p[i]が期待値になった
list00=[]
for i in range(k-1, n):
  p[i]=(p[i]+1)*p[i]/(p[i]*2)#p[i]が期待値になった
  list00.append(sum(p[i-k+1:i+1]))
list00.sort()
print(list00[n-k])


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))

kouho=0
lis=[0]*n
lis[0]=(1+p[0])/2
for i in range(0,n):
  if i>=1:
    lis[i]=lis[i-1]+(1+p[i])/2
  if i==k-1:
    kouho=lis[i]
  if i>k:
    if lis[i]-lis[i-k]>kouho:
      kouho=lis[i]-lis[i-k]
print(kouho)
### BUGGY CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]
sall = lambda: sys.stdin.readlines()

def main():
    n, k = na()

    '''
    for i in range(k, n+1, k):
        for j in range(k, n+1, k):
            if (i + j) % k == 0:
                for m in range(k, n+1, k):
                    if (i+m) % k == 0 and (j+m) % k == 0:
                        print(i, j, m)
    '''
    # kは奇数
    if k % 2 == 1:
        print((n // k) ** 3)
        return

    c = 0
    for i in range(k//2, n+1, k//2):
        for j in range(k//2, n+1, k//2):
            if (i + j) % k == 0:
                for m in range(k//2, n+1, k//2):
                    if (i+m) % k == 0 and (j+m) % k == 0:
                        #print(i, j, m)
                        c += 1

    # kは偶数
    print(c)

main()


### FIXED CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]
sall = lambda: sys.stdin.readlines()

def main():
    n, k = na()

    '''
    for i in range(k, n+1, k):
        for j in range(k, n+1, k):
            if (i + j) % k == 0:
                for m in range(k, n+1, k):
                    if (i+m) % k == 0 and (j+m) % k == 0:
                        print(i, j, m)
    '''
    # kは奇数
    if k % 2 == 1:
        print((n // k) ** 3)
        return
    '''
    c = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            if (i + j) % k == 0:
                for m in range(1, n+1):
                    if (i+m) % k == 0 and (j+m) % k == 0:
                        print(i, j, m)
                        c += 1
    '''
    # kは偶数
    c = (n//k) ** 3 + (n//(k//2) - n//k)  ** 3
    print(c)

main()
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i, n):
        for k in range(j, n):
            if (s[i] != s[j] and s[i] != s[k] and s[j] != s[k]) and (j-i != k-j):
                ans += 1

print(ans)

### FIXED CODE ###

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

R = s.count('R')
G = s.count('G')
B = s.count('B')
ans = R*G*B

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n: break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

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

mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    dat_m.append(int(input()))
dp[0] = 1
for i in range(1, n + 1):
    #print(dp)
    dp[i] = dp[i - 1]

    if i > 1:
        dp[i] += dp[i - 2]

    if i in dat_m:
        dp[i] = 0

    dp[i] = dp[i] % mod

#import pprint
print(dp[n])
#pprint.pprint(dp)

### FIXED CODE ###

mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    t = int(input())
    dp[t] = -1

dp[0] = 1
for i in range(1, n + 1):
    if dp[i] == -1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

print(dp[n])
### BUGGY CODE ###

from bisect import *
from sys import stdout
N, Q = map(int, input().split())
c = 1
B = [1]
ans = []
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, input().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    ans.append(str(v))
print("\n".join(ans))


### FIXED CODE ###

from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(n-1):
    ans += i+1

print(ans)

### FIXED CODE ###

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

print(ans)