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

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[INF]*W for _ in range(H)]
dists[r1][c1] = 0
q = deque([(r1,c1)])
while q:
    y,x = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if dists[ny][nx] <= dists[y][x] + 1: continue
        dists[ny][nx] = dists[y][x] + 1
        q.append((ny,nx))

costs = [INF] * (H*W*4)
costs[(r1*W+c1)*4] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if dists[ny][nx] >= dists[y][x] + 20: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if costs[(y*W+x)*4+di] <= nc: continue
            costs[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if costs[(ny*W+nx)*4+di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

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

L = [[0 for j in range(W)] for i in range(H)]
R = [[0 for j in range(W)] for i in range(H)]
U = [[0 for j in range(W)] for i in range(H)]
D = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        L[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == 0 else L[i][j-1])
    for j in range(W-1, -1, -1):
        R[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == W-1 else R[i][j+1])
for j in range(W):
    for i in range(H):
        U[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == 0 else U[i-1][j])
    for i in range(H-1, -1, -1):
        D[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == H-1 else D[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

### FIXED CODE ###

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

L = [[0 for j in range(W)] for i in range(H)]
R = [[0 for j in range(W)] for i in range(H)]
U = [[0 for j in range(W)] for i in range(H)]
D = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        L[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == 0 else L[i][j-1])
    for j in range(W-1, -1, -1):
        R[i][j] = 0 if S[i][j] == '#' else 1 + (0 if j == W-1 else R[i][j+1])
for j in range(W):
    for i in range(H):
        U[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == 0 else U[i-1][j])
    for i in range(H-1, -1, -1):
        D[i][j] = 0 if S[i][j] == '#' else 1 + (0 if i == H-1 else D[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

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

N,X,Y=map(int,input().split())

Ans=[]

i=1
while i<=N:
    j=i+1
    while j<=N:
        Ans.append(min(j-i,abs(X-i)+1+abs(j-Y)))
        j=j+1
    i=i+1

k=1
while k<=N-1:
    print(Ans.count(k))
    k=k+1

### FIXED CODE ###

N,X,Y=map(int,input().split())

Ans=[0]*N

i=1
d=0
while i<=N:
    j=i+1
    while j<=N:
        d=(min(j-i,abs(X-i)+1+abs(j-Y)))
        Ans[d]+=1
        j+=1
    i+=1

k=1
while k<=N-1:
    print(Ans[k])
    k+=1
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2, N):
        k = 1
        for k in range(1, K + 1):
            if 0 > i - k:
                break
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

    print(dp[-1])


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(N)]
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2, N):
        k = 1
        for k in range(1, K + 1):
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))
    print(dp[-1])


main()
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [-1] * (W + 1)
dp[0] = 0
ws = []
ps = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  ps.append(v)
  
for i in range(len(ws)):  
  for j in range(W - ws[i], -1, -1):
    dpi = dp[j]
    if dpi != -1:
      if dp[j + ws[i]] < dpi + ps[i]:
        dp[j + ws[i]] = dpi + ps[i]
print(max(dp))

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

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

ex = [0] * n
for i in range(n):
    ex[i] += sum([j for j in range(1, p[i] + 1)]) / p[i]

ans = 0
for j in range(n - k + 1):
    sum = 0
    for z in range(j,j + k):
        sum += ex[z]
    ans = max(ans, sum)

print(ans)

### FIXED CODE ###

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

saikoro = [0] * 1001
for i in range(1, 1001):
    saikoro[i] = (saikoro[i-1] + i)

s = [0] * (n + 1)
for u in range(1,n + 1):
    s[u] = saikoro[p[u - 1]] / p[u - 1] + s[u - 1]

ans = 0
for j in range(k - 1,n):
    ans = max(ans, s[j + 1] - s[j + 1 - k])
 
print(ans)
### BUGGY CODE ###

import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


primes = eratosthenes(N)

like_2017 = [p for p in primes if (p + 1) // 2 in primes]


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if i in like_2017:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])


### FIXED CODE ###

import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


_primes = eratosthenes(N)

primes = [False] * (10**5 + 1)

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5 + 1)

for p in _primes:
    if primes[(p + 1) // 2]:
        like_2017[p] = True


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])
### BUGGY CODE ###

K, S = map(int, input().strip().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().strip().split())

ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - (x + y)
        if z >= 0 and z <= K:
            ans += 1

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

