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

tmp = [int(i) for i in input().split()]
N,Q = tmp[0],tmp[1]
S = [str(i) for i in input().split()][0]

for i in range(Q):
  L = [int(i) for i in input().split()]
  s = S[L[0]-1:L[1]]

  cnt = 0
  for i in range(0,len(s)):
    if s[i]=='A':
      if i+1!=len(s) and s[i+1]=='C':
        cnt+=1
  print(cnt)

        

### FIXED CODE ###

tmp = [int(i) for i in input().split()]
N,Q = tmp[0],tmp[1]
S = [str(i) for i in input().split()][0]

cnt=0
num=[0]
for i in range(len(S)):
  if S[i-1]=='A':
    if S[i]=='C':
      cnt+=1
  num.append(cnt)

for i in range(Q):
  L = [int(i) for i in input().split()]
  print(num[L[1]]-num[L[0]])
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = False
cnt = Counter()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N = int(input())

x,y,z = 1,1,1

def is_true(x,y,z,i):
    if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
        return True
    return False

loop = int(N ** (1/2))
for i in range(1,N+1):
    count = 0

    if i < 6:
        print(count)
        continue
    for a in range(loop):
        for b in range(loop):
            for c in range(loop):
                X = x+a
                Y = y+b
                Z = z+c
                if is_true(X,Y,Z,i):
                    count += 1
    print(count)


### FIXED CODE ###

N = int(input())

ans = [0 for _ in range(10050)]

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a < 10050:
                ans[a] += 1
for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

def main():
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5)+1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n//i)
      divisors.sort()
      return divisors

  n = int(input())
  l = make_divisors(n)
  ans = make_divisors(n-1)
  for i in l:
    m=n
    if i==1:
      continue
    else:
      while(m%i==0):
        m//=i
    if m==1:
      ans.append(i)
    else:
      if i in make_divisors(m-1):
        ans.append(i)
  ans=set(ans)
  print(len(ans)-1)  

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5)+1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n//i)
      divisors.sort()
      return divisors

  n = int(input())
  l = make_divisors(n)
  ans = make_divisors(n-1)
  for i in l:
    m=n
    if i==1:
      continue
    else:
      while(m%i==0):
        m//=i
    if m==1:
      ans.append(i)
    else:
      if i in make_divisors(m-1):
        ans.append(i)
  ans=set(ans)
  print(len(ans)-1)  

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

# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True

def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))

def main():
  n = INT()
  a = LMAPINT()

  ans = [0] * (max(a) + 1)
  for x in a:
    if ans[x] == 0:
      for j in range(x, max(a)+1, x):
        ans[j] += 1
    else:
      ans[x] += 1

  print(len(list(filter(lambda x: ans[x] == 1, a))))

  
