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

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)

### FIXED CODE ###

#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
dp[0][0] = 0

for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)
### BUGGY CODE ###

S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = [0] * 2019
a[0] = 1
T = 0
r = 1
c = 0
for i in range(N-1, -1, -1):
    T = T + h[i] * r
    q = T % 2019
    r = r * 10
    c += a[q]
    a[q] += 1
print(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
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [[int(_) for _ in input().split()] for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

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

import numpy as np
goukei = 0

N = int(input()) * (-1)
Ai = list(map(int, input().split()))
array_Ai = np.array(Ai)
number = np.array([j for j in range(0, N, -1)])
new_ai = number + array_Ai
for i in range(len(Ai)):
    goukei += np.count_nonzero(new_ai == (-Ai[i] - i))
print(goukei)

### FIXED CODE ###

import collections
goukei = 0

N = int(input())
Ai = list(map(int, input().split()))
number = [j for j in range(1, N+1, 1)]
plus_Ai = [x + y for (x, y) in zip(Ai, number)]
minus_Ai = [x - y for (y, x) in zip(Ai, number)]
c = collections.Counter(plus_Ai)

for i in minus_Ai:
    goukei += c[i]
print(goukei)
### BUGGY CODE ###

s=input()
s=list(s)
n=len(s)
if n==1:
    if s[0]=='?':
        print('D')
    else:
        print(s[0])
else:
    for i in range(0,n):
        if i!=(n-1):
            if s[i]=='?' and s[i+1]=='P':
                s[i]='D'
            elif (s[i]=='?'):
                s[i]='P'
        else:
            if s[i]=='?':
                s[i]='D'
    ans=""
    for h in s:
        ans+=h
    print(ans)

### FIXED CODE ###

s=input()
n=len(s)
for i in range(0,n):
    if(s[i]=='?'):
        print('D',end="")
    else:
        print(s[i],end="")
### BUGGY CODE ###

S = list(input())
Q = int(input())
Qry = [input().split() for i in range(Q)]
for q in Qry:
    if q[0] == '1':
        #S = [S[-1]] + S[1:-1] + [S[0]]
        S = S[::-1]
    else:
        if q[1] == '1':
            S = [q[2]] + S
        else:
            S += [q[2]]
print(*S, sep='')


### FIXED CODE ###

S = input()
Q = int(input())
qry = [input().split() for _ in range(Q)]
A = ''
B = ''
oq = 0
even = True
for q in qry:
    if q[0] == '1':
        even = not even
        if oq == '1':
            continue
    else:
        if even:
            if q[1] == '1':
                A = q[2] + A
            else:
                B += q[2]
        else:
            if q[1] == '1':
                B += q[2]
            else:
                A = q[2] + A
    oq = q

if even:
    print(A+S+B)
else:
    print(B[::-1]+S[::-1]+A[::-1])
### BUGGY CODE ###

n,m,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(k)]
friend=[[]for _ in range(n)]
block=[[]for _ in range(n)]
for a,b in ab:
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
for c,d in cd:
  block[c-1].append(d-1)
  block[d-1].append(c-1)
# 友達連結内でかつ友達でもブロックでもない。
# 友達連結グループわけ
ans=[0]*n
seen=[0]*n
while 0 in seen:
  member=[]
  t=seen.index(0)
  todo=[t]
  seen[t]=1
  while todo:
    t=todo.pop()
    member.append(t)
    f=friend[t]
    for fi in f:
      if seen[fi]==0:
        todo.append(fi)
        seen[fi]=1
  for m in member:
    ans[m]=len([mi for mi in member if mi not in block[m]])-len(friend[m])-1
print(' '.join(map(str,ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  gf=[[]for _ in range(n)]
  for a,b in ab:
    gf[a-1].append(b-1)
    gf[b-1].append(a-1)
  gb=[[]for _ in range(n)]
  for c,d in cd:
    gb[c-1].append(d-1)
    gb[d-1].append(c-1)
  seen=[0]*n
  ans=[0]*n
  for i in range(n):
    c=set([i])
    if seen[i]==0:
      todo=[i]
      while todo:
        e=todo.pop()
        l=gf[e]
        for li in l:
          if seen[li]==0:
            todo.append(li)
            seen[li]=1
            c.add(li)
      base=len(c)-1
      for ci in c:
        ans[ci]=base
        for fb in gb[ci]+gf[ci]:
          if fb in c:
            ans[ci]-=1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

summ=sum(a)
num=[a.count(i) for i in range(100001)]
for i in range(q):
    b,c=map(int,input().split())
    b_num=num[b]
    num[c] += b_num
    num[b]=0
    summ +=(c-b)*b_num
    print(summ)

### FIXED CODE ###

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

summ=sum(a)
num=[0 for i in range(10**5+1)]
for i in range(n):
    num[a[i]] += 1
for i in range(q):
    b,c=map(int,input().split())
    b_num=num[b]
    num[c] += b_num
    num[b]=0
    summ +=(c-b)*b_num
    print(summ)
### BUGGY CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()
### BUGGY CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

### FIXED CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]


def memo_dp(dp_list, i, j, k):
    if (i < 0) or (j < 0) or (k < 0):
        return 0
    if i + j + k == 0:
        return dp_list[i][j][k]
    else:
        pt1 = i * memo_dp(dp_list, i - 1, j, k)
        pt2 = j * memo_dp(dp_list, i + 1, j - 1, k)
        pt3 = k * memo_dp(dp_list, i, j + 1, k - 1)
        dp_list[i][j][k] = (n + pt1 + pt2 + pt3) / (i + j + k)
        return dp_list[i][j][k]


dp = [[[0.0] * (301) for _ in range(301)] for _ in range(301)]

ans = memo_dp(dp, p, q, r)
print(ans)


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    a = []
    b = []
    c = []
    for i in range(M):
        a_, b_ = map(int, input().split())
        a.append(a_)
        b.append(b_)
        c_ = np.array(list(map(int, input().split()))) - 1
        c.append(c_)

    INF = int(1e10)
    dp = [INF] * (1 << N)
    dp[0] = 0

    for i in range(M):
        key = 0
        for j in range(b[i]):
            key |= (1 << c[i][j])
        for bits in range(1 << N):
            dp[bits | key] = min(dp[bits | key], dp[bits] + a[i])
    
    if dp[(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    INF = int(1e10)
    dp = [INF] * (1 << N)
    dp[0] = 0
    bits = set()
    bits.add(0)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        key = 0
        for t in c:
            key += 1 << (t - 1)
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        bits |= add_bits
    
    if dp[(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

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

n=int(input())
slis=[]
orislis=[]
clis=[]
for i in range(n):
	a=sorted(list(input()))
	slis.append(a)
	if a not in orislis:
		orislis.append(a)
for i in orislis:
	a=0
	for j in slis:
		if i==j:
			a+=1
	clis.append(a)
ans=0
for i in clis:
	b=(i*(i-1))/2
	ans+=b
print(int(ans))

### FIXED CODE ###

from collections import Counter
n=int(input())
slis=[]
for i in range(n):
	s=sorted(list(input()))
	slis.append(s)
ctr=Counter()
ans=0
for s in slis:
	a="".join(s)
	if a in ctr:
		ans+=ctr[a]
	ctr[a] +=1
print(ans)
### BUGGY CODE ###

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

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

#Aをソート
A.sort()

for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        if min(A) < c:
            A[0] = c
            A.sort()

print(sum(A))

### FIXED CODE ###

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

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

A_dict = {}

#Aをhash
for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1


for i in range(M):
    b, c = map(int, input().split())
    if c in A_dict:
        A_dict[c] += b
    else:
        A_dict[c] = b

A_dict = sorted(A_dict.items(), key=lambda x: -x[0])


card = 0
ans = 0
for i in A_dict:
    if card == N:
        break
    elif card + i[1] > N:
        ans += (N - card) * i[0]
        break
    else:
        ans += i[0] * i[1]
        card += i[1]
print(ans)
### BUGGY CODE ###

import collections

n = int(input())
OddList = []
EvenList = []
list = input()

for i in range(n):
    if i%2==1:
        OddList.append(int(list.split(" ")[i]))
    else:
        EvenList.append(int(list.split(" ")[i]))

Odd = collections.Counter(OddList)
Even = collections.Counter(EvenList)

if (Odd.most_common()[0][0] == Even.most_common()[0][0]):
    if (len(Odd) == 1)and(len(Even) == 1):
        print(len(OddList))
    elif (len(Odd) == 1)and(len(Even) > 1):
        print(len(EvenList) - Even.most_common()[1][0])
    elif (len(Odd) > 1)and(len(Even) == 1):
        print(len(OddList) - Odd.most_common()[1][0])
    else:
        if Odd.most_common()[1][1] >= Even.most_common()[1][1]:
            print(len(OddList) - Odd.most_common()[1][1] + len(EvenList) - Even.most_common()[0][1])
        else:
            print(len(OddList) - Odd.most_common()[0][1] + len(EvenList) - Even.most_common()[1][1])
else:
    print(len(OddList)+len(EvenList)-Odd.most_common()[0][1]-Even.most_common()[0][1])


### FIXED CODE ###

import collections

def answer(list,n):
    Even = collections.Counter(list[::2]).most_common(2)
    Odd = collections.Counter(list[1::2]).most_common(2)

    if Even[0][0] != Odd[0][0]:
        return n - Even[0][1] - Odd[0][1]
    else:
        if len(Even) == 1 or len(Odd) == 1:
            return n // 2
        else:
            return n - max(Even[0][1]+Odd[1][1],Even[1][1]+Odd[0][1])

N = int(input())
list = input().split(" ")
print(answer(list,N))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 %mod

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

depth = [-1]*n
ko = [[] for _ in range(n)]
ko_all = [0 for _ in range(n)]


def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            ko[v].append(w)
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1)
    tmp %=mod
    for w in ko[i]:
        tmp -= pow2[ko_all[w]+1]-1
        tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 %mod

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

depth = [-1]*n
ko_all = [0 for _ in range(n)]
ko_only =[0 for _ in range(n)]

def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1
            ko_only[v] += pow2[ko_all[w]+1]-1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1) - ko_only[i]
    tmp %=mod
    cnt += tmp
    cnt %= mod

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# 番兵法 (#を外周に設置する)
visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))

# #の位置をqに格納
q = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

# dx,dyを使用せずにBFS 
# 定数倍改善
ans = -1
while q:
  qq = []
  # 新たに#となった地点をqqに格納
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  ans += 1
  
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = min(i, k)
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))


### FIXED CODE ###

def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    visited = set()
    tmp = 0
    for k in range(K):
        if P[i] in visited: break
        tmp += C[P[i]]
        i = P[i]
        visited.add(i)
        ans = max(ans, tmp)
    if tmp < 0: continue
    l = len(visited)
    rem = K-l
    d,m = divmod(rem,l)
    if m==0 and d > 0:
        m = l
        d -= 1
    tmp *= (d+1)
    for k in range(m):
        tmp += C[P[i]]
        i = P[i]
        ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float('inf')
for i in range(N):
    s = 0
    j = i
    for k in range(K):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)
        if j==i: break
    d,m = divmod(K, k+1)
    if m==0 and d>1:
        m = k+1
        d -= 1
    s *= d
    ans = max(ans, s)
    for k in range(m):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)

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

N = int(input())
s = []
for i in range(N):
    word = sorted(input())
    s.append(word)
moji = ""
temp = []
cnt = 0
for i in range(N):
    moji = ""
    for x in s[i]:
        moji += x
    temp.append(moji)
for i in range(len(temp)):
    for j in range(i+1,len(temp)):
        if temp[i] == temp[j]:
            cnt+=1
print(cnt)

### FIXED CODE ###

import collections

N = int(input())
s = ["".join(sorted(input())) for i in range(N)]
c = collections.Counter(s)
cnt = 0
for i in set(s):
    n = c[i]
    cnt += n*(n-1)//2
print(cnt)