import sys
from bisect import bisect_right,bisect_left
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A,B = LI(),LI()

# 各桁の xor を考える

ans = 0
mod = 1 << 29
for i in range(29,0,-1):  # 2**(i-1) の位
    X = [A[j] & (mod-1) for j in range(N)]
    Y = [B[j] & (mod-1) for j in range(N)]
    Y.sort()
    mod >>= 1
    r = 0
    for j in range(N):
        a = X[j]
        # [2**(i-1)-a,2*2**(i-1)-a),[3*2**(i-1)-a,4*2**(i-1)-a) にある Y の要素の個数を数え上げる
        r += bisect_right(Y,2*mod-a-1) - bisect_left(Y,mod-a)
        r += bisect_right(Y,4*mod-a-1) - bisect_left(Y,3*mod-a)
    if r % 2 == 1:
        ans += mod

print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_right,bisect_left
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A,B = LI(),LI()

# 各桁の xor を考える

ans = 0
mod = 1 << 29
for i in range(29,0,-1):  # 2**(i-1) の位
    X = [a & (mod-1) for a in A]
    Y = [b & (mod-1) for b in B]
    X.sort()
    Y.sort(reverse=True)
    mod >>= 1
    r = 0
    i1,i2,i3 = 0,0,0
    for j in range(N):
        x = X[j]
        # [2**(i-1)-x,2*2**(i-1)-x),[3*2**(i-1)-x,4*2**(i-1)-x) にある Y の要素の個数を数え上げる
        # 尺取り法
        while i1 < N and Y[i1] >= mod-x:
            i1 += 1
        while i2 < N and Y[i2] >= 2*mod-x:
            i2 += 1
        while i3 < N and Y[i3] >= 3*mod-x:
            i3 += 1
        r += i1-i2+i3
    if r % 2 == 1:
        ans += mod

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

import math
monsterNum, centerDamage, otherDamage = map(int, input().split())
monsterHitpoint = [0] * monsterNum
maxHitpoint = 0

def enough(times):
  damageCount = 0
  hitpoint = [monsterHitpoint[i] - otherDamage * times for i in range(monsterNum)]
  for i in range(monsterNum):
    if hitpoint[i] > 0:
      damageCount += math.ceil(hitpoint[i] / (centerDamage - otherDamage))
  if damageCount <= times:
    return True
  else:
    return False
  
for i in range(monsterNum):
  monsterHitpoint[i] = int(input())
  if maxHitpoint < monsterHitpoint[i]:
    maxHitpoint = monsterHitpoint[i]
#2分探索
ansFlag = False
subtractionValue = math.ceil(maxHitpoint / otherDamage)
minTimes = subtractionValue
while not ansFlag:
  checkEnough = enough(minTimes)
  subtractionValue = subtractionValue // 2
  if checkEnough and not(enough(minTimes - 1)):
    ansFlag = True
  elif checkEnough:
    minTimes -= subtractionValue
  elif not checkEnough and (enough(minTimes + 1)):
    minTimes += 1
    ansFlag = True
  elif not checkEnough:
    minTimes += subtractionValue + 1
print(minTimes)

### FIXED CODE ###

import math
monsterNum, centerDamage, otherDamage = map(int, input().split())
monsterHitpoint = [0] * monsterNum
maxHitpoint = 0

def enough(times):
  result = True
  damageCount = 0
  hitpoint = [monsterHitpoint[i] - otherDamage * times for i in range(monsterNum)]
  for i in range(monsterNum):
    if hitpoint[i] > 0:
      damageCount += math.ceil(hitpoint[i] / (centerDamage - otherDamage))
    if damageCount > times:
      result = False
      break
  return result
  
for i in range(monsterNum):
  monsterHitpoint[i] = int(input())
  if maxHitpoint < monsterHitpoint[i]:
    maxHitpoint = monsterHitpoint[i]
#2分探索
low, high = 0, math.ceil(maxHitpoint / otherDamage)
while low <= high:
  minTimes = (low + high) // 2
  checkEnough = enough(minTimes)
  if checkEnough and not(enough(minTimes - 1)):
    break
  elif checkEnough:
    high = minTimes - 1
  elif not checkEnough and (enough(minTimes + 1)):
    minTimes += 1
    break
  elif not checkEnough:
    low = minTimes + 1
