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

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
counter_comb = list(map(lambda y: int(y*(y-1)/2), counter.values()))

for i in range(n):
    z = counter[A[i]]
    if z>0:
        print(sum(counter_comb)-(z-1))
    else:
        print(sum(counter_comb))
    

### FIXED CODE ###

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
counter_comb = list(map(lambda y: int(y*(y-1)/2), counter.values()))
sum_counter = sum(counter_comb)
for i in range(n):
    z = counter[A[i]]
    if z>0:
        print(sum_counter-(z-1))
    else:
        print(sum_counter)
### BUGGY CODE ###

import math

n = int(input())
x = list(map(int, input().split()))
mod = 10 ** 9 + 7

fac = math.factorial(n - 1)


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


res = 0
for i in range(n - 1):
    d = x[n - 1] - x[i]
    res += (d * fac * pow(i + 1, mod - 2)) % mod

print(res % mod)


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
mod = 10 ** 9 + 7


fac = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, n + 2):
    fac.append((fac[i - 1] * i) % mod)

d = 0
f = 1
res = 0
for i in range(n - 1):
    d = x[n - 1] - x[i]
    res += (d * fac[n - 1] * pow(i + 1, mod - 2)) % mod

print(res % mod)
### BUGGY CODE ###

n,y=map(int,input().split())
for i in range(n+1):
    for r in range(n+1):
        for x in range(n+1):
            total = 10000*i+5000*r+1000*x
            if total==y and i+r+x==n:
                print(i,r,x)
                exit(0)
print(-1,-1,-1)
                

### FIXED CODE ###

n,y=map(int,input().split())
for i in range(n+1):
    for r in range(n+1-i):
        x=n-r-i
        total = 10000*i+5000*r+1000*x
        if total==y and i+r+x==n:
            print(i,r,x)
            exit(0)
print(-1,-1,-1)
### BUGGY CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
xy_l = []
for i in range(1 << N):
    xy = 0
    for j in range(N):
        if (i >> j) & 1:
            xy += V[j] - C[j]
    xy_l.append(xy)
print(max(xy_l))

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
cnt = 0
""""
xy_l = []
for i in range(1 << N):
    xy = 0
    for j in range(N):
        if (i >> j) & 1:
            xy += V[j] - C[j]
            print(xy)
    xy_l.append(xy)
print(max(xy_l))
"""

for i in range(N):
    if V[i] > C[i]:
        cnt += V[i] - C[i]
print(cnt)
### BUGGY CODE ###

pattern = int(input())

xs = []
ys = []
hs = []

for _ in range(pattern):
    x, y, h = map(int, input().split(' '))
    xs.append(x)
    ys.append(y)
    hs.append(h)

correct = 0

max_h = max(hs) + 200

for Cx in range(101):
    for Cy in range(101):
        for H in range(max(hs), max_h):
            for x, y, h in zip(xs, ys, hs):
                if abs(x-Cx) + abs(y-Cy) == abs(h-H):
                    correct += 1
                    if correct == len(xs) and max(hs) <= H:
                        print(Cx, Cy, H)
                        quit()
                else:
                    correct = 0
                    continue

### FIXED CODE ###

N = int(input())

coords = [list(map(int, input().split(' '))) for _ in range(N)]

coords.sort(key=lambda x: x[2], reverse=True)

# 全探索
def search():
    for Cx in range(101):
        for Cy in range(101):
            x, y, h = tuple(coords[0])
            H = h + abs(Cx - x) + abs(Cy - y)
            for x, y, h in coords:
                if max(H - abs(Cx - x) - abs(Cy - y), 0) != h:
                    break
            else:
                return Cx, Cy, H

x, y, h = search()
print("{} {} {}".format(x, y, h))
### BUGGY CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

def h(i,j,k):
  if dp[i][j][k] is None:
    dp[i][j][k] =((i*h(i-1,j  ,k  ) if i else 0)+
                  (j*h(i+1,j-1,k  ) if j else 0)+
                  (k*h(i  ,j+1,k-1) if k else 0)+
                  N)/(i+j+k)
  return dp[i][j][k]

print(h(A,B,C))

### FIXED CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

