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

s = input()
k = int(input())
x = []
n = len(s)
for i in range(n):
    for j in range(n-i):
        t = s[j:j+i+1]
        if not t in x:
            x.append(s[j:j+i+1])
x.sort()
print(x[k-1])

### FIXED CODE ###

s = input()
k = int(input())
x = []
n = len(s)
for i in range(k):
    for j in range(n-i):
        t = s[j:j+i+1]
        if not t in x:
            x.append(t)
x.sort()
print(x[k-1])
### BUGGY CODE ###

N,M=map(int,input().split())
ans=1
if M%N==0:
    print(int(M/N))
else:
    
    for i in range(2,int(M/N)+1):
        if (M-((N-1)*i))%i==0:
            ans=i
    print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
ans=0
for i in range(1,10**5):
    if M%i==0:
        a=max(M//i,i)
        b=min(M//i,i)
        if M//a>=N and ans<a:
            ans=a
        if M//b>=N and ans<b:
            ans=b
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    dfrag = 0
    for i in range(N):
        if a[i]%2 == 0 and dfrag == 0 :
            a[i] = a[i]//2
            dfrag = 1
        else:
            a[i] = a[i]*3
    if dfrag == 0:
        break
    cnt += 1
print(cnt)
        

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    dfrag = 0
    for i in range(N):
        if a[i]%2 == 0:
            a[i] = a[i]//2
            dfrag = 1
            cnt += 1
    if dfrag == 0:
        break
print(cnt)
### BUGGY CODE ###

import math
from functools import reduce
import itertools


def gcd(*numbers):
    return reduce(math.gcd, numbers)

x = int(input())
_sum = [gcd(*i) for i in itertools.product(range(1, x+1), repeat=3)]
print(sum(_sum))

### FIXED CODE ###

import math
from itertools import product
 
x = int(input())

s = 0
for a, b, c in product(range(1, x+1), repeat=3):
  s += math.gcd(math.gcd(a, b), c)
print(s)
### BUGGY CODE ###

import bisect

N,M = map(int, input().split())
A_list = list(map(int, input().split()))

A_list = sorted(A_list)
#print(A_list)

for i in range(M):
    val = A_list.pop()//2
    bisect.insort_left(A_list, val)

print(sum(A_list))

### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A_list = list(map(int, input().split()))
for i in range(N):
    A_list[i] *= -1

heapq.heapify(A_list)

for i in range(M):
    heapq.heappush(A_list, ((heapq.heappop(A_list) * -1 )// 2) * -1)

print(sum(A_list) * -1)
### BUGGY CODE ###

a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = []
for r in br:
    cr.append(ar.count(r))
cr.sort()
count = 0
for i in range(len(br)-b):
    count += cr[i]
print(count)

### FIXED CODE ###

import collections
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = collections.Counter(ar)
n = len(br) - b
dr = []
for v in cr.values():
    dr.append(v)
dr.sort()
count = 0
for i in range(n):
    count += dr[i]
print(count)
### BUGGY CODE ###

X=int(input())

Xkon=X**0.2
if(Xkon==int(Xkon)):
    print(str(0)+" "+str(int(-Xkon)))
    #break
else:
    m=-(10**2)
    while m<0:
        A=X+(m**5)
        check=(A**0.2)
        # print(type(check))
        if(type(check)!=complex):
            if(check==int(check)):
                AnsA=-check
                AnsB=-m
                print(str(int(AnsB))+" "+str(int(AnsA)))
                break
            else:
                pass
        else:
            m=m+1
    n=1
    while n<10**2:
        A=X+(n**5)
        check=(A**0.2)
        if(check==int(check)):
            AnsA=check
            AnsB=n
            print(str(int(AnsB)+" "+str(int(-AnsA))))
            break
        else:
            n=n+1


### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
### BUGGY CODE ###

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

i = 0
A = 7 % K
flag = True
while flag:
    if A == 0:
        print(i+1)
        flag = False
    i += 1
    A = (10 * A + 7) % K



### FIXED CODE ###

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

A = 0
for i in range(K):
    A = (10 * A + 7) % K
    if A == 0:
        print(i+1)
        break
### BUGGY CODE ###

import math
N = int(input())
counts = [0] * N
for x in range(1, N, 1):
    # if x**2>(int(math.sqrt(N))+1):
    # break
    for y in range(1, N, 1):
        # if y**2 > (int(math.sqrt(N))+1):
        # break
        for z in range(1, N, 1):
            # if z**2 > (int(math.sqrt(N))+1):
            # break
            i = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
            # print(x,y,z,i)
            if i <= N:
                counts[i - 1] += 1
for k in counts:
    print(k)

### FIXED CODE ###

import math
N = int(input())
counts = [0] * N
for x in range(1, N, 1):
    if x**2>N:
        break
    for y in range(1, N, 1):
        if y**2 > N:
            break
        for z in range(1, N, 1):
            if z**2 > N:
                break
            i = (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (z * x)
            # print(x,y,z,i)
            if i <= N:
                counts[i - 1] += 1
for k in counts:
    print(k)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

def retInd(A, k):
    for i in range(len(A)):
        if A[i]-1== k:
            return i

for i in range(N):
    print(retInd(A,i)+1, end=" ")


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

AB = [(A[i],i) for i in range(N)]

AB.sort(key = lambda x:x[0])

B = [AB[i][1]+1 for i in range(N)]

ans = " ".join(map(str,B))
print(ans)
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))

# c(i)をiのaにおける個数とする
res = 0

for i in set(a):
    # aにおけるiの個数
    ci = a.count(i)
    # c(i) > iの時は c(i) = i になるまで取り除くしかない
    if ci > i:
        res += ci - i
    # c(i) < iの時は，ci個取り除く
    elif ci < i:
        res += ci

print(res)




### FIXED CODE ###

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

res = 0

num = [0]*(N)
cnt = [0]*(N)

for i in range(N):
    if A[i] > N:
        res += 1
    else:
        cnt[A[i]-1] += 1

for i in range(N):
    if cnt[i] < i+1:
        res += cnt[i]
    else:
        res += cnt[i] - (i+1)

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

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

Asum=[0]
Bsum=[0]
for i, a in enumerate(A):
  Asum.append(Asum[i]+a)
for i, b in enumerate(B):
  Bsum.append(Bsum[i]+b)

ans = 0 
for a, asum in enumerate(Asum):
  if asum > K:
    break
  b=M
  while Bsum[b]>K - asum:
    b-=1
  ans = max(ans, a+b)
print(ans)
 


### FIXED CODE ###

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

Asum=[0]
Bsum=[0]
for i, a in enumerate(A):
  Asum.append(Asum[i]+a)
for i, b in enumerate(B):
  Bsum.append(Bsum[i]+b)

ans, b = 0, M
for a, asum in enumerate(Asum):
  if asum > K:
    break
  while Bsum[b]>K - asum:
    b-=1
  ans = max(ans, a+b)
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

a.sort(reverse=True)
sol = 3 ** n % modulo
s = sum(a)
half_s = s / 2


dp = [Counter([0])]
for i, ai in enumerate(a):
    dp.append(dp[i] + dp[i])
    for key, item in dp[-2].items():
        dp[-1][key + ai] += dp[-2][key]
        # if dp[-1][key + ai] > modulo:
        #    dp[-1][key + ai] -= modulo

sol -= 3 * sum(item for key, item in dp[-1].items() if key >= half_s)

if s % 2 == 0:
    dp = [Counter([0])]
    for i, ai in enumerate(a):
        dp.append(dp[-1].copy())
        for key, item in dp[-2].items():
            new_key = key + ai
            if new_key <= int(half_s):
                dp[-1][new_key] += dp[-2][key]
                # if dp[-1][new_key] > modulo:
                #    dp[-1][new_key] -= modulo

    sol += 3 * dp[-1][half_s]
sol %= modulo

print(sol)
# print(dp[-1])


### FIXED CODE ###

import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]
        dp %= modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)
### BUGGY CODE ###

N=int(input())
A=[]
B=[[] for i in range(N+1)]
B[0].append("")
for i in range(N):
    A.append(chr(97+i))
    for j in B[i]:
        for k in A:
            B[i+1].append(j+k)
for i in B[N]:
    count=ord("a")
    yes=1
    for j in range(N):
        if ord(i[j])<=count+1:
            count=max(count,ord(i[j]))
        else:
            yes=0
    if yes==1:
        print(i)

### FIXED CODE ###

N=int(input())
A=[]
B=[[] for i in range(N+1)]
B[0].append("")
for i in range(N):
    A.append(chr(97+i))
    for j in B[i]:
        for k in A:
            B[i+1].append(j+k)
for i in B[N]:
    count=ord("a")
    yes=1
    for j in range(N):
        if ord(i[j])<=count+1:
            count=max(count,ord(i[j]))
        else:
            yes=0
            continue;
    if yes==1:
        print(i)
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
fship = []
for i in range(M):
    x,y = map(int,input().split())
    if x>y:
        x,y = y,x
    if [x,y] not in fship:
        fship.append([x-1,y-1])
fship.sort(key = lambda x: x[0])
graph = [[] for _ in range(N)]
for i in fship:
    graph[i[0]].append(i[1])

dist = [0]*N

ans = 0
for i in range(N):
    if dist[i]:
        continue
    dist[i] = 1
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i]:
                continue
            dist[i] = 1
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

