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

N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_W = 10 ** 5

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])

### FIXED CODE ###

N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_W = 10 ** 5

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()

    x = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x += pow(2, i)
    xc = binbin(x)
    x1 = x % (xc + 1)
    if xc == 1:
        x2 = -1
    else:
        x2 = x % (xc - 1)
    for i in range(N):
        z = pow(2, N - i - 1)
        if X[i] == '0':
            if x + z == 0:
                print(0)
            else:
                print(1 + popcount((x + z) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                print(1 + popcount((x - z) % (xc - 1)))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


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

import numpy as np
A,B,N=map(int,input().split())
x = np.array([j for j in range(N+1)])
val=np.floor(A*x/B)-A*np.floor(x/B)
print(int(np.max(val)))


### FIXED CODE ###

import math
A,B,N=map(int,input().split())
if(N<B):
    x = N
else:
    x =B-1    

print(int( math.floor(A*x/B)-A*math.floor(x/B)  ))
### BUGGY CODE ###

import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
dp = [[] for i in range(N)]
dp[0] = [A[0]]

for i in range(1, N):
    index = bisect.bisect_left(dp[i-1], A[i])
    dp[i] = dp[i-1].copy()
    if index == 0:
        dp[i].append(A[i])
        dp[i].sort()
    
    else:
        dp[i][index-1] = A[i]
print(len(dp[N-1]))




### FIXED CODE ###

import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
now = [-A[0]]

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]

print(len(now))
### BUGGY CODE ###

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, d in es[v]:
        if value[i] == INF:
            value[i] = value[v] + d
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    #print("lrd",lrd)
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

#print(lrd)

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = ["first"]*n
        answer[i]=1
        BFD(i)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

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

#coding:utf-8
n = int(input())
prices = [int(input()) for i in range(n)]
max_profit = None

for i in range(n-1):
    purchase = prices[i]
    for j in range(i+1,n):
        selling = prices[j]
        if (not max_profit) or max_profit < selling - purchase:
            max_profit = selling - purchase

print(max_profit)

### FIXED CODE ###

#coding:utf-8
#1_1_D
n = int(input())
prices = [int(input()) for x in range(n)]
maxv = -2 * 10 ** 9
minv = prices[0]
for i in range(1, n):
    maxv = max(maxv, prices[i] - minv)
    minv = min(minv, prices[i])

print(maxv)
### BUGGY CODE ###

n = int(input())
rlist = []
for i in range(n):
    r = int(input())
    rlist.append(r)
mlist = [rlist[1] - rlist[0]]
for i in range(1,n):
    m = rlist[i] - min(rlist[:i])
    if(m > mlist[-1]):
        mlist.append(m)
        
print(mlist[-1])


### FIXED CODE ###

n = int(input())
rlist = []
for i in range(n):
    r = int(input())
    rlist.append(r)
mlist = [rlist[1] - rlist[0]]
mini = rlist[0]
for i in range(1,n):
    if(rlist[i-1] < mini):
        mini = rlist[i-1]
    m = rlist[i] - mini
    if(m>mlist[-1]):
        mlist.append(m)
print(mlist[-1])
### BUGGY CODE ###

import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353


def two(x):
    return "0" * (w - len(bin(x)[2:])) + bin(x)[2:]


h, w, maxx = map(int, input().split())
A = []
for i in range(h):
    A.append(input().strip())
# for binary in range(1<<(w-1),(1<<(w-1))+1):
ans = inf
for binary in range(1 << (w - 1)):  # every binary
    S = two(binary)
    B = [-1]
    for i in range(len(S)):
        if S[i] == "1":
            B.append(i)
    B.append(len(S) - 1)  # every horizontal cut, contain the head and the tail
#    print(B)
    SUM = [0] * (len(B))
    isok = 1
    cut_vertical = 0
    cut_horizontal = len(B) - 2
    for i in range(h):
        PRE = copy(SUM)  # previous total numbers between every cut
        for j in range(1, len(B)):  # every cut
            for k in range(B[j - 1] + 1, B[j] + 1):
                if A[i][k] == "1":
                    SUM[j] += 1
        flag = 0
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                flag = 1
        if flag:
            for j in range(1, len(B)):
                SUM[j] -= PRE[j]
            cut_vertical += 1
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                isok = 0
        if isok == 0:
            break
    if isok:
        ans = min(ans, cut_vertical + cut_horizontal)
print(ans)


### FIXED CODE ###

import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353


def two(x):
    return "0" * (h - 1 - len(bin(x)[2:])) + bin(x)[2:]


h, w, k = map(int, input().split())
S = []
ans = inf
for i in range(h):
    S.append(input().strip())
for way_cut in range(1 << (h - 1)):
    way_cut = two(way_cut)
    number_cut_horizontal = way_cut.count("1")
    number_cut_vertical = 0
    CUT = [-1]
    for i in range(len(way_cut)):
        if way_cut[i] == '1':
            CUT.append(i)
    CUT.append(len(way_cut))
    SUM = [0] * (w)
    PRE = [0] * (w)
    for col in range(w):
        for i in range(1, len(CUT)):
            for between in range(CUT[i - 1] + 1, CUT[i] + 1):
                SUM[i] += 1 if S[between][col] == "1" else 0
        isok = True
        for i in range(1, len(CUT)):
            if PRE[i] + SUM[i] > k:
                isok = False
        if not isok:
            number_cut_vertical += 1
            PRE = copy(SUM)
            SUM = [0]*(w)  # leave out
            # recheck
            for i in range(1, len(CUT)):
                if PRE[i] > k:
                    number_cut_vertical = inf
                    break
        else:
            for i in range(1, len(CUT)):
                PRE[i] += SUM[i]
                SUM[i] = 0
    ans = min(ans, number_cut_vertical + number_cut_horizontal)
print(ans)
### BUGGY CODE ###

import copy
import fractions
import functools


def gcd(*numbers):
    return functools.reduce(fractions.gcd, numbers)


n = int(input())
a = list(map(int, input().split()))
nl = set(range(n))
gcd_list = [0]
for i in nl:
    tmp = copy.deepcopy(a)
    tmp.pop(i)
    tmp2 = gcd(*tmp)
    gcd_list.append(tmp2)
ans = max(gcd_list)
print(ans)

### FIXED CODE ###

import fractions


n = int(input())
a = list(map(int, input().split()))
nl = set(range(n))
l = [0]
r = [0]
m = []
for i in nl:
    l.append(fractions.gcd(l[i], a[i]))
    r.append(fractions.gcd(r[i], a[-i-1]))
r.reverse()
for i in nl:
    m.append(fractions.gcd(l[i], r[i+1]))
ans = max(m)
print(ans)
### BUGGY CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
j = 2
res = 1
if N == 1:
  print(P)
  exit()
elif P == 1|N>=40:
  print(1)
  exit()
else:
  while P%(j**N)==0:
    P = P//(j**N)
    res *= j
  j += 1
  if N >= 26:
    print(res)
    exit()
  for f in range(j,i+1,2):
    while P%(f**N) == 0:
      P = P//(f**N)
      res *= f
      
  print(res)
  exit()

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
### BUGGY CODE ###

a = int(input())

ans = 0
for i in range(1,a):
  ans += i
  
print(ans)

### FIXED CODE ###

n = int(input())

print(n*(n-1)//2)
### BUGGY CODE ###

N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())


### FIXED CODE ###

n=int(input())
l=[list(map(int,input().split()))    for _ in range(n)]

def chk():
  v=0
  for j in range(n):
    for i in range(n):
      f=True
      for k in range(n):
        if l[i][j]>l[i][k]+l[k][j]:
          return -1
        if l[i][j]==l[i][k]+l[k][j] and i!=k and k!=j:
          f=False
      if f:v+=l[i][j]
  return v//2
print(chk())
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(q):
    x = list(input())
    if len(x) == 1:
        s.reverse()
    else:
        if x[2] == "1":
            s.insert(0, x[4])
        else:
            s.append(x[4])
print("".join(s))

### FIXED CODE ###

s = list(input())
q = int(input())
left = []
right = []
rev = False
for i in range(q):
    x = list(input())
    if len(x) == 1:
        rev = not rev
        #s.reverse()
    else:
        if (x[2] == "1" and not rev) or (x[2] == "2" and rev):
            left.append(x[4])
        else:
            right.append(x[4])
ans = "".join(left[::-1]) + "".join(s) + "".join(right)
if rev:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n+2,n+2))
for i in range(m):
  s,e=map(int,input().split())
  a[:s+1,e:]+=1