for k in range(C+1):
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[i][j][k] =((i*dp[i-1][j][k] if i else 0)+
                      (j*dp[i+1][j-1][k] if j else 0)+
                      (k*dp[i][j+1][k-1] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass

print(dp[A][B][C])
### BUGGY CODE ###

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

for ele in a:
    ans = ans * ele

if ans > max:
    print('-1')
else:
    print(ans)


### FIXED CODE ###

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

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

for ele in a:
    ans = ans * ele
    if ans > max:
        print('-1')
        exit()

print(ans)
### 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())))

ans=0
for a in A:
    for i in range(len(B)):
        if a < B[i]:
            for j in range(len(C)):
                if B[i] < C[j]:
                    ans += len(C)-j
                    break    

print(ans)

### FIXED 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 b in B:
    a = bisect.bisect_left(A,b)
    c = n - bisect.bisect_right(C,b)
    ans += a*c

print(ans)
### 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,p = list(map(int, input().split()))
s = input()

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        a = int(s[n-1-i])
        if a % p == 0: ans += n-i

else:
    b = [int(s[n-1-i:]) % p for i in range(n)] + [0]
    d = Counter(b)

    for dd in d.values():
        ans += dd*(dd-1)//2

print(ans)











### 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,p = list(map(int, input().split()))
s = input()

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        a = int(s[n-1-i])
        if a % p == 0: ans += n-i

else:
    d = {0: 1}
    c = 0
    for i in range(n):
        c += (pow(10, i, p)*int(s[n-1-i])) % p
        c %= p
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1

    for dd in d.values():
        ans += dd*(dd-1)//2

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

s = str(input())
k = int(input())

dic = {}
for i in range(1,len(s)+1):
    for j in range(len(s)+1-i):
        dic.setdefault(s[j:j+i],0)
        dic[s[j:j+i]] += 1
sort_dic = sorted(dic)
print(sort_dic[k-1])

### FIXED CODE ###

s = str(input())
k = int(input())

dic = {}
for i in range(1,6):
    for j in range(len(s)+1-i):
        dic.setdefault(s[j:j+i],0)
        dic[s[j:j+i]] += 1
sort_dic = sorted(dic)
print(sort_dic[k-1])
### BUGGY CODE ###

S=input()
count=0

while S.count('01')!=0 or S.count('10')!=0:
    S=S.replace('01','X')
    S=S.replace('10','X')
    count += 2*S.count('X')
    S=S.replace('X','')
    
print(count)

### FIXED CODE ###

S=input()
count=0

A=S.count('0')
B=S.count('1')

print(A+B-abs(A-B))
### BUGGY CODE ###

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

for i in range(n -1):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

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

if len(a) == len(set(a)):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
 
n = ni()
a = [int(ns()) for i in range(n)]
pushed = []

next_b = 1
count = 0
while True:
  if next_b == 2:
    break
  count += 1
  next_b = a[next_b-1]
  if next_b in pushed:
    count = -1
    break
  pushed.append(next_b)
  
print(count)
  

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
 
n = ni()
a = [int(ns()) for i in range(n)]
pushed = {}

next_b = 1
count = 0
for _ in range(0,n):
  if next_b == 2:
    break
  count += 1
  next_b = a[next_b-1]
  if pushed.get(next_b) != None:
    count = -1
    break
  pushed[next_b] = True
  
if count == n:
  count = -1
print(count)
### BUGGY CODE ###

import heapq

dic = {}
n, m = map(int, input().split())
for _ in range(n):
  a, b = map(int, input().split())
  if dic.get(a) is not None:
    dic[a].append(-b)
  else:
    dic[a] = [-b,]

ans = 0
bite = []
for i in range(1, m+1):
  if dic.get(i) is not None:
    bite = bite + dic[i]
  if len(bite) > 0:
    heapq.heapify(bite)
    ans += heapq.heappop(bite)
print(ans*-1)

### FIXED CODE ###

import heapq

dic = {}
n, m = map(int, input().split())
for _ in range(n):
  a, b = map(int, input().split())
  if dic.get(a) is not None:
    dic[a].append(-b)
  else:
    dic[a] = [-b,]

ans = 0
bite = []
for i in range(1, m+1):
  if dic.get(i) is not None:
    #bite = bite + dic[i]
    for val in dic[i]:
      heapq.heappush(bite, val)
  if len(bite) > 0:
    #heapq.heapify(bite)
    ans += heapq.heappop(bite)
print(ans*-1)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        dp[i] = min(costs)

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        costs = []
        for j in range(1, k+1):
            if j > i:
                break
            if abs(h[i-j]-h[i]) == 0:
                costs.append(dp[i-j])
                break
            costs.append(dp[i-j] + abs(h[i-j]-h[i]))

        # if i == 3:
        #     print(costs)
        dp[i] = min(costs)

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

import collections as co
S=input()
Q=int(input())
count=0
back=str()
front=str()
judge=True
for i in range(Q):
    a=list(map(str,input().split()))   
    if  int(a[0])==1:
        if judge==True:
            judge=False
        else:
            judge=True
    elif int(a[0])==2 and int(a[1])==1:
        if judge==True:
            front=a[2]+front
        if judge==False:
            back=back+a[2]
    else:
        if judge==True:
            back=back+a[2]
        if judge==False:
            front=a[2]+front
    a.clear
if judge==True:
    S=front+S+back
if judge==False:
    S=S[::-1]
    back=back[::-1]
    front=front[::-1]
    S=back+S+front
print(S)

### FIXED CODE ###

import collections as co
S=input()
Q=int(input())
count=0
back=str()
front=str()
judge=True
for i in range(Q):
    a=list(map(str,input().split()))   
    if  int(a[0])==1:
        if judge==True:
            judge=False
        else:
            judge=True
    elif int(a[0])==2 and int(a[1])==1:
        if judge==True:
            front=a[2]+front
        if judge==False:
            back=back+a[2]
    else:
        if judge==True:
            back=back+a[2]
        if judge==False:
            front=a[2]+front
    a.clear
if judge==True:
    S=front+S+back
if judge==False:
    S=front+S+back
    S=S[::-1]
print(S)
### BUGGY CODE ###

from bisect import bisect_left

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)
    ans = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L[j+1:], a + L[j])
            ans += k

    print(ans)

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left

