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

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)


### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

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


#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs

	
def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	s=np.array([int(c) for c in s])
	s0=s.copy()
	ans=0
	lenS=len(s)
	for i0 in range(lenS):
		r=s%p
		ans+=(r==0).sum()
		if i0<lenS-1:
			s0=s0[1:]
			s10=r[:-1]
			s=s10*10+s0
	print(ans)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)
	

### FIXED CODE ###


#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		r=0
		modD=int(1%p)
		for i0 in range(len(s)-1,-1,-1):
			
			sub=s[i0:i0+1]
			sub=int(sub)
			sub=r+sub*modD
			r=sub%p
			ans+=numP0[r]
			numP0[r]+=1
			modD=int((modD*10)%p)
	print(ans)
		
	

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

from collections import Counter as C
n=int(input())
s=['']*n
for i in range(n):
  s[i]=C(sorted(list(input())))
ans=0
for i in range(n):
  for j in range(i,n):
    if s[i]==s[j] and not i==j:
      ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
dict={}
ans=0
for i in range(n):
  s=''.join(sorted(input()))
  dict[s]=dict.get(s,-1)+1
  ans+=dict[s]
print(ans)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

for i in range(K):
  ta = B+C
  tb = A+C
  tc = A+B
  A = ta
  B = tb
  C = tc
  if abs(A-B) > 10**18:
    print('Unfair')
    exit()
print(A-B)

### FIXED CODE ###

A,B,C,K = map(int,input().split())

if abs(B-A) > 10**18:
  print('Unfair')
else:
  if K % 2 == 0:
    print(A-B)
  else:
    print(B-A)
### BUGGY CODE ###


def Dictionary(b):
    a=list(input().split())
    if(a[0] == "insert"):
        b.append(a[1])
    elif(a[0] == "find"):
        if(a[1] in b):
            print("yes")
        else:
            print("no")

if __name__ == "__main__":
    n=int(input())
    b=[]
    for i in range(n):
        Dictionary(b)
    
            
                


### FIXED CODE ###

import sys
d={}
input()
for i in sys.stdin:
    if i[0] == "i":
        d[i[7:]]=0
    else:
        if i[5:] in d:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N = int(input())
    S = input()

    ans = 0
    for x in range(0, 1000):
        t = "{:0=3}".format(x)
        j = 0
        for i in range(N):
            if t[j] == S[i]:
                j += 1
            if j == 3:
                ans += 1
                break

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N = int(input())
    S = input()

    ans = 0
    for x in range(0, 1000):
        t = "{:0=3}".format(x)
        j = 0
        for i in range(N):
            if t[j] == S[i]:
                j += 1
            if j == 3:
                ans += 1
                break

    print(ans)


def main():
    solve()


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

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

s = s.replace("R", "0").replace("G", "1").replace("B", "2")

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for j in range(i+1, n):
    if 2*j - i >= n:
      break;
    else:
      a = int(s[i])
      b = int(s[j])
      c = int(s[2*j-i])
      if noteq(a, b, c):
        ans -= 1
    
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for d in range(n):
    j = i + d
    k = j + d
    if k >= n:
      break;
    else:
      a = s[i]
      b = s[j]
      c = s[k]
      if noteq(a, b, c):
        ans -= 1
    
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
n = int(readline())
a = []
for i in range(n):
    ai = readline().strip()
    idx = ai.find(".")
    if idx >= 0:
        v = len(ai)-idx-1
        ai = int(ai.replace(".",""))
    else:
        ai = int(ai)
        v = 0
    c2 = c5 = 0

    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #print(ai,c2,c5)
    a.append((c2,c5,v))

ans = 0
for i in range(n):
    c,d,v = a[i]
    for j in range(i+1,n):
        e,f,w = a[j]
        if c+e >= v+w and d+f >= v+w:
            ans += 1

print(ans)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
#C = [0]*n
#D = [0]*n

"""
dp[i][j] = 2,5で何回割れるか
"""
dp = [[0]*20 for _ in range(50)]