if __name__ == '__main__':
  main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = sorted([(a, 2), (b, 3), (c, 5)],
                     key=lambda x: x[1]//x[0], reverse=True)
        ans = n*d
        stack = [(n, d)]  # remaining, cost
        while stack:
            rem, cost = stack.pop()
            if rem <= 1:
                ans = min(ans, cost)
                continue
            for y, x in ABC:
                if cost+y < ans:
                    stack.append((rem//x, (rem % x)*d+cost+y))
                    stack.append((-(-rem//x), (-rem % x)*d+cost+y))

        ret.append(str(ans))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)
S = sum(A)

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(S+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(S+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(S+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] += D[i][j] * 2
        D[i+1][j+A[i]] += D[i][j]

for i in range(N):
    for j in range(S+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] += D2[i][j]
        D2[i+1][j+A[i]] += D2[i][j]

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)


### FIXED CODE ###

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)

PS = [0 for i in range(N+1)]
for i in range(N):
    PS[i+1] = PS[i] + A[i]

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] = (D[i+1][j] + D[i][j] * 2) % mod
        D[i+1][j+A[i]] = (D[i+1][j+A[i]] + D[i][j]) % mod

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] = (D2[i+1][j] + D2[i][j]) % mod
        D2[i+1][j+A[i]] = (D2[i+1][j+A[i]] + D2[i][j]) % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

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

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
s = input()
chk_0 = []
chk_1 = []
c0 = 0
c1 = 0
if s[0]=='0':
  c0 += 1
else:
  c1 += 1
  chk_0.append(0)
  
for i in range(n-1):
  if s[i]=='0' and s[i+1]=='0':
    c0 += 1
  if s[i]=='0' and s[i+1]=='1':
    chk_0.append(c0)
    c0 = 0
    c1 = 1
  if s[i]=='1' and s[i+1]=='0':
    chk_1.append(c1)
    c0 = 1
    c1 = 0
  if s[i]=='1' and s[i+1]=='1':
    c1 += 1
    
if c0 != 0:
  chk_0.append(c0)
  chk_1.append(0)
elif c1 != 0:
  chk_1.append(c1)
  chk_0.append(0)

if len(chk_0) <= k:
  print(n)
  exit()
  
ab = [x+y for x,y in zip(chk_0,chk_1)]
ab = tuple(ab)
chk_1 = tuple(chk_1)
#print(chk_0,chk_1,ab)
ans = 0
for i in range(len(chk_0)-k+1):
  chk = sum(ab[i:i+k])
  if i >= 1:
    chk += chk_1[i-1]
  ans = max(ans,chk)
print(ans)

### FIXED CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  import numpy as np

  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  chk_1 = tuple(chk_1)
  chk_0 = tuple(chk_0)
  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)
  ab = tuple(ab)
  #print(ab)
  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
move_lst = [int(input()) for _ in range(5)]
time = 0
people_lst = [n] + [0]*5

while people_lst[-1]!=n:
    time += 1

    for i in range(4,-1,-1):
        people = people_lst[i]
        move = move_lst[i]

        people_lst[i] -= min(people, move)
        people_lst[i+1] += min(people, move)

print(time)

### FIXED CODE ###

def need(x,y):
    if x%y==0:
        answer = x//y
    else:
        answer = x//y + 1

    return answer

n = int(input())
move_lst = [int(input()) for _ in range(5)]
min_move = min(move_lst)

answer = need(n, min_move) + 4
print(answer)
### BUGGY CODE ###

import math
from functools import reduce

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

n = int(input())
sum = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            sum += gcd(i, j, k)

print(sum)

### FIXED CODE ###

import math
from functools import reduce

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

n = int(input())
sum = 0

for i in range(1,n+1):
    for j in range(1,i+1):
        for k in range(1,j+1):
            if i == j and j == k:
                sum += gcd(i, j, k)
            elif i == j or j == k or k == i:
                sum += 3 * gcd(i, j, k)
            else:
                sum += 6 * gcd(i, j, k)


print(sum)
### BUGGY CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    memo = [0] * (n + 1)
    for _ in range(k):
        for i, aa in enumerate(a):
            bf = (i - aa if i - aa >= 0 else 0)
            af = (i + aa + 1 if i + aa < n else n)
            memo[bf] += 1
            memo[af] -= 1
        for i in range(n):
            memo[i + 1] += memo[i]
            a[i] = memo[i]
            memo[i] = 0
        if set(a) == {n}:
            break
    print(*a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


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

if __name__ == '__main__':
    NK=input().split(" ")
    N=int(NK[0])
    K=int(NK[1])
    res=1
    n=0
    tem=[1]
    temp=1
    A=list(map(int,input().split(" ")))
    dic={}
    for i in range(0,N):
        dic[i+1]=A[i]
    for i in range(N):
        res=dic[res]
        n+=1
        if (res in tem):
            temp=res
            break
        tem.append(res)
    if K<=N:
        res=1
        for i in range(K):
            res=dic[res]
        print(res)
    else:
        m=0
        tem=[res]
        for i in range(N):
            res=dic[res]
            m+=1
            if (res in tem):
                temp=res
                break
            tem.append(res)
        # if n==N:
        #     res=dic[K%N]
        # else:
        for i in range(0, (K-n)%m):
            res=dic[res]
        print(res)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
test_pos = 1
sub = 0
loop = 0
city = [0 for i in range(n)]
while True:
    test_pos = a[test_pos-1]
    city[test_pos-1] += 1
    sub += 1
    if city[test_pos-1] == 2:
        loop_start = test_pos
        break

while True:
    test_pos = a[test_pos-1]
    loop += 1
    if test_pos == loop_start:
        break
if k > sub:
    k -= sub
    k %= loop
    pos = loop_start
    for i in range(k):
        pos = a[pos-1]
    print(pos)
else:
    pos = 1
    for i in range(k):
        pos = a[pos - 1]
    print(pos)
### BUGGY CODE ###

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

def abs(a):
    if a>=0:
        return a
    else:
        return -a

List=[]

while True:
    n=abs(n-k)
    if n not in List:
        List.append(n)
    else:
        break

print(min(List))

### FIXED CODE ###

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

def abs(a):
    if a>=0:
        return a
    else:
        return -a

m=n%k

while True:
    b=m
    m=abs(m-k)
    if b<=m:
        print(b)
        break
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
import sys

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

que = deque()
dist = [float('inf')] * n
dist[0] = 0
que.append(0)
while que:
    now = que.pop()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            que.append(edge)

# print(dist)
arrow = [0] * n
for i, j in enumerate(dist):
    if i == 0:
        continue
    idxs = []
    for idx in range(n):
        if dist[idx] == j - 1:
            idxs.append(idx)
    for edge in edges[i]:
        if edge in idxs:
            arrow[i] = edge + 1
            break
    if arrow[i] == 0:
        print('No')
        sys.exit()

print('Yes')
for i in range(1, n):
    print(arrow[i])


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque
# import sys
# input = sys.std.readline

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.popleft()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


print('Yes')
for i in range(1, n):
    print(prev[i])
### BUGGY CODE ###

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

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

def waribiki(X,Y):
    return X//(2**Y)

while M>0:
    A.sort(reverse=True)
    A[0] = waribiki(A[0],1)
    M -= 1

print(sum(A))


### FIXED CODE ###

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

def intm(x):
    return int(x)*-1
A = list(map(intm, input().split()))

import heapq

heapq.heapify(A)
while M>0:
    a = -heapq.heappop(A) // 2
    heapq.heappush(A,-a)
    M -= 1
   

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

n = int(input())
left = 0
right = n - 1

for _ in range(20):
    mid = (left + right) // 2
    print(left)
    sl = input()
    if sl[0] == "V":
        quit()
    print(right)
    sr = input()
    if sr[0] == "V":
        quit()
    print(mid)
    sm = input()
    if sm[0] == "V":
        quit()

    if sm - sl + 1 % 2 == 1 and sm != sl:
        sl += 1
        sr = sm - 1
        continue
    if sr - sm + 1 % 2 == 1 and sm != sr:
        sr -= 1
        sl = sm + 1
        continue



### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = []

edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    ab.append((a, b))

K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set([i for i in range(1, K+1)])
    points = Q.popleft()
    #print(points)
    p0, p1 = points

    set1 = set(adjm[p0])
    can_use_labels = labels - (set1)
    use_label = can_use_labels.pop()


    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if adjm[p1][p] == 0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])









### FIXED CODE ###

#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
#AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)
#for val in AB:
for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for color in colors:
    print(color)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()] 