def main():
    N = int(input())
    L = list(map(int, input().split()))
    
    L = sorted(L)
    ans = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L[j+1:], a + L[j])
            ans += k

    print(ans)

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

K,S=map(int,input().split())

count=0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        count+=1
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
r=K+1
count=0
for x in range(r):
  if x>S:
    break
  for y in range(r):
    if y>S:
      break
    z=S-x-y
    if 0<=z and z<=K:
      count+=1
print(count)
### BUGGY CODE ###

from itertools import accumulate
n, K = map(int,input().split())
A = list(map(int,input().split()))
b = [0 for _ in range(n+1)]

for _ in range(min(50, K)):
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    ac = list(accumulate(b))
    A = ac
    b = [0 for _ in range(n+1)]
    
    if sum(ac) == n*n:
        print(*ac[:-1])
        exit()

print(*ac[:-1])

### FIXED CODE ###

n, K = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(K):
    b = [0 for _ in range(n+1)]
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]

    A = b[:-1]
    if all(a == n for a in A):
        break
print(*A)
### BUGGY CODE ###

S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = []
T = 0
r = 1
for i in range(N-1, -1, -1):
    T = T + h[i] * r
    r = r * 10
    a.append(T%2019)
b = []
for j in range(0, N):
    if a[j] not in b:
        b.append(a[j])
c = 0
for k in range(0, len(b)):
    d = a.count(b[k])
    c += d * (d-1) /2
c += a.count(0)
print(int(c))

### FIXED CODE ###

S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1

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

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()
S_ = 'ST'+S
while S_ != S:
    S = S_
    S_ = S.replace('ST', '', 1)

print(len(S))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()
'''
f_cnt = b_cnt = 0
for m in S:
    if m != 'T':
        break
    f_cnt += 1

for m in S[::-1]:
    if m != 'S':
        break
    b_cnt += 1
print(max(f_cnt, b_cnt) * 2)
'''
s_cnt = 0
for m in S:
    if m == 'S':
        s_cnt += 1
    elif m == 'T' and s_cnt > 0:
        s_cnt -= 1

