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

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[[0,0,i] for i in range(Q)]
for i in range(Q):
    lr[i][0],lr[i][1]=map(int1,input().split())
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i in range(N):
    if lastap[a[i]]!=-1:
        b.add(lastap[a[i]],lastap[a[i]]+1,-1)
    b.add(i,i+1,1)
    lastap[a[i]]=i
    while r==i:
        ans[j]=b.sum(l,r+1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
for x in ans:
    print(x)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[[0,0,i] for i in range(Q)]
for i in range(Q):
    lr[i][0],lr[i][1]=map(int1,input().split())
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i,x in enumerate(a):
    if lastap[x]!=-1:
        b.add(lastap[x],lastap[x]+1,-1)
    b.add(i,i+1,1)
    lastap[x]=i
    while r==i:
        ans[j]=b.sum(l,r+1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
for x in ans:
    print(x)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
cnt = 0
for i in range(n):
    num_c = c[i]
    b_idx = bisect_left(b,num_c)
    for j in range(b_idx):
        num_b = b[j]
        a_idx = bisect_left(a, num_b)
        cnt += a_idx
print(cnt)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
len_c = len(c)
total = 0
for num in b:
    idx_a = bisect_left(a, num)
    idx_c = bisect_right(c, num)
    cnt = idx_a * (len_c - idx_c)
    total += cnt
print(total)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))


gcds = []
for i in range(len(A)):
    A[:i] + A[i+1:]
    gcds.append(reduce(gcd, A[:i]+A[i+1:]))

print(max(gcds))


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))

from itertools import accumulate

gcds = []
left_all_gcd = list(accumulate(A, gcd))
right_all_gcd = list(accumulate(A[::-1], gcd))
for i in range(len(A)):
    if i == 0:
        gcds.append(right_all_gcd[-2])
    if i == len(A)-1:
        gcds.append(left_all_gcd[-2])
    else:
        hoge = [left_all_gcd[i-1]] + [right_all_gcd[-i-1]]
        gcds.append(gcd(left_all_gcd[i-1], right_all_gcd[-i-2]))

print(max(gcds))
### BUGGY CODE ###

a, b = map(int, input().split())
ans = []

for i in range(a,b+1):
    ans.append(i)

if ans.count(0) == 1:
    print("Zero")
    exit()

c = 0

for i in ans:
    if i < 0:
        c += 1

if c % 2 != 0:
    print("Negative")
else:
    print("Positive")


### FIXED CODE ###

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


if a < 0 and b > 0:
    print("Zero")

elif a > 0:
    print("Positive")

elif b < 0 and a < 0:
    if (b - a + 1) % 2 != 0:
        print("Negative")
    else:
        print("Positive")
### BUGGY CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict
from heapq import *

vs = defaultdict(set)
ws = defaultdict(int)

for a, b in AB:
    vs[a].add(b)
    ws[b] += 1

for i in range(1, N + 1):
    if not ws[i]:
        root = i
        break

h = []

heappush(h, (0, root, 0))

rs = [-1] * (N + 1) 
ls = [0] * (N + 1)

rs[root] = 0

#print(vs)

while h:
    l, n, parent = heappop(h)
    #print("*", l, n, parent)
    for m in vs[n]:
        if ls[m] > l - 1:
            #print("+", l -1, m, n)
            heappush(h, (l - 1, m, n))
            ls[m] = l - 1
            rs[m] = n

for i in range(1, N + 1):
    print(rs[i])


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)
### BUGGY CODE ###

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

for i in range(1,n+1):
	ans = 0
	for j in range(n-1):
		if a[j] == i:
			ans += 1
		else:
			ans += 0
	print(ans)

### FIXED CODE ###

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

from collections import Counter

c = Counter(a)

for i in range(1,n+1):
	print(c[i])
### BUGGY CODE ###

n = int(input())

s = 1

for i in range(n):
  s = s * (i+1)
print(s%1000000007)

### FIXED CODE ###

n = int(input())
 
s = 1
 
