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

import sys
input = sys.stdin.readline

import numpy as np
from collections import defaultdict
n = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず1とかにする）
d = defaultdict(int)
for i in range(n):
    d[a[i]] = b[i]

from_ = 1
count = 0
while True:
    count += 1
    from_ = d[from_]
    if from_ == 1:
        break

if count != n:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import numpy as np

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

a_sort = np.sort(a)
b_sort = np.sort(b)

# 1. 回数関係なくそもそも不可能なやつ → no
# 2-a. サイクルは1つだとしても，完璧じゃない組み合わせが1つ以上許容されるやつ → yes
# 2-b. サイクルが2以上にわけられるやつ → yes

# 1
if (a_sort > b_sort).any():
    print('No')
    exit()

# 2-a
if (a_sort[1:] <= b_sort[:-1]).any():
    print('Yes')
    exit()

# 2-b （startをとりあえず0番目とかにする）
index = b.argsort()
a = a[index]
sort_dict = a.argsort().tolist()
from_ = 0
count = 0
while True:
    count += 1
    from_ = sort_dict[from_]
    if from_ == 0:
        break

if count != n:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

for i in range(1, n + 1):
    cnt = 0
    flg = False
    for j in a:
        if i == j:
            flg = True
            cnt += 1
        elif i != j and flg == True:
            break
    print(cnt)

### FIXED CODE ###

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

res = [0] * n
for i in range(len(a)):
    res[a[i]-1] += 1

[print(j) for j in res]
### BUGGY CODE ###


def main():
    n = int(input())
    array = list(map(int, input().split()))
    ans = 1
    for i in range(n):
        ans *= array[i]
        re = 10 ** 18

    
    if ans > re:
        print(-1)
    else:
        print(ans)
    return 0
        
main()

### FIXED CODE ###

def main():
    n = int(input())
    array = list(map(int, input().split()))
    ans = 1
    re = 10 ** 18
    for i in range(n):
        if array[i] == 0:
            print(0)
            return 0
    for i in range(n):
        ans *= array[i]
        if ans > re:
            print(-1)
            return 0
    print(ans)
    return 0
        
main()
### BUGGY CODE ###


import itertools
import numpy as np
from numba import jit


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


def gcd3(a, b, c):
    return gcd(gcd(a, b), c)


N = input()
a = [int(N) for k in range(3)]
range_list = list(map(lambda x: range(1, x+1), a))
prd_list = itertools.product(*range_list)

# prd_set = ((s[0] + 1, ))

gcds = [gcd3(*prd) for prd in prd_list]

s = np.sum(gcds)

print(s)

### FIXED CODE ###

#!/usr/bin/env python3

from math import gcd


t = int(input())
ans = 0
for i in range(1, t + 1):
    for j in range(1, t + 1):
        r = gcd(i, j)

        for k in range(1, t + 1):
            ans += gcd(r, k)

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

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=h+i<H and 0<=w+j<W:
                if fs[h+i][w+j] == ".":
                    if dps[h+i][w+j] <= cnt:continue
                    q.append((h+i,w+j))
                    dps[h+i][w+j] = min(dps[h+i][w+j], cnt + 1)
    for dh, dw in mvs:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] <= cnt:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn))
                dps[hn][wn] = min(dps[h][w], cnt)

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###

k = int(input())
s = input()
mod = 10**9+7
n = len(s)
def nCr(N, R, mod):
	R = min(R, N-R)
	numer = denom = 1
	for i in range(1, R+1):
		numer = numer * (N+1-i) % mod
		denom = denom * i % mod
	return numer * pow(denom, mod-2, mod) % mod


ans = 0
for i in range(k+1):
  a = pow(25, i, mod)
  a *= nCr(i+n-1, n-1, mod)
  a *= pow(26,k-i, mod)
  ans += a
  ans %= mod
print (ans)

### FIXED CODE ###

k = int(input())
s = input()
mod = 10**9+7
n = len(s)
fact =[1]*(k+n)
factinv = [1]*(k+n)
inv = [0,1]
 
 
for i in range(2,k+n):
    fact[i] = (fact[i-1] * i) % mod
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv[i] = (factinv[i-1] * inv[i]) % mod

def nCr(n,r):
  r = min(r,n-r)
  return (fact[n] * factinv[r] * factinv[n-r])%mod
ans = 0
for i in range(k+1):
  a = pow(25, i, mod)
  a *= nCr(i+n-1, n-1)
  a *= pow(26,k-i, mod)
  ans += a
  ans %= mod
print (ans)
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
    ans.append(str(L.index(i)+1))
print(' '.join(ans))


### FIXED CODE ###

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

D={}
for i in range(n):
      D.update({i+1:A[i]})

