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

import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = [] 

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print(*ret, sep="\n")

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

n,m=map(int,input().split())
s=0
for i in range(m):
  l,r=map(int,input().split())
  temp=range(l,r+1)
  if i==0:
    s=set(temp)
  else:
    s&=set(temp)

print(len(s))

### FIXED CODE ###

n,m=map(int,input().split())
li=[list(map(int,input().split())) for i in range(m)]
maxl=0
minr=1000000
for i in range(m):
  maxl=max(li[i][0],maxl)
  minr=min(minr, li[i][1])
if maxl<=minr:
  print(minr-maxl+1)
else:
  print(0)
### BUGGY CODE ###

n = int(input())
lst = [[-1]*n for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int, input().split())
        lst[i][x-1] = y

item = [i for i in range(2**n)]
def bitka(n):
    honest = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            honest.append(item[j])  # フラグが立っていたら bag に果物を詰める
    return honest

def check(honest, lst):
    for i in honest:
        for j in range(n):
            if lst[i][j]==1 and (j not in honest):
                return False
            elif lst[i][j]==0 and (j in honest):
                return False
    return True

ans = 0
for i in range(2**n):
    if check(bitka(i),lst)==True:
        ans = max(ans, len(bitka(i)))
print(ans)


### FIXED CODE ###

n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])

# ms =  [2, 2, 2]
# say = [[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    for j in range(n):
        for k in range(ms[j]):
            if nowbit[j]==1:
                if say[j][k][1] != nowbit[say[j][k][0]-1]:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(nowbit))

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

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

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for _ in range(n)]
inf = float('inf')
dp = [inf] * (h + 1)
dp[0] = 0
for i, (a, b) in enumerate(ab):
    for j in range(h):
        if j + a >= h:
            dp[-1] = min(dp[-1], dp[j] + b)
        else:
            dp[j + a] = min(dp[j + a], dp[j] + b)
print(dp[-1])


### FIXED CODE ###

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

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [inf] * (2 * 10 ** 4)
dp[0] = 0
for a, b in ab:
    for n in range(h):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

ans = min(dp[h:])
print(ans)
### BUGGY CODE ###

N, WW = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

inf = float('inf')
dp = [[inf] * (10 ** 5 + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(10 ** 5 + 1):
        dp[i + 1][j] = dp[i][j]
        if j - V[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - V[i]] + W[i])

ans = -1

for i in range(10 ** 5 + 1):
    if dp[N][i] <= WW:
        ans = i

print(ans)


### FIXED CODE ###

N, WW = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

inf = float('inf')
dp = [[inf] * (10 ** 5 + 1) for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(10 ** 5 + 1):
        dp[i + 1][j] = dp[i][j]
        if j - V[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - V[i]] + W[i])

ans = -1

for i in range(10 ** 5 + 1):
    if dp[N][i] <= WW:
        ans = i

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

N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N-2):
  for j in range(i+1,N): 
    ans += sum([1 for k in L[j+1:] if abs(L[j]-L[i]) < k < L[j]+L[i]])
print(ans)
  


### FIXED CODE ###

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

def f(j, max1, max2):
    L_temp = L[j+1:]
    # print("max1 = ", max1, "max2 = ", max2, L_temp)
    dif = max1 - max2
    left = -1
    right = len(L_temp)
    while right - left != 1:
        temp = (left+right)//2
        if dif < L_temp[temp]:
            left = temp
        else:
            right = temp
    if left != N:
        return left+1
    else:
        return left


ans = 0
max1 = 0
max2 = 0
for i in range(N):
    max1 = L[i]
    for j in range(i+1, N-1):
        max2 = L[j]
        ans += f(j, max1, max2)
        # print("ans = ", ans)
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(n+1)
l[0]=1
l[1]=a[0]
for i in range(2,n+1):
  l[i]=l[i-1]*a[i-1]
#print(l)
grade=[0]*(n-k+1)
for i in range(n-k+1):
  grade[i]=l[i+k]//l[i]