seen = [None]*N
ans = -1

for i in range(N):
    if seen[i]:
        continue
    seen[i] = True
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if seen[i]:
                continue
            seen[i] = True
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)
### BUGGY CODE ###

n = int(input())
lis = []
for _ in range(n):
    x = int(input())
    if x in lis:
        lis.remove(x)
    else:
        lis.append(x)

print(len(lis))

### FIXED CODE ###

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

import collections

ans = 0
lis = collections.Counter(lis)

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

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

s = input()

al = [chr(ord('a') + i) for i in range(26)]
c = dict()
for _al in al:
    c[_al] = [0]

for i in range(len(s)):
    for _al in al:
        if _al == s[i]:
            c[_al].append(c[_al][-1] + 1)
        else:
            c[_al].append(c[_al][-1])

f = False
for _al in al:
    tmp = []
    curmin = []
    for i in range(len(c[_al])):
        cur = c[_al][i] * 2 - i

        tmp.append(cur)
        if i == 0:
            curmin.append(cur)
        else:
            curmin.append(min(cur, curmin[-1]))

        if i >= 2:
            if tmp[-1] > curmin[-3]:
                y = i
                f = True

                for j in range(len(tmp)):
                    if tmp[j] == curmin[-3]:
                        x = j + 1
                        break

                if f:
                    break

    if f:
        break