M = 10**9
for i in range(n):
    bi = float(readline())
    ai = int(round(bi*M))
    
    c2=c5=0    
    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #C[i] = c2
    #D[i] = c5
    dp[c2][c5] += 1
    #print(c2,c5)

"""
dp[i][j] = 2,5で何回割れるか(50*20)
"""
acc = [dp[i][:] for i in range(50)]
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i != 49:
            acc[i][j] += acc[i+1][j] 
        if j != 19:
            acc[i][j] += acc[i][j+1] 
        if i != 49 and j != 19:
            acc[i][j] -= acc[i+1][j+1] 
            
ans = 0
for i in range(50):
    for j in range(20):
        ans += dp[i][j] * acc[max(0,18-i)][max(0,18-j)]
        if i >= 9 and j >= 9: ans -= dp[i][j]

#print(ans)
print(ans//2)
### BUGGY CODE ###

a = input().split()
b = input().split()

exlist = []

for i in range(int(a[0])):
    exlist.append((1 + int(b[i]))/2)

ans = 0

for i in range(int(a[0])-int(a[1])+1):
    sum = 0
    for j in range(int(a[1])):
        sum += exlist[i+j]
    if ans < sum:
        ans = sum

print(ans)

### FIXED CODE ###

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

sum = 0
ans = 0

for i in range(a[0]):
    sum += (1 + b[i])/2
    if i > a[1]-1:
        sum -= (1 + b[i-a[1]])/2
    if ans < sum:
        ans = sum

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

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


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

    max_l = max(L)

    ans = 0

    for a in range(N):

        for b in range(a+1, N):
            if L[a] >= L[b] + max_l:
                continue

            for c in range(b+1, N):
                if L[a] < L[b] + L[c] and L[b] < L[c] + L[a] and L[c] < L[a] + L[b]:
                    ans += 1
                else:
                    break

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import bisect
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce, reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


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

    ans = 0

    for a in range(N):

        for b in range(a+1, N-1):
            ab = L[a] + L[b]
            i = bisect.bisect_left(L, ab) - 1

            ans += i - b

    print(ans)


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

x, y, z, k = map(int, input().split())
cs = list(map(int, input().split()))
bs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
# flag = True
minlist = 0
for a in a_s:
    if minlist >= (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist >= (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if minlist >= abc:
                break
            if i >= k:
            # if flag and i >= k:
                list.sort(reverse=True)
                minlist = list[k]
                # flag = False

            list.append(abc)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in[1,0],[-1,0],[0,1],[0,-1]:
  for z in range(k):
   i,j=s+y*~z,t+x*~z
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import heapq
x, y, z, k = map(int, input().split())

a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

abc = [[[0 for _ in range(z)] for __ in range(y)] for ___ in range(x)]

stu = [[-a[0]-b[0]-c[0], 0,0,0]]
heapq.heapify(stu)
while k > 0:
    out_p, n, m, l = heapq.heappop(stu)
    if n+1<x and abc[n+1][m][l]==0:
        abc[n+1][m][l]=1
        heapq.heappush(stu, [-a[n+1]-b[m]-c[l], n+1, m, l])
    if m+1<y and abc[n][m+1][l]==0:
        abc[n][m+1][l]=1
        heapq.heappush(stu, [-a[n]-b[m+1]-c[l], n, m+1, l])
    if l+1<z and abc[n][m][l+1]==0:
        abc[n][m][l+1]=1
        heapq.heappush(stu, [-a[n]-b[m]-c[l+1], n, m, l+1])
    print(-out_p)
    k -= 1

### FIXED CODE ###

import heapq
import sys
x, y, z, k = map(int, input().split())

a, b, c = (sorted(map(int, sys.stdin.readline().split()), reverse=True) for _ in range(3))

abc = {(0,0,0)}

stu = [[-a[0]-b[0]-c[0], 0,0,0]]
heapq.heapify(stu)
result = []
while k > 0:
    out_p, n, m, l = heapq.heappop(stu)
    if n+1<x and not((n+1,m,l) in abc):
        abc.add((n+1,m,l))
        heapq.heappush(stu, [-a[n+1]-b[m]-c[l], n+1, m, l])
    if m+1<y and not((n,m+1,l) in abc):
        abc.add((n,m+1,l))
        heapq.heappush(stu, [-a[n]-b[m+1]-c[l], n, m+1, l])
    if l+1<z and not((n,m,l+1) in abc):
        abc.add((n,m,l+1))
        heapq.heappush(stu, [-a[n]-b[m]-c[l+1], n, m, l+1])
    result.append(-out_p)
    k -= 1
result.sort(reverse=True)
for i in result:
    print(i)
### BUGGY CODE ###

INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))
### BUGGY CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要

#メイン文
d = [INF] * N #最短距離を記録しておくリスト
# prev = [-1] * N
negative = [False] * N
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while count < N - 1:
        count += 1
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
    
    count = 0
    while count < N:
        count += 1
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] == INF:
                continue
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                negative[e[1]] = True
            if negative[e[0]]:
                negative[e[1]] = True