print(2*s_cnt)
### BUGGY CODE ###

n,m=map(int,input().split())
IN,OUT,p=[],[],0
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:IN.append(b)
    if b==n:OUT.append(a)
for i in IN:
    if i in OUT:p=1
if p==1:print("POSSIBLE")
else:print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
IN,OUT={},{}
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in OUT:
            print("POSSIBLE")
            exit()
        else:IN[b]=1
    if b==n:
        if a in IN:
            print("POSSIBLE")
            exit()
        else:OUT[a]=1
print("IMPOSSIBLE")
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            S = Query[4] + S
        else:
            S = S + Query[4]

if reverse == True:
    S = S[::-1]


print(S)
print('\n')


### FIXED CODE ###

S = input()
Q = int(input())
front = ''
end = ''
reverse = False
for i in range(Q):
    Query = input()
    if Query[0] == '1':
        reverse = not reverse 
    else:
        if (Query[2] == '1' and reverse == False) or (Query[2] == '2' and reverse == True):
            front = Query[4] + front
        else:
            end = end + Query[4]

S = front + S + end
if reverse == True:
    S = S[::-1]


print(S)
print('\n')
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(0,M):
    m=max(A)
    index=A.index(m)
    A[index]=m//2
print(sum(A))

### FIXED CODE ###

import heapq

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

# D - Knapsack Queries on a tree

n = int(input())
vw = [tuple(map(int, input().split())) for _ in range(n)]
q = int(input())
vl = [tuple(map(int, input().split())) for _ in range(q)]

tables = [None] * n

def dfs(u, table):
    "u: vertex; table: weight -> max value"
    if u >= n:
        return
    val, wgt = vw[u]
    tables[u] = table.copy()
    for w in table:
        v1 = table[w] + val
        v2 = table[w + wgt] if w + wgt in table else 0
        tables[u][w + wgt] = max(v1, v2)
    dfs(u * 2 + 1, tables[u])
    dfs(u * 2 + 2, tables[u])

dfs(0, {0: 0})

for v, l in vl:
    if l not in tables[v - 1]:
        tables[v - 1][l] = 0

for v in range(n):
    m = 0
    for k in sorted(tables[v].keys()):
        m = max(m, tables[v][k])
        tables[v][k] = m

for v, l in vl:
    print(tables[v - 1][l])


### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

S = input()

def ctoi(c):
    return ord(c) - ord('a')

masks = [1<<k for k in range(26)]
cums = [0]
for c in S:
    cums.append(cums[-1] ^ masks[ctoi(c)])
if cums[-1] == 0:
    print(1)
    exit()

dp = {0:0}
for i,b in enumerate(cums):
    for m in masks:
        msk = b^m
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

### FIXED CODE ###

def ctoi(c):
    return ord(c) - ord('a')

def solve(s):
    masks = [1<<k for k in range(26)]
    cums = [0]
    for c in s:
        cums.append(cums[-1] ^ masks[ctoi(c)])
    if cums[-1] == 0:
        print(1)
        exit()

    dp = {0:0}
    for b in cums:
        for m in masks:
            msk = b^m
            if msk in dp:
                if b in dp:
                    dp[b] = min(dp[b], dp[msk]+1)
                else:
                    dp[b] = dp[msk]+1
    return dp[cums[-1]]

print(solve(input()))
### BUGGY CODE ###

import time

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

INF = 10 ** 9

magic = []

for i in range(n):
    a, b = map(int, input().split())
    magic.append((a, b))

# t = time.time()

magic.sort(reverse=True, key=lambda x: x[0])

dp = [INF] * (h + 10 ** 4)
dp[0] = 0
c = 0
for a, b in magic:
    for i in range(h):
        if dp[i] != INF:
            tmp = dp[i] + b
            c += 1
            if dp[i + a] > tmp:
                dp[i + a] = tmp

ans = min(dp[h:])

print(ans)
# print(time.time() - t)

### FIXED CODE ###

def main():
    inf = 10**9
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))
 
 
main()