print(minTimes)
### BUGGY CODE ###

from functools import reduce
n=int(input())
k=list(map(int,input().split()))
for i in range(n):
  c=k[:i]+k[i+1:]
  print(reduce(lambda a,b:a^b,c),end=" ")

### FIXED CODE ###

from functools import reduce
n=int(input())
k=list(map(int,input().split()))
c=reduce(lambda a,b:a^b,k)
for i in range(n):
  print(k[i]^c,end=" ")
### BUGGY CODE ###

from collections import deque

s=deque(list( input() ))
t=deque([]) #

#print(t,s)

cnt=0
while len(s)>0:
  x=s.popleft()
  if len(t)>=2 and x=="C":
    if t[-2]=="A" and t[-1]=="B":
      cnt += 1
      t.pop()
      t.pop()
      s.appendleft("A")
      s.appendleft("C")
      s.appendleft("B")
    else:
      t.append(x)
  else:
    t.append(x)
        
#print(t,s)
print(cnt)

### FIXED CODE ###

from collections import deque

s=input()
s=s.replace("BC","D")
N=len(s)

cnt=0
cntA=0
cntD=0

for i in range(N):
  if s[i]=="A":
    cntA += 1
  elif s[i]=="D":
    cnt += cntA
  else:
    cntA=0
    cntD=0
    
print(cnt)
### BUGGY CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"

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

list_d.sort()

for number in list_t:
    ind = binarySearch(list_d, number)
    if ind != "NOT_FOUND":
        del list_d[ind]
    else:
        print("NO")
        break
else:
    print("YES")


### FIXED CODE ###

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

dict_d = {}
dict_t = {}
for number in set(list_d):
    dict_d[number] = 0
for number in set(list_t):
    dict_d[number] = 0
for number in list_d:
    dict_d[number] += 1

for number in set(list_t):
    dict_t[number] = 0
for number in list_t:
    dict_t[number] += 1

for number,value in dict_t.items():
    if dict_d[number] < value:
        print("NO")
        break
    else:
        pass
else:
    print("YES")
### BUGGY CODE ###

# B_A to Z String
import sys

s = input()

def getNum(s) :
    for i in range(len(s)):
        for j in reversed(range(len(s))):
            if s[i] == 'A' and s[j] == 'Z' :
                res = j - i + 1
                return res
print(getNum(s))

### FIXED CODE ###

# B_A to Z String

s = input()

def getNum(s) :
    a = s.find("A")
    b = s.rfind("Z")
    return b - a + 1
print(getNum(s))
### BUGGY CODE ###

import sys
s = sys.stdin.readlines()
N = int(s[0])
S = s[1]
Q = int(s[2])

seg = [set([]) for _ in range(2*N-1)]
def update(k, x):
    k += N-1
    seg[k] = set([x])
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = set([])
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return len(res)

for i in range(N):
    update(i, S[i])
    
for i in range(3, Q+3):
    a,b,c = map(str, s[i].split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

### FIXED CODE ###

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

seg = [0]*(2*N-1)

def update(k, x):
    k += N-1
    seg[k] = 2**x
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return bin(res).count("1")

def f(s):
    return ord(s) - ord("a") + 1

for i in range(N):
    update(i, f(S[i]))
    
Q = int(input())
for _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, f(c))
    else:
        print(query(int(b)-1, int(c)))
### BUGGY CODE ###

n = int(input())
s = list(map(int, input()))

used = [False] * 10
pins = []

for i in range(n - 2):
    if not used[s[i]]:
        used[s[i]] = True
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                pin = f"{s[i]}{s[j]}{s[k]}"
                if pin not in pins:
                    pins.append(pin)
print(len(pins))

### FIXED CODE ###

n = int(input())
s = list(map(int, input()))

ans = []

for i in range(10):
    if i in s:
        a = s.index(i)
        for j in range(10):
            if j in s[a + 1 :]:
                b = [x for x, y in enumerate(s) if x > a and y == j][0]
                for k in range(10):
                    if k in s[b + 1 :]:
                        ans.append(f"{i}{j}{k}")