if f:
    print(' '.join([str(x), str(y)]))
else:
    print('-1 -1')


### FIXED CODE ###

s = input()

al = [chr(ord('a') + i) for i in range(26)]
c = dict()
for _al in al:
    c[_al] = [0]

for i in range(len(s)):
    for _al in al:
        if _al == s[i]:
            c[_al].append(c[_al][-1] + 1)
        else:
            c[_al].append(c[_al][-1])

f = False
for _al in al:
    tmp = []
    curmin = []
    for i in range(len(c[_al])):
        cur = c[_al][i] * 2 - i

        tmp.append(cur)
        if i == 0:
            curmin.append(cur)
        else:
            curmin.append(min(cur, curmin[-1]))

        if i >= 2 and tmp[-1] > curmin[-3]:
            y = i
            f = True
            break

    if f:
        break

if f:
    for j in range(len(tmp)):
        if tmp[j] == curmin[-3]:
            x = j + 1
            break
    print(' '.join([str(x), str(y)]))
else:
    print('-1 -1')
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
ans= max(a.count(a[0]) + a.count(a[0]+1),a.count(a[-1]) + a.count(a[-1]-1))

set_a = set(a)
for i in set_a:
  counter = a.count(i-1) + a.count(i)+a.count(i+1)
  if ans < counter:
    ans = counter
  
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
cand = collections.Counter(a)
cand_list = cand.most_common(len(set(a)))
ans = 0
for i in range(len(set(a))):
  num = cand_list[i][0]
  count = cand[num] + cand[num + 1] + cand[num - 1]
  ans = max(ans,count)

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

def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()


### FIXED CODE ###

def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
s=input()
place=tuple(tuple(int(i) for i in input().split()) for _ in range(q))
for i in place:
    print(s.count("AC",i[0]-1,i[1]))

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

n, m = [int(v) for v in input().split()]
values = sorted([int(v) for v in input().split()], reverse=True)

def insert(arr, val):
    left, right = 0, len(arr) - 1
    while right - left > 1:
        index = (left + right) // 2
        if val <= arr[index]:
            left = index
        else:
            right = index
    return arr[0:(left + 1)] + [val] + arr[(left + 1):]

for _ in range(m):
    v = values[0] >> 1
    values = insert(values[1:], v)

print(sum(values))

### FIXED CODE ###

from heapq import heappush, heappop, heapify

n, m = [int(v) for v in input().split()]
values = [-int(v) for v in input().split()]
heapify(values)

for _ in range(m):
    v = -((-heappop(values)) >> 1)
    heappush(values, v)

print(-sum(values))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
for i in a:
  if i == 0:
    sum = 0
    break
  sum *= i
  if sum > 1000000000000000000:
    sum = -1
print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if sorted(a)[0] == 0:
  sum = 0
else:
  sum = 1
if sum == 1:
  for i in a:
    sum *= i
    if sum > 1000000000000000000:
      sum = -1
      break
print(sum)
### BUGGY CODE ###

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

for i in range(m):
    a_l[0] //= 2
    max_price = a_l[0]
    for j in range(1,n):
        if a_l[j] >= max_price:
            a_l[j] //2
        else:
            break
    a_l.sort(reverse=True)

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a_l = list(map(int, input().split()))
a_l.sort(reverse=True)