for i in range(n):
  s = (s * (i+1)) % 1000000007
print(s%1000000007)
### BUGGY CODE ###

N = int(input())
l = input().split()

ans_list = []

for i in range(1, N+1):
  ans_list.append(str(l.index(str(i))+1))

l = " ".join(ans_list)
  
print(l)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * N
for i, a in enumerate(A):
    ans[a-1] = i+1

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

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

A = [0] * (N+1)
B = [0] * (N+1)
#magic = np.zeros((N+1, 2), dtype=int)

for i in range(1, N+1):
    A[i], B[i] = map(int, input().split())

# print(magic)
# print(A)
# print(B)

INF = 100000010  # 10^4 * 10^4 + spare

#dp = np.full((N+1, H*2+1), INF)
#dp[0][0] = 0

dp = [INF]*(H+1)
#dp = np.full(H+1, INF, dtype=int)
dp[0] = 0

for i in range(1, N+1):
    for j in range(H + 1):
        # 貰うDP
        if j-A[i] >= 0:
            dp[j] = min(dp[j - A[i]] + B[i], dp[j])
        else:
            dp[j] = min(dp[0] + B[i], dp[j])

#        print(dp[i])
#    print(dp)

print(dp[H])


### FIXED CODE ###

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

A = [0] * (N+1)
B = [0] * (N+1)
#magic = np.zeros((N+1, 2), dtype=int)

for i in range(1, N+1):
    A[i], B[i] = map(int, input().split())

# print(magic)
# print(A)
# print(B)

INF = 100000010  # 10^4 * 10^4 + spare

#dp = np.full((N+1, H*2+1), INF)
#dp[0][0] = 0

dp = [INF]*(H+1)
#dp = np.full(H+1, INF, dtype=int)
dp[0] = 0

for i in range(1, N+1):
    for j in range(H + 1):
        # 貰うDP
        if j-A[i] >= 0:
            dp[j] = min(dp[j - A[i]] + B[i], dp[j])
        else:
            dp[j] = min(dp[0] + B[i], dp[j])

#        print(dp[i])
#    print(dp)

print(dp[H])
### BUGGY CODE ###

n = int(input())
sg = []
for _ in range(n):
    s = input()
    if sg.count(s) == 0:
        sg.append(s)
print(len(sg))

### FIXED CODE ###

import collections
n = int(input())
sg = []
for _ in range(n):
    s = input()
    sg.append(s)
sgc = collections.Counter(sg)
print(len(sgc))
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
ANS = SME(A, 0, N, L, ANS)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

I = lambda: map(int, input().split())
N, A = I()
x = list(I())
 
from collections import deque
import copy
memo = []
checked = []
q = deque()
q.append([False]*N)
 
while q:
    indexs = q.popleft()
    if indexs in checked:
        continue
    checked.append(indexs)
    sum_x = 0
    for i, bit in enumerate(indexs):
        if bit:
            sum_x += x[i]
 
    if indexs.count(True) > 0 and sum_x / indexs.count(True) - A == 0:
        if indexs not in memo:
            memo.append(indexs)
 
    for i in range(N):
        a = copy.deepcopy(indexs)
        a[i] = not(a[i])
        if a not in checked:
            q.append(a)
 
print(len(memo))

### FIXED CODE ###

N,A=map(int, input().split())
x=list(map(int, input().split()))
dp = [[[0]*(51*51) for _ in range(N+1)] for _ in range(N+1)]
# dp[j][k][s]
for j in range(N+1):
    for k in range(N+1):
        for s in range(51*51):
            if j==0 and k==0 and s==0:
                dp[j][k][s] = 1
            elif j >=1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >=1 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s] = 0

ans = 0
for i in range(1, N+1):
    ans+= dp[N][i][i*A]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
num = [0]*100000
s = sum(A)
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(100000):
    num[i] = A.count(i+1)
for i in range(Q):
    s += (C[i]-B[i])*num[B[i]-1]
    print(s)
    num[C[i]-1] += num[B[i]-1]
    num[B[i]-1] = 0

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0
### BUGGY CODE ###