D_sorted = sorted(D.items(),key=lambda x:x[1])

D2=[]
for i in range(n):
  D2.append(str(D_sorted[i][0]))


print(' '.join(D2))
### BUGGY CODE ###

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

def f(i):
    return sum(A[(i + j) % N] * (1 if j % 2 == 0 else -1) for j in range(N))

B = [f(i) for i in range(N)]

print(' '.join(map(str, B)))

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[0] // 2

# 2 * A[0] = B[0] + B[1]
# 2 * A[1] = B[1] + B[2]
# 2 * A[2] = B[2] + B[0]

# 2 * A[2] - 2 * A[1] = B[0] - B[1]
# 2 * A[0] - 2 * A[2] = B[1] - B[2]
# 2 * A[1] - 2 * A[0] = B[0] - B[2]

# A[0] - A[2] + A[1] = B[1]

# B[i] = A[i] + A[i - 1] - A[i + 1]

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = B[0] - B[2]
# A[1] - A[2] = B[1] - B[3]
# A[2] - A[3] = B[2] - B[4]
# A[3] - A[4] = B[3] - B[0]
# A[4] - A[0] - B[4] - B[1]

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

S=input()
q=int(input())
s=[]
for i in S:
    s.append(i)
for i in range(q):
    qv=list(input().split())
    if qv[0]=='1':
        ss=[]
        for j in range(len(s)):
            ss.append(s[-1-j])
        s=ss
    else:
        if qv[1]=='1':
            s.insert(0,qv[2])
        else:
            s.append(qv[2])
    
ans=''.join(s)
print(ans)

### FIXED CODE ###

S=input()
q=int(input())
s=[]
r=[]
for i in S:
    s.append(i)
t=1
for i in range(q):
    qv=list(input().split())
    if qv[0]=='1':
        t^=1
    else:
        if int(qv[1])^t==0 or int(qv[1])^t==2:
            r.append(qv[2])
        else:
            s.append(qv[2])
            
if t==0:
    ss=s.copy()
    s=[]
    for j in range(len(ss)):
        s.append(ss[-1-j])
    ans=s
    ans.extend(r)
else:
    rr=r.copy()
    r=[]
    for j in range(len(rr)):
        r.append(rr[-1-j])
    ans=r
    ans.extend(s)
answer=''.join(ans)
print(answer)
### BUGGY CODE ###

n = int(input())

power=1
index=2
while index < n+1:
    power*=index
    index+=1

if power > 10**9 + 7:
    print(power%(10**9 + 7))
else:
    print(power)

### FIXED CODE ###

n = int(input())

if n < 5000:
    power=1
    index=2
    while index < n+1:
        power*=index
        index+=1
elif n == 5000:
    power = 541108809 + (10**9 + 7)*2
elif n > 5000 and n < 40000:
    power = 541108809
    index = 5001
    while index < n+1:
        power*=index
        index+=1
elif n == 40000:
    power = 422550956 + (10**9 + 7)*2
elif n > 40000 and n < 70000:
    power = 422550956
    index = 40001
    while index < n+1:
        power *= index
        index += 1
elif n == 70000:
    power = 296716438 + (10**9 + 7)*2
else:
    power = 296716438
    index= 70001
    while index < n+1:
        power *= index
        index += 1

if power > 10**9 + 7:
    print(power%(10**9 + 7))
else:
    print(power)
### BUGGY CODE ###

from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 


# 2 cases
if P == 2 or P == 5:
	digitdiv = []
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1

else:
	#
	prefix = []
	for i in range(N):
		x = int(S[i:]) % P 
		prefix.append(x)
	prefix.append(0)
	count = Counter()
	for i in range(N + 1):
		count[int(prefix[i])] += 1

	for val in count.values():
		ans += val*(val - 1)//2


print (ans)





### FIXED CODE ###

from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 


# 2 cases
if P == 2 or P == 5:
	digitdiv = []
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1

else:
	#
	count = Counter()
	prefix = []
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P 
		prefix.append(x)
		count[x] += 1
		ten = (ten * 10) % P 
		mod = x
	prefix.append(0)
	count[0] += 1
	for val in count.values():
		ans += val*(val - 1)//2


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

import queue
import copy
def dfs(L,start,end):
    stack = [start]

    visited = []

    path =[ 0 for i in range((len(L)+1))]

    while stack:
        node = stack.pop()
        if node == end:
            return path[end]
        for n in L[node]:
            if n[0] not in visited:

                path[n[0]] = path[node]  + n[1]

                stack.append(n[0])
                visited.append(n[0])


def bfs(L,start,end):
    que = queue.Queue()
    que.put(start)

    visited = [start]
    while not que.empty():
        q = que.get()
        if q == end:
            return visited

        for v in L[q]:
            if v[0] not in visited:
                visited.append(v[0])
                que.put(v[0])