#呼び出しスタート地点を入れる
shortest_path(1)
if negative[N - 1]:
    print (-1)
    # print (d)
    exit()
# print (d)
else:
    print (max(0, -d[N - 1]))

### FIXED CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == 2 * N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

print (max(0, -d[N - 1]))
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
S = ["".join(sorted(input())) for i in range(N)]

S_ = S[:]
S_ = set(S_)

a = [int(combinations_count(S.count(i), 2)) for i in S_ if not S.count(i) == 1]

print(sum(a))


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
existed = {}
c = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))

  if sorted_s in existed:
    c += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(c)
### BUGGY CODE ###

class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True

H, W = list(map(int, input().split()))
S = list(input() for _ in range(H))
uf = UnionFind(H*W)

def get(h, w):
    return h * W + w

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if (h + dh) >= H or (w + dw) >= W:
                continue
            if S[h][w] != S[h+dh][w+dw]:
                uf.union(get(h, w), get(h+dh, w+dw))


from itertools import product

C1 = [(h, w) for h, w in product(range(H), range(W)) if S[h][w] == "."]
C2 = [(h, w) for h, w in product(range(H), range(W)) if S[h][w] == "#"]

ans = 0
for h1, w1 in C1:
    for h2, w2 in C2:
        if uf.same(get(h1, w1), get(h2, w2)):
            ans += 1
print(ans)


### FIXED CODE ###

class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True

H, W = list(map(int, input().split()))
S = list(input() for _ in range(H))
uf = UnionFind(H*W)

def get(h, w):
    return h * W + w

for h in range(H):
    for w in range(W):        
        for dh, dw in zip((0, 1), (1, 0)):
            if (h + dh) >= H or (w + dw) >= W:
                continue
            if S[h][w] != S[h+dh][w+dw]:
                uf.union(get(h, w), get(h+dh, w+dw))


from itertools import product

C1 = []
C2 = []

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            C1.append((h, w))
        else:
            C2.append((h, w))

white = [0] * (H * W)
black = [0] * (H * W)

for h in range(H):
    for w in range(W):
        n = get(h, w)
        par = uf.find(n)
        # print(h, w, n, par)
        if par < 0:
            par = n
        if S[h][w] == ".":
            white[par] += 1
        else:
            black[par] += 1
            
ans = 0
# print(white)
# print(black)
for h in range(H):
    for w in range(W):
        n = get(h, w)
        ans += white[n] * black[n]
print(ans)
### BUGGY CODE ###

import sys

a, b, c, d = list(input().split())
a = int(a)
b = int(b)
c = int(c)
d = int(d)

# A: 5 B: 10 C: 3 D: 7
ans = 0
for i in range(b-a+1):
    n = i + a
    if n % c != 0 and n % d != 0:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
import fractions as fl

a, b, c, d = input().split()
a = int(a)
b = int(b)
c = int(c)
d = int(d)

#全体の個数
all = b - a + 1
#cとdの最小公倍数
e = c * d // fl.gcd(c, d)
# a以下でcまたはdで割れる個数
r1 = (a-1) // c + (a-1) // d - (a-1) // e
# b以下でcまたはdで割れる個数
r2 = b // c + b // d - b // e
ans = all - (r2 - r1)
print(ans)