for i in range(q):
  s,e=map(int,input().split())
  print(int(a[s,e]))


### FIXED CODE ###

import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n+2,n+2))
for i in range(m):
  s,e=map(int,input().split())
  a[s,e]+=1

b=a.cumsum(1)
b=np.flipud(b)
b=b.cumsum(0)
b=np.flipud(b)

for i in range(q):
  s,e=map(int,input().split())
  print(int(b[s,e]))
### BUGGY CODE ###

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

dp = [[10**9 for _ in range(W)] for __ in range(H)]

#solve
def dfs(i, j, score, lc):
    if i < H and i >= 0 and j < W and j >= 0:
        if lc == '.' and g[i][j] == '#':
            score += 1
        dp[i][j] = min(dp[i][j], score)

        dfs(i+1, j, score, g[i][j])
        dfs(i, j+1, score, g[i][j])        
    
dfs(0, 0, 0, '.')
print(dp[H-1][W-1])

### FIXED CODE ###

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

dp = [[10**9 for _ in range(W)] for __ in range(H)]

dp[0][0] = 1 if g[0][0] == '#' else 0
d = ([0,1], [1,0])
for ix in range(H):
    for jx in range(W):
        for dx,dy in d:
            ni = ix + dx
            nj = jx + dy
            if ni >= H or nj >= W:
                continue
            add = 0
            if g[ix][jx] == '.' and g[ni][nj] == '#':
                add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)