N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

for i in range(Q):
    v1 = dfs(L,xy[i][0],K)
    v2 = dfs(L,K,xy[i][1])
    print(v1+v2)


### FIXED CODE ###

import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])
### BUGGY CODE ###

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)
S = input()
Scount = 0
for i in range(len(S)-1):
    for j in range(1,len(S)):
        if (i+j)<=len(S):
            part_S = S[i:i+j]
            num = int(part_S)
            if num % 2019==0:
                Scount += 1
print(Scount)

### FIXED CODE ###

S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*'
            x=re.match(p, s)
            if x:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from pprint import pprint
from collections import deque, defaultdict
N, M = map(int, input().split())

if M == 0:
    print("Yes")
    exit()

LRD = [list(map(int, input().split())) for _ in range(M)]

# 速めのdfs（非再帰）
graph = defaultdict(lambda: defaultdict(int))
visited = defaultdict(bool)

for L,R,D in LRD:
    graph[L][R] = D
    graph[R][L] = -D
    visited[L] = False
    visited[R] = False

# pprint(graph)

def xfs(v):
    que = deque()
    # visited[v] = True
    vis_set = set([v])
    que.append((v,0,[v]))
    while len(que) > 0:
        i,cnt,vis = que.pop()  # 深さ優先探索
        for n,val in graph[i].items():
            if n not in vis:
            # if visited[n] == False:
                # visited[n] = True
                # print("if:v,i,n,cnt,val", v,i,n, cnt, val)
                vis_set.add(n)
                que.append((n, cnt+val,vis+[n]))
            elif n == v:
                # print("el:v,i,n,cnt,val", v,i,n, cnt, val)
                if cnt + val != 0:
                    return False

    for i in list(vis_set):
        visited[i] = True
    return True


que2 = deque()
L, _, _ = LRD[0]
que2.append(L)
while len(que2) > 0:
    L = que2.pop()
    if xfs(L):
        for k,v in [(k,v) for k,v in visited.items() if v==False]:
            que2.append(v)
            break
    else:
        # pprint(visited)
        # print("L=",L)
        print("No")
        exit()

# pprint(visited)
print("Yes")


### FIXED CODE ###

# -*- coding: utf-8 -*-
from pprint import pprint
import random
from collections import deque, defaultdict
N, M = map(int, input().split())

if M == 0:
    print("Yes")
    exit()

LRD = [list(map(int, input().split())) for _ in range(M)]

# N,M = 100000,200000
# LRD = [[i+10+random.randint(-9,100),i+20+random.randint(-18,200),random.randint(1,300)] for i in range(M)]
# print("run")

# 速めのdfs（非再帰）
graph = defaultdict(lambda: defaultdict(int))
# graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
# graph = [defaultdict(int) for _ in range(N+1)]
visited = defaultdict()

for L,R,D in LRD:
    graph[L][R] = D
    graph[R][L] = -D
    visited[L] = None
    visited[R] = None

# print("step1")
# pprint(graph)

def xfs(v):
    que = deque()
    que.append((v,0))
    while len(que) > 0:
        i,cnt = que.pop()  # 深さ優先探索
        visited[i] = cnt
        # print("step3:i",i)
        for n,val in graph[i].items():
            if visited[n] == None:
                # print("if:v,i,n,cnt,val", v,i,n, cnt, val)
                que.append((n, cnt+val))
            else:
                # print("el:v,i,n,cnt,val,visited[n]",
                #       v, i, n, cnt, val, visited[n])
                if cnt + val != visited[n]:
                    return False

    return True


que2 = deque()
L, _, _ = LRD[0]
que2.append(L)
while len(que2) > 0:
    L = que2.pop()
    # print("step2:L",L)
    if xfs(L):
        for k,v in [(k,v) for k,v in visited.items() if v==None]:
            # print("step4:k", k)
            que2.append(k)
            break
    else:
        # pprint(visited)
        # print("L=",L)
        print("No")
        exit()

# pprint(visited)
print("Yes")
### BUGGY CODE ###

import random
import copy

def cal(x):
  Manzoku=0
  l=[0]*26
  for d in range(D):
    l[x[d]-1]=d
    Manzoku+=s[d][x[d]-1]
    for i in range(26):
      Manzoku-=c[i]*(d-l[i])
  return Manzoku

D=int(input())
c=list(map(int,input().split()))
s=[]
t=[]
for i in range(D):
  s.append(list(map(int,input().split())))
l=[0]*26

max=0
target=0
deg=0
#初期t生成
for d in range(D):
  degsum=0
  max=0
  for i in range(26):
    degsum+=c[i]*(d-l[i])
  for i in range(26):
    w=degsum-c[i]*(d-l[i])-s[d][i]
    if max < -w:
      max=-w
      target=i
  t.append(target+1)
  l[target]=d
  