m_count = 0
while True:
    max_price = a_l[0]//2
    for j in range(n):
        if a_l[j] >= max_price:
            a_l[j] //= 2
            m_count += 1
            if m_count == m:
                break
        else:
            break
        if m_count == m:
            break
    a_l.sort(reverse=True)
    if m_count == m:
        break

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)
### BUGGY CODE ###

n,w = map(int,input().split())
item = [list(map(int,input().split())) for i in range(n)]

dp = [[0]*(w+1) for i in range(n+1)]

for i in range(1,n+1):
  for j in range(1,w+1):
    if item[i-1][0] <= j:
      dp[i][j] = max(dp[i-1][j-item[i-1][0]]+item[i-1][1],dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][w])


### FIXED CODE ###

n,w = map(int,input().split())
item = [list(map(int,input().split())) for i in range(n)]

dp = [[0]*(w+1) for i in range(n+1)]

for i in range(1,n+1):
  for j in range(1,w+1):
    if item[i-1][0] <= j:
      dp[i][j] = max(dp[i-1][j-item[i-1][0]]+item[i-1][1],dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][w])
### BUGGY CODE ###

def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    queries.append([r-1,l-1,i])
  ans=[0]*q
  queries.sort()
  queries.append([10*20,0,0])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    S = input().strip()
    
    if p == 2 or p == 5:
        count = 0
        digits = '02468' if p == 2 else '05'
        for i, x in enumerate(S, 1):
            if x in digits:
                count += i
        print(count)
    else:
        counter = [0]*p
        for i in range(n-1, -1, -1):
            counter[int(S[i:]) % p] += 1
        print(counter[0] + sum(i*(i-1)//2 for i in counter))

main()

### FIXED CODE ###

n, p = map(int, input().split())
if p in (2, 5):
  c = 0
  for i, x in enumerate(map(int, input()[::-1])):
    if x % p == 0:
      c += n-i
  print(c)
else:
  c = [0] * p
  y = 0
  t = 1
  for x in map(int, input()[::-1]):
    y = (y + t*x) % p
    c[y] += 1
    t = (10 * t) % p
  print(sum(i * (i-1) // 2 for i in c) + c[0])
### BUGGY CODE ###

N=int(input())
ls=[]
for i in range(N):
    s=input()
    dc={}
    for ss in s:
        if ss in dc.keys():
            dc[ss]+=1
        else:
            dc[ss]=1
    ls.append(dc)
ans=0
#print(ls)
for i in range(N):
    for j in range(i+1,N):
        if ls[i]==ls[j]:
            ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
#ls=[]
ds={}
for i in range(N):
    s=input()
    #dc={}
    #for ss in s:#sを辞書化
        #if ss in dc.keys():
            #dc[ss]+=1
        #else:
            #dc[ss]=1
    #s=sorted(s)
    s="".join(sorted(s))#sを比較できる形へ

    #ls.append(dc)
    #if dc in ds:#文字列がそれぞれ何個重複しているかわかる
    #_TypeError: unhashable type: 'dict'
    #_辞書のキーはイミュータブルでなければならない
    #    ds[dc]+=1
    #else:
    #    ds[dc]=1"""

    if s in ds:
        ds[s]+=1
    else:
        ds[s]=1

ans=0
for i in ds:
    ans+=ds[i]*(ds[i]-1)/2
#print(ls)
#for i in range(N):
    #for j in range(i+1,N):
        #if ls[i]==ls[j]:
        #    ans+=1

    #dc=ls[i]
    #del ls[i]
    #if dc in ls:
print(int(ans))
### BUGGY CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( power(2, ( H // htgcd)) + power(2, (W // wtgcd)) - 3)
p += power(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)


### FIXED CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = pow( 2, ( H // htgcd) ,mod ) +pow( 2, (W // wtgcd) , mod) - 3
p += pow(2,fractions.gcd( H // htgcd , W // wtgcd),mod)

#print (p,n)

ans = pow( p , n , mod )

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

import numpy as np

def main():
    n, k = map(int, input().split())
    p = np.array(list(map(int, input().split())))
    e = np.array([(k + (p[j-1:j+k-1].sum())) / 2. for j in range(1, n-k+2)])
    ans = e.max()
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    e = [(p[j-1]+1)/2.for j in range(1, n+1)]
    s = [sum(e[:k])]
    for i in range(1, n-k+1):
        s.append(s[-1]-e[i-1]+e[k+i-1])
    ans = max(s)
    print(ans)

if __name__ == "__main__":
    main()