print(dp[H-1][W-1])
### BUGGY CODE ###

N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()
score = 0
for i in range(N):
    if(T[i]=="r"):
        score +=P
    elif(T[i]=="s"):
        score +=R
    elif(T[i]=="p"):
        score +=S
    if(i <= N-K-1):
        if(T[i]==T[i+K]):
            Tl = list(T)
            Tl[i+K] = "0"
            T = "".join(Tl)
print(score)

### FIXED CODE ###

N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = list(input())
score = 0
for i in range(N):
    if(T[i]=="r"):
        score +=P
    elif(T[i]=="s"):
        score +=R
    elif(T[i]=="p"):
        score +=S
    if(i <= N-K-1):
        if(T[i]==T[i+K]):
            T[i+K] = "0"
print(score)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
  for i in range(1, len(s) + 1):
    dpi = dp[i]
    dpi1 = dp[i - 1]
    si1 = s[i - 1]
    for j in range(1, len(t) + 1):
      k = dpi1[j]
      l = dpi[j - 1] 
      if l > k:
        k = l
      l = dpi1[j - 1] + 1
      if si1 == t[j - 1] and l > k:
        k = l
      dpi[j] = k
  u = []
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      u.append(s[i - 1])
      i -= 1
      j -= 1
  print(''.join(reversed(u)))
main()

### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

from collections import deque
import itertools

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

kukan = 0
kukan_list = deque()
for i in range(k):
    kukan_list.append(p[i])

for i in range(n - k+1):
    if kukan < sum(kukan_list):
        kukan = sum(kukan_list)
    if i+k<n:
        kukan_list.popleft()
        kukan_list.append(p[i+k])


ans = kukan / 2 + 0.5 * k
print(ans)


### FIXED CODE ###

from collections import deque
import itertools
import time

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

kukan = 0
for i in range(k):
    kukan += p[i]

kukan_max = kukan
for i in range(n - k + 1):
    kukan_max = max(kukan_max, kukan)
    if i+k<n:
        kukan += p[i+k]
        kukan -= p[i]
ans = kukan_max / 2 + 0.5 * k
print(ans)
### BUGGY CODE ###

S = input()
L = len(S)
while 1:
    l = len(S)
    S = S.replace('01', '').replace('10', '')
    l2 = len(S)
    if l==l2:
        break
print(L-l2)

### FIXED CODE ###

S = list(input())
L = len(S)
from collections import Counter
c = Counter(S)
one = c['1']
zero = c['0']

print(L-abs(one-zero))
### BUGGY CODE ###

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

b = []

for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(*b)


### FIXED CODE ###

from collections import deque

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

b = deque()


for i in range(n):
    if i % 2 == 0:
        b.appendleft(a[i])
    else:
        b.append(a[i])
if n % 2 == 0:
    b = list(b)[::-1]
print(*b)
### BUGGY CODE ###

n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,n+1):
  c=(c*(n+1-i))%m
  d=(d*i)%m
  if i==a or i==b:
    e+=c*pow(d,m-2,m)%m
f=1
for i in range(n):
  f*=2
  if f>m:
    f%=m
print(f-e-1)

### FIXED CODE ###

n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,b+1):
    c=(c*(n+1-i))%m
    d=(d*i)%m
    if i==a or i==b:
        e+=c*pow(d,m-2,m)%m
print((pow(2,n,m)-e-1)%m)
### BUGGY CODE ###