mManzoku=cal(t)
for i in range(100000):
  rd=int(random.random()*D)
  ri=int(random.random()*26)
  t1=copy.deepcopy(t)
  t1[d]=ri+1
  n=cal(t1)
  if mManzoku < n:
    t=copy.deepcopy(t1)
    mManzoku=n

print(mManzoku)
for i in range(D):
  print(t[i])


### FIXED CODE ###

D=int(input())
c=list(map(int,input().split()))
s=[]
t=[]
for i in range(D):
  s.append(list(map(int,input().split())))
l=[0]*26
Manzoku=0

max=0
target=0
deg=0
for d in range(1,D+1):
  for i in range(26):
    deg=c[i]*(d-l[i])
    if max < deg:
      max=deg
      target=i
  t.append(target+1)
  l[target]=d

for i in range(D):
  print(t[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i, j = [], []
for s in range(n):
    num = s+1
    i.append(a[s]+num)
    j.append(num-a[s])
result = 0
for p in range(n-1):
    result += j[p+1:].count(i[p])
print(result)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
i, j = [], []
for s in range(n):
    num = s+1
    i.append(a[s]+num)
    j.append(num-a[s])
x = Counter(j)
result = 0
for p in range(n-1):
    if i[p] in x:
        result += x[i[p]]
    x[j[p]] += 1 
print(result)
### BUGGY CODE ###

import re
n0=input()
s=input()
ans=0

for i in range(1000):
    n = str(i).zfill(3)
#    print(n[0])
    p = ".*"+ n[0] + ".*" + n[1] + ".*" + n[2] +".*"
    if re.search(p,s):
        ans += 1
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

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

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    ans = 0
    for i in range(N-2):
        for j in range(i, N-1):
            if S[i] == S[j]:
                continue
            for k in range(j, N):
                if S[i] != S[k] and S[j] != S[k]:
                    if j - i == k - j:
                        continue
                    ans += 1

    print(ans)




if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    R = [0] * N
    G = [0] * N
    B = [0] * N
    rcnt = 0
    gcnt = 0
    bcnt = 0
    rgb = {
        ('R', 'G'):'B',
        ('G', 'R'):'B',
        ('R', 'B'):'G',
        ('B', 'R'):'G',
        ('G', 'B'):'R',
        ('B', 'G'):'R'
    }
    for i, s in enumerate(S):
        if s == 'R':
            rcnt += 1
        elif s == 'G':
            gcnt += 1
        elif s == 'B':
            bcnt += 1
        R[i] = rcnt
        G[i] = gcnt
        B[i] = bcnt
    # print(R, rcnt)
    # print(G, gcnt)
    # print(B, bcnt)
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            # print('i = {}:{}, j = {}:{}'.format(i, S[i], j, S[j]), end=', ')
            if S[i] == S[j]:
                # print('S[i] == S[j] == {}'.format(S[i]))
                continue
            s = rgb[S[i], S[j]]
            if s == 'R':
                ans += rcnt - R[j]
                # print('ans += {}'.format(rcnt - R[j]))
            elif s == 'G':
                ans += gcnt - G[j]
                # print('ans += {}'.format(gcnt - G[j]))
            elif s == 'B':
                ans += bcnt - B[j]
                # print('ans += {}'.format(bcnt - B[j]))
            tn = j + (j-i)
            if tn < N and S[tn] == s:
                ans -= 1

    print(ans)




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

import sys
sys.setrecursionlimit(500*500) # default 1000
N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
def dfs(v,p=-1): # vertices & parent idx
    for child in to[v]:
        if child==p:
            continue
        ans[child]+=ans[v]
        dfs(child,v)
        


to=[[] for j in range(N)] # N points
ans=[0]*N # N points

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

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

dfs(0)
print(' '.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

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

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)
### BUGGY CODE ###

#import itertools
import math
n=int(input())
s = [str(sorted(list(input()))) for i in range(n)]
l=[]
for si in set(s):
    l.append(s.count(si))
ans=0
for i in l:
    if i>=2:
        #x=len(list(itertools.combinations(range(i),2)))
        x = (math.factorial(i) // (math.factorial(i - 2) * math.factorial(2)))
        ans+=x
print(ans)

### FIXED CODE ###

import math
from collections import Counter
n=int(input())
s = [str(sorted(list(input()))) for i in range(n)]
c = Counter(s)
#l=[]
#for si in set(s):
#    l.append(s.count(si))
ans=0
for i in c.values():
    if i>=2:
        x = (math.factorial(i) // (math.factorial(i - 2) * math.factorial(2)))
        ans+=x
print(ans)