#print(grade)
for i in range(n-k):
  if grade[i]<grade[i+1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(n-k)
for i in range(n-k):
    l[i]=a[i+k]/a[i]
for i in range(n-k):
    if l[i]>1:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, p = list(map(int, input().split()))
s = input()

count = 0
for i in range(n):
  for j in range(n-i):
    if(int(s[i:i+j+1]) % p == 0):
      count += 1
print(count)


### FIXED CODE ###

import numpy as np

def a():
  n, p = list(map(int, input().split()))
  num = [int(s) for s in input()]
  
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(num[-i]%p == 0):
        count += n-i+1
    print(count)
    return
  
  counts = np.zeros(p)
  tmp = 0
  tens = 1
  for i in range(1,n+1):
    tmp = (tens*num[-i] + tmp) % p
    counts[tmp] += 1
    tens = (tens*10)%p
  ret = int(counts[0] + sum(counts*(counts-1)//2))
  print(ret)
  return
a()
### BUGGY CODE ###

import numpy as np

N = int(input())
S = []
for i in range(N):
  S.append(list(input()))

S = np.array(S)

s = list('abcdefghijklmnopqrstuvwxyz')

T = np.zeros([N, 26])

for i, a in enumerate(s):
  T[:, i] = np.sum(S == a, axis=1)


c = 0
for i in range(N):
  c += np.sum(np.prod(T[i] == T[i+1:], axis=1))
  
print(c)

### FIXED CODE ###

def number(x):
  return int((1 + (1 + 8*x)**0.5) / 2)


N = int(input())
d = {}
for i in range(N):
  s = ''.join(sorted(input()))
  if s in d.keys():
    d[s] += number(d[s])
  else:
    d[s] = 0


print(sum(d.values()))
### BUGGY CODE ###

import sys

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_attend_stu = []
for i in range(1, Num + 1):
    for l in range(0, Num):
        if list_stu_Num[l] == str(i):
            list_attend_stu.append(l + 1)
print(*list_attend_stu)


### FIXED CODE ###

import sys
import numpy as np

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
print(*np.argsort(list_stu_Num_int) + 1)
### BUGGY CODE ###

#####segfunc######
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(n):
        seg[i + num - 1] = set(init_val[i])
        # built
    for i in range(num - 2, -1, -1):
        seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])


def update(k, x):
    k += num - 1
    seg[k] = set(x)
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = set()

n = int(input())
S = input().strip()
Q = int(input())

num = 2 ** (n - 1).bit_length()
seg = [set()] * 2 * num

init(S)


for _ in range(Q):
    a, b, c = [x for x in input().split()]
    if a == "1":
        update(int(b) - 1, c)
    else:
        print(len(query(int(b) - 1, int(c))))


### FIXED CODE ###

#####segfunc######
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(n):
        seg[i + num - 1] = set(init_val[i])
        # built
    for i in range(num - 2, -1, -1):
        seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])


def update(k, x):
    k += num - 1
    seg[k] = set(x)
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = set()

n = int(input())
S = input().strip()
Q = int(input())

num = 2 ** (n - 1).bit_length()
seg = [set()] * 2 * num

init(S)


for _ in range(Q):
    a, b, c = [x for x in input().split()]
    if a == "1":
        update(int(b) - 1, c)
    else:
        print(len(query(int(b) - 1, int(c))))
### BUGGY CODE ###

from collections import defaultdict

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

pre = [1<<i for i in range(n)]
bitcnt = [0]*(1<<n)
bitcnt[1] = 1
for i in range(1<<(n-1)):
    bitcnt[2*i] = bitcnt[i]
    bitcnt[2*i+1] = bitcnt[i]+1

DP = [defaultdict(lambda : float("inf")) for i in range(n)]

for i in range(n):
    DP[i][1<<i] = 0

for i in range(n-1):
    nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
    for j in range(n):
        last = a[j] if (i-j)%2 == 0 else b[j]
        for state, cost in DP[j].items():
            for to in range(n):
                if state>>to&1:
                    continue
                nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                if last > nlast:
                    continue
                nstate = state + pre[to]
                ncost = cost
                ncost += bitcnt[state>>to]
                nxt[to][nstate] = min(nxt[to][nstate], ncost)
    DP = nxt