import numpy as np

N = [int(i) for i in input().split()][0]
string = list(input())
Q = [int(i) for i in input().split()][0]
queries = [[i for i in input().split()] for _ in range(Q)]

tmp = N 
c = 0
while tmp > 0:
  c += 1
  tmp //= 2
N2 = 2**c

seg_trees = np.array([[0 for _ in range(26)] for _ in range(N2*2 -1)])
for n in range(N):
  ind = ord(string[n]) - ord("a")
  seg_trees[N2-1+n][ind] = 1                     

def set_seg_tree(i, seg_trees):
  if i >= N2 -1:
    return seg_trees[i]
  left = 2*i + 1
  right = 2*i + 2
  l_seg = set_seg_tree(left, seg_trees)
  r_seg = set_seg_tree(right, seg_trees)
  seg_trees[i] = l_seg + r_seg
  return seg_trees[i]
set_seg_tree(0, seg_trees)

    
def modify_diff(i, diff,  c, seg_trees):
  i += N2 -1
  seg_trees[i, c] += diff
  while i > 0:
    i = (i - 1)//2
    seg_trees[i, c] = seg_trees[i * 2 + 1, c] + seg_trees[i * 2 + 2, c]

def get_sum(a, b, k, l, r, seg_trees):
  if (b <= l) or (r <= a):
    return 0
  if (a <= l) and (r <= b):
    return seg_trees[k]
  vl = get_sum(a, b, k * 2 + 1, l, (l + r)//2, seg_trees)
  vr = get_sum(a, b, k * 2 + 2, (l + r)//2, r, seg_trees)
  return vl + vr

for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    old = ord(string[i]) - ord("a")
    string[i] = q
    modify_diff(i, 1, pos, seg_trees)
    modify_diff(i, -1, old, seg_trees)
  else:
    l = int(i) - 1
    r = int(q)
    ret = get_sum(l, r, 0, 0, N2, seg_trees)
    print(np.sum(ret > 0))                     


### FIXED CODE ###



N = [int(i) for i in input().split()][0]
string = list(input())
Q = [int(i) for i in input().split()][0]
queries = [[i for i in input().split()] for _ in range(Q)]

tmp = N 
c = 0
while tmp > 0:
  c += 1
  tmp //= 2
N2 = 2**c
offset = N2 - 1

seg_tree = [0 for _ in range(N2*2 -1)]
for n in range(N):
  ind = ord(string[n]) - ord("a")
  seg_tree[offset + n] = 1 << ind

def set_seg_tree(i, seg_trees):
  if i >= N2 -1:
    return seg_trees[i]
  left = 2*i + 1
  right = 2*i + 2
  l_seg = set_seg_tree(left, seg_trees)
  r_seg = set_seg_tree(right, seg_trees)
  seg_trees[i] = l_seg | r_seg
  return seg_trees[i]
set_seg_tree(0, seg_tree)
    
def update(i, c, seg_trees):
  i += offset
  seg_trees[i] = 1 << c
  while i > 0:
    i = (i - 1)//2
    seg_trees[i] = seg_trees[i * 2 + 1] | seg_trees[i * 2 + 2]

def get_sum(a, b, k, l, r, seg_trees):
  if (b <= l) or (r <= a):
    return 0
  if (a <= l) and (r <= b):
    return seg_trees[k]
  vl = get_sum(a, b, k * 2 + 1, l, (l + r)//2, seg_trees)
  vr = get_sum(a, b, k * 2 + 2, (l + r)//2, r, seg_trees)
  return vl | vr

for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    update(i, pos, seg_tree)
  else:
    l = int(i) - 1
    r = int(q)
    ret = get_sum(l, r, 0, 0, N2, seg_tree)
    print(bin(ret).count("1"))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

def main():
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    for i in range(k, n+2):
        ans += len(set(map(sum, list(itertools.combinations(n_li,i)))))

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    MOD = 1000000007
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    while(k <= n+1):
        p = (k - 1) * k / 2
        q = ((n + n - k + 1) * k) / 2

        ans += q - p + 1
        ans %= MOD
        k += 1

    print(int(ans))

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

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
for x in C:
  if x==1:
    break
  count+=x*(x-1)/2
for x in B:
  ans=count-B.count(x)+1
  print(int(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
i=0
dict={}
for x in C:
  count+=x*(x-1)/2
  dict[V[i]]=x
  i+=1
for x in B:
  ans=count-dict[x]+1
  print(int(ans))