print(len(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
Left = True

for i in range(Q):
    TFC = input()

    if TFC[0] == "1":
        Left = not Left

    elif TFC[0] == "2" and TFC[2] == "1":
        if Left:
            S = TFC[4] + S
        else:
            S = S + TFC[4]

    else:
        if Left:
            S = S + TFC[4]
        else:
            S = TFC[4] + S

if not Left:
    S = S[::-1]

print(S)


### FIXED CODE ###

from collections import deque

S = deque(map(str, input().split()))
Q = int(input())
Left = False

for i in range(Q):
    TFC = input()

    if TFC[0] == "1":
        Left = not Left

    else:
        _, f, c = TFC[0], TFC[2], TFC[4]
        f = int(f)
        if Left ^ (f == 1):
            S.appendleft(c)

        else:
            S.append(c)

T = "".join(S)
if Left:
    T = T[::-1]

print(T)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1;d=[b]
while b!=2 and b!=1 and len(set(d))==len(d):
  b=a[b-1]
  c+=1
  d.append(b)
if b==2:print(c)
else:print(-1)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=a[0];c=1
while b!=2 and c<=n:
  b=a[b-1]
  c+=1
if b==2:print(c)
else:print(-1)
### BUGGY CODE ###

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


#S_R = []
#S_G = []
#S_B = []
R = 0
G = 0
B = 0

for i in range(N):
    s = S[i]
    if (s == 'R'):
        #_R.append(i)
        R +=1
    if (s == 'G'):
        #S_G.append(i)
        G +=1
    if (s == 'B'):
        #S_B.append(i)
        B +=1

count = R * G * B

#count = len(S_R) * len(S_G) * len(S_B)
#rgb = {'R', 'G', 'B'}


#for i in range(N):
    #for j in range(i):
        #x = S[j::i]
        #for a, b, c in zip(x, x[1:], x[2:]):
            #if({a,b,c} == rgb):
                #count -=1

for i in range(N):
    for j in range(N//2 + 1):
        if(i + j*2 >= N):
            break
        if((S[i] != S[i + j]) & (S[i + j] != S[i + 2 * j]) & (S[i + 2 * j] != S[i])):
            count -= 1




print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    N = int(input())
    A = input_nums()
    C = collections.Counter(A)

    X = {}
    Y = {}

    for k, v in C.items():
        if v >= 2:
            X[k] = cmb(v, 2)
        else:
            X[k] = 0
        if v >= 3:
            Y[k] = cmb(v-1, 2)
        else:
            Y[k] = 0

    ANS = {}
    for k in X.keys():
        val = 0
        for k2 in X.keys():
            if k == k2:
                val += Y[k2]
            else:
                val += X[k2]
        ANS[k] = val
    for a in A:
        print(ANS[a])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    N = int(input())
    A = input_nums()
    C = collections.Counter(A)

    X = {}
    Y = {}
    maxv = 0
    for k, v in C.items():
        if v >= 2:
            X[k] = cmb(v, 2)
            maxv += X[k]
        else:
            X[k] = 0
        if v >= 3:
            Y[k] = cmb(v-1, 2)
        else:
            Y[k] = 0

    ANS = {}
    for k in Y.keys():
        ANS[k] = maxv - (X[k] - Y[k])

    for a in A:
        print(ANS[a])

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

N, K = map(int, input().split())
MOD = 998244353
S = [0] * (N + 1)
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S[j] = 1

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for j in range(1, i + 1):
        if S[j]:
            dp[i] += dp[i - j]
print(dp[-1] % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)
### BUGGY CODE ###

H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])



### FIXED CODE ###

H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])
### BUGGY CODE ###

import collections
K = int(input())
Q = collections.deque([[1, 1]])
searched = set()
while True:
    n, d = Q.popleft()
    r = n % K
    if not r in searched:
        if r == 0:
            break
        else:
            searched.add(r)
            Q.append([n + 1, d + 1])
            Q.appendleft([n * 10, d])
print(d)
# https://img.atcoder.jp/arc084/editorial.pdf


### FIXED CODE ###

import collections
K = int(input())
Q = collections.deque([(1, 1)])
searched = set()
while True:
    n, d = Q.popleft()
    r = n % K
    if not r in searched:
        if r == 0:
            break
        else:
            searched.add(r)
            Q.append((n + 1, d + 1))
            Q.appendleft((n * 10 % K, d))
print(d)
# https://img.atcoder.jp/arc084/editorial.pdf
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
ans = 0

for i in range(N):
  ans += i

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())

print(N * (N - 1) // 2)