mask = (1<<n)-1
ans = float("inf")
for i in range(n):
    ans = min(ans, DP[i][mask])
if ans == float("inf"):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    if s[(nstate, nlast)] <= ncost:
                        continue
                    s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = ncost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

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

from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            nxt_lis = lis
        else:
            nxt_lis = list(lis)
        if idx == len(nxt_lis):
            nxt_lis.append(A[cur])
        else:
            nxt_lis[idx] = A[cur]
        ans[cur] = len(nxt_lis)
        nxt_override = (cur != 0)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
            nxt_override = False
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


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

from heapq import nlargest
N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    bit = 1<<i
    for j in range(1<<N):
        if j & bit:
            f[j] = nlargest(2, f[j]+f[j^bit])
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

for _ in range(INT()):
    a, b, c, d = MAP()
    if a < b or d < b:
        No()
        continue
    stock = a
    S = set()
    while 1:
        if stock >= b * 2:
            stock = (a - c) % b + c
            if stock <= c:
                stock += d
        if stock < b:
            No()
            break
        if stock in S:
            Yes()
            break
        else:
            S.add(stock)
        stock -= b
        if stock <= c:
            stock += d


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

for _ in range(INT()):
    a, b, c, d = MAP()

    # そもそも無理
    if a < b or d < b:
        No()
        continue
    
    # b個減ってd個増える繰り返しなので、このgより細かく値が動くことはない
    g = gcd(b, d)

    # cより大きくてb未満が存在するかどうか
    mn = bisearch_min(-INF, INF, lambda m: a%g + g*m > c)
    mx = bisearch_max(-INF, INF, lambda m: a%g + g*m < b)
    if mn > mx:
        Yes()
    else:
        No()
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                for ei in e[__]:
                    nxt.add(ei)
            items = nxt
        items -= {i}
        e3[i] = list(items)

    ans = -1

    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            nxt |= set(e3[ci])
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


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

from collections import deque
from copy import copy

r, c = map(int, input().split())
map_ = [[c == "#" for c in input().strip()] for _ in range(r)]

queue = deque([(i, j) for j in range(c) for i in range(r) if map_[i][j]])

def bfs(maze, queue):
    depth = 0
    while True:
        depth += 1
        nextqueue = deque()
        while queue:
            posr, posc = queue.popleft()
            for dr, dc in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < r and 0 <= nextc < c and not maze[nextr][nextc]:
                    maze[nextr][nextc] = True
                    nextqueue.append((nextr, nextc))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return depth - 1


print(bfs(map_, queue))

### FIXED CODE ###

from collections import deque
from copy import copy

row, column = map(int, input().split())
map_ = [[c == "#" for c in input().strip()] for _ in range(row)]

queue = deque([(i, j) for j in range(column) for i in range(row) if map_[i][j]])

def bfs(maze, queue):
    depth = 0
    while True:
        depth += 1
        nextqueue = deque()
        while queue:
            posr, posc = queue.popleft()
            for dr, dc in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < row and 0 <= nextc < column and not maze[nextr][nextc]:
                    maze[nextr][nextc] = True
                    nextqueue.append((nextr, nextc))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return depth - 1

print(bfs(map_, queue))
### BUGGY CODE ###



H = int(input())
S = []
for _ in range(H):
	S.append(input()) 

L = []

for i in range(0,len(S)):
	L.append(sorted(S[i]))

counter = 0
  
for i in range(0,len(L)):
	for j in range(i+1,len(L)):
		if L[i] == L[j]:
			counter += 1

print(counter)

### FIXED CODE ###

H = int(input())
S = []
for _ in range(H):
	S.append(input()) 

L = []

for i in range(0,len(S)):
	L.append(sorted(S[i]))

for i in range(0,len(L)):
	L[i] = ",".join(L[i])

dicL = dict()
answer = 0

for l in L:
	if l in dicL:
		dicL[l] += 1
		answer += dicL[l]
	else:
		dicL[l] = 0
		
print(answer)