import sys
import math

input= sys.stdin.readline
N, M = map(int,input().split())

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

A.sort(reverse=True)
cnt = 1
A[0]=A[0]//2

if N==1:
    while A[0]>0 and cnt<M:
        cnt+=1
        A[0]=A[0]//2
else:
    while cnt<M:
        c=int(math.log2(A[0]/A[1])+1)
        cnt+=c
        A[0]=A[0]//(2**c)
        A.sort(reverse=True)
    
print(sum(A))
    
        

### FIXED CODE ###

import heapq

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

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

heapq.heapify(a)

num = 0
hq = 1

while num < M and hq != 0:
    hq = -heapq.heappop(a)
    hq2 = hq // 2
    heapq.heappush(a, -hq2)
    num += 1

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

def main():
    import numpy as np
    s = []
    for i in reversed(input()):
        if i == "?":
            s.append(None)
        else:
            s.append(int(i))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int64)
    m13 = np.array([(10**i) % 13 for i in range(12)], dtype=np.int64)
    memo[0] = 1
    for k, i in enumerate(s):
        memo2 = np.zeros(13, dtype=np.int64)
        a = m13[k % 12]
        if i is None:
            for l in a*np.arange(10) % 13:
                for j in range(13):
                    memo2[(l+j) % 13] += memo[j]
            memo = memo2 % mod
        else:
            l = a*i
            memo = np.append(memo[(-l) % 13:], memo[:(-l) % 13]) % mod
    print(memo[5])


main()

### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

if __name__ == '__main__':
    a, v = map(int, input().split())
    b, w = map(int, input().split())
    t = int(input())

    if w>= v:
        print("NO")
    else:
        flag = False
        if a == b:
            flag = True

        for i in range(t):
            if b>a:
                a+=v
                b+=w
            else:
                a-=v
                b-=w
            if a==b:
                flag=True
        if flag:
            print("YES")
        else:
            print("NO")



### FIXED CODE ###

if __name__ == '__main__':
    a, v = map(int, input().split())
    b, w = map(int, input().split())
    t = int(input())
    l =abs(a - b)
    s=abs(v - w)

    if w >= v or l / s > t:
        print("NO")
    else:
        print("YES")
### BUGGY CODE ###

n,m=map(int,input().split())
data=[]
p=[0]*n
y=[[] for _ in range(n)]
q=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i])
    p[p_i-1]+=1
    y[p_i-1].append(y_i)
for i in range(n):
    if p[i]>1:
        y[i].sort()
for i in range(m):
    ans_p=data[i][0]
    ans_y=y[ans_p-1].index(data[i][1])+1
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
data=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i,i])
data.sort()
data.append([n+1,0,m])
buf=1
for i in range(m):
    data[i].append(buf)
    if data[i][0]==data[i+1][0]:
        buf+=1
    else:
        buf=1
data.sort(key=itemgetter(2))
for i in range(m):
    ans_p=data[i][0]
    ans_y=data[i][3]
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)
### BUGGY CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
bit = Bit(n)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    a = bit.sum(y)
    b = i - a
    c = y - a - 1
    d = (n - i - 1) - c
    bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * pb * pc
    tmp += (pb - 1) * (pc - 1) * pa * pd
    tmp -= (pa - 1) * (pb - 1) * (pc - 1) * (pd - 1)
    ans = (ans + tmp) % MOD
print(ans)


### FIXED CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
f_bit = Bit(n)
b_bit = Bit(n)
for i in range(1, n + 1):
    b_bit.add(i, 1)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    b_bit.add(y, -1)
    a = f_bit.sum(y)
    b = i - a
    c = b_bit.sum(y)
    d = (n - i - 1) - c
    f_bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * pb * pc
    tmp += (pb - 1) * (pc - 1) * pa * pd
    tmp -= (pa - 1) * (pb - 1) * (pc - 1) * (pd - 1)
    ans = (ans + tmp) % MOD
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
ans=False
for i in range(m):
	a,b=map(int,input().split(" "))
	if a==1:l.append(b)
	if b==n:bone.append(a)