a = np.array(a)
ls = a

st = int(n/2)
for ind in range(st, 0, -1):
    tmp = list(range(2*ind-1, n, ind))
    s = ls[tmp].sum()%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        
print(sum(ls))
ans = np.where(ls==1)[0] + 1
ans = list(ans.astype(str))
print(' '.join(ans))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()] 
ls = a

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n, m, r = map(int, input().split())
*R, = map(int, input().split())
E = [[10**18]*n for i in range(n)]
for i in range(n):
    E[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = E[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])

memo = {}
ALL = 2**r-1
def dfs(state, pos):
    if (state, pos) in memo:
        return memo[state, pos]
    if state == ALL:
        return 0
    res = 10**18
    for i in range(r):
        if state & (1 << i) == 0:
            res = min(res, dfs(state | (1 << i), R[i]-1) + E[pos][R[i]-1])
    memo[state, pos] = res
    return res
print(min(dfs(0, i) for i in range(n)))

### FIXED CODE ###

n, m, r = map(int, input().split())
*R, = map(int, input().split())
E = [[10**18]*n for i in range(n)]
for i in range(n):
    E[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = E[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])

memo = {}
ALL = 2**r-1
def dfs(state, pos):
    if (state, pos) in memo:
        return memo[state, pos]
    if state == ALL:
        return 0
    res = 10**18
    for i in range(r):
        if state & (1 << i) == 0:
            res = min(res, dfs(state | (1 << i), R[i]-1) + E[pos][R[i]-1])
    memo[state, pos] = res
    return res
print(min(dfs(0, i) for i in range(n)))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ans=N
D=[[False]*K for i in range(N+1)]
D[N][0]=True
for i in range(N-1,-1,-1):
    D[i][0]=True
    if A[i]>=K:
        ans=i
        continue
    else:
        for k in range(K):
            if D[i+1][k]:
                if K-A[i]<=k:
                    ans=i
                D[i][k]=True
                if k+A[i]<K:
                    D[i][k+A[i]]=True
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=0
ans=0
for a in A:
    if S+a<K:
        S+=a
        ans+=1
    else:ans=0
print(ans)
### BUGGY CODE ###

n = int(input())
str_list = [input() for i in range(n)]
ans = 0
from collections import Counter
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
    if get_counter(first_word) == get_counter(second_word):
      return 1
    else:
      return 0
for i in range(n):
  for j in range(n-i-1):
    ans += verify_anagrams(str_list[i], str_list[j+i+1])
    
print(ans)

### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)