l.sort()
bone.sort()
for i in l:
	for j in bone:
		if i == j:
			ans=True
	
if ans == True:print("POSSIBLE")
else:print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

s = input()
mod = 10**9 + 7
n = len(s)
dp = [[0] * 13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    if s[i] != "?":
        for j in range(13):
            dp[i+1][(10 * j + int(s[i])) % 13] += dp[i][j]

    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(10 * j+k) % 13] += dp[i][j]
                dp[i+1][(10 * j+k) % 13] %= mod


print(dp[n][5])

### FIXED CODE ###

s = input()
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(len(s)+1)]
for i in range(10):
    if s[0] == "?":
        dp[1][i] += 1
    else:
        dp[1][int(s[0])] = 1
        break

for i, v in enumerate(s):
    if i == 0:
        continue
    for j in range(13):
        for k in range(10):
            x = (10 * j + k) % 13
            if v != "?":
                if int(v) == k:
                    dp[i + 1][x] += dp[i][j]
                    dp[i + 1][x] %= mod
                else:
                    dp[i + 1][x] += 0
            else:
                dp[i + 1][x] += dp[i][j]
                dp[i + 1][x] %= mod

print(dp[-1][5])
### BUGGY CODE ###

def main():
    import sys
    import fractions as f
    N = int(sys.stdin.readline())
    total=0
    for i in range(1, N+1):
        for j in range(i, N+1):
            for k in range(j, N+1):
                if i==j and j==k:
                    total+=f.gcd(f.gcd(i,j), f.gcd(j,k))
                elif i==j or j==k or i==k:
                    total+=f.gcd(f.gcd(i,j), f.gcd(j,k))*3
                else:
                    total+=f.gcd(f.gcd(i,j), f.gcd(j,k))*6
    print(total)
    


if __name__=='__main__':
    main()

### FIXED CODE ###

def gcd(x,y,z):
    for i in range(x, 0, -1):
        if x%i==0 and y%i==0 and z%i==0:
            #print(i)
            return i
            break
            
    

def main():
    import sys
    N = int(sys.stdin.readline())
    total=0
    for i in range(1, N+1):
        for j in range(i, N+1):
            for k in range(j, N+1):
                if i==j and j==k:
                    total +=gcd(i, j, k)
                elif i==j or j==k or i==k:
                    total +=gcd(i, j, k)*3
                else:
                    total +=gcd(i, j, k)*6
                
    print(total)
    


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

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

a = list(set(A))
ans = []
for i in range(len(a)):
  if A.count(a[i]) < 2:
    continue
  if A.count(a[i]) >= 4:
    ans += [a[i] , a[i]]
  else:
    ans.append(a[i])
ans.sort()
print(ans[-1]* ans[-2] if len(ans) >= 2 else 0)

### FIXED CODE ###

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

ans = []
s = A[0]
n = 1
for i in range(1, N):
  if len(ans) == 2: break
  if A[i] == s:
    n += 1
    if n == 2 or n == 4:
      ans.append(s)
  else:
    s = A[i]
    n = 1
print(ans[0] * ans[1] if len(ans) != 0 else 0)
### BUGGY CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

M = max(ok)

for i in ok:
    for j in range(2,M+1):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

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

N = int(input())
list = [int(i) for i in input().split()]

count = 0

for j in range(N):
    #print("j="+str(j))
    for k in range(j+1):
        #print("k="+str(k))
        if (list[k] >= list[j]):
            #print("k > j")
            if(k == j):
                count += 1
                break

            continue
        elif(list[k] < list[j]):
            break

print(count)


### FIXED CODE ###

N = int(input())
list = [int(i) for i in input().split()]

ans = 0
min = list[0]

for j in range(N):
    if (min  >= list[j]):
        ans += 1
        min = list[j]
    else:
        continue

print(ans)
### 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]))

for i in range(0,len(L)):
	L[i] = ",".join(L[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)