Harryxun/stf_run huggingface dataset:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

### FIXED CODE ###

import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)
N = int(input())
A = [map(int, input().split())]
ans = int(0)
for i in A:
  ans *= i
  if ans >= 1e18:
    ans = -1
    break

### FIXED CODE ###

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

A.sort()

ans = 1
for i in A:
    ans *= i
    if ans > MAX:
        ans = -1
        break

print(ans)
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

### FIXED CODE ###

# D - Knapsack 1
N,W = map(int,input().split())
value = []
weight = []
for _ in range(N):
    w,v = map(int,input().split())
    value.append(v)
    weight.append(w)

# DP テーブル
# dp[i][j]: i-1 番目までの品物から重さが j を超えないように選んだときの価値の最大値
# W <= 100000, N <= 100 よりテーブルの個数を決める
dp = [[0]*100010 for _ in range(102)]

# DP テーブル全体を初期化
for i in range(102):
    for j in range(100010):
        dp[i][j] = 0# 最大化問題

# DP ループ
# v-1 番目の荷物に対する情報を dp[v] に記録
for v in range(1,N+1):
    for w in range(W+1):
        # v-1 番目の品物を選ぶ場合
        if (w - weight[v-1]) >= 0:
            dp[v][w] = max(dp[v][w],dp[v-1][w - weight[v-1]] + value[v-1])
        # v-1 番目の品物を選ばない場合
        dp[v][w] =  max(dp[v][w],dp[v-1][w])
        
# 価値の総和の最大値を出力
print(dp[N][W])
A,B = [int(i) for i in input().split(' ')]

0<=A
B<=10**9

if (A%2==0) AND (B%2==0):
  print((A+B)/2)
elif (A%2 !=0) AND (B%2 !=0):
  print((A+B)/2)
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

A,B = [int(i) for i in input().split(' ')]

0<=A
B<=10**9

if (A+B)%2 == 0:
  print((A+B)//2)
else:
  print('IMPOSSIBLE')
list = set(input())
lists = set([chr(i) for i in range(ord('a'), ord('z')+1)])
ans = lists-list
print(min(ans) if len(list(ans)) == 0 else 'None')

### FIXED CODE ###

S = list(input())
minal = ord('z')
for i in range(ord('a'), ord('z')+1):
    if i < minal and chr(i) not in S:
        minal = i
list = set(S)
print(chr(minal) if len(list)!=26 else 'None')
n, m = map(int, input().split())
x =[]
y =[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
d ={}
for i in range(1,n+1):
    d[i]=0

for i in range(m):
    d[x[i]] += 1
    d[y[i]] += 1

for i in range(1,n+1):
    print(d[i])




### FIXED CODE ###

a, b, c = map(int, input().split())
if a<=c<=b:
    print("Yes")
else:
    print("No")
n,l=map(int,input().split())
A=list(map(int,input().split()))
A=list([i+1,A[i]] for i in range(n))
cnt,cnt_list=0,[]
ans=[]
for x,y in A:
    cnt +=y
    cnt_list.append(x)
    if x==n:cnt_list.pop()
    if cnt>=l:
        ans.append(cnt_list.pop())
        for i in cnt_list:
            ans.append(i)
        cnt=0
        cnt_list=[]

if len(ans)==n-1:
    print("Possible")
    for i in ans:print(i)
else:print("Impossible")

### FIXED CODE ###

n,l=map(int,input().split())
A=list(map(int,input().split()))
add=0
for i in range(1,n):
    if A[i]+A[i-1]>=l:
        add=i+1
        break
if add==0:print("Impossible");exit()
print("Possible")
for i in range(1,add-1):print(i)
for i in [j for j in range(add,n)][::-1]:print(i)
print(add-1)
n = int(input())
l = []
for i in range(n):
    l.append(int(input())
           
for j in range(n):
    print(max(l[:i]+l[i+1:]))        

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
           
s = sorted(l, reverse=True)
      
for value in l:
    if value == s[0]:
        print(s[1])
    else:
        print(s[0])
b = input()
if b = "A":
  b = "T"
elif b = "T":
  b = "A"
elif b = "C":
  b = "G"
elif b = "G":
  b = "C"
print(b)

### FIXED CODE ###

b = input()
if b == "A":
  b = "T"
elif b == "T":
  b = "A"
elif b == "C":
  b = "G"
elif b == "G":
  b = "C"
print(b)
N = int(input())
total = 0
for i in range(N):
    money, tani = map(input().split())
    money = float(input())
    if tani = "JPY":
        total += money
    else:
        total += money * 380000
print("%f"%(total))

### FIXED CODE ###

year, month, day = map(int, input().split("/"))
if year <= 2019 and month <= 4 and day <= 30:
    print("Heisei")
else:
    print("TBD")
N = int(input())
S = input()

ans = 0
x = 0
for s in S:
  v = 1 if s == 'I' else: 0
  x += v
  ans = max(ans, x)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
x = 0
for s in S:
  v = 1 if s == 'I' else -1
  x += v
  ans = max(ans, x)
print(ans)
a,b=input().split()
 
print(min(a*int(b),b*(int(a) ) )
      


### FIXED CODE ###

a, b = input().split()
 
print(min(a*int(b), b*int(a) ) )
import sys

n, m = map(int, input().split())

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0 or m == 1:
    print(1)
    sys.exit()

adjacency_list = [[] for x in range(n + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))


### FIXED CODE ###

import sys

n, m = map(int, input().split())

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0:
    print(0)
    sys.exit()

adj_array = [[] for x in range(n + 1)]
res_array = [True] + [False for x in range(n)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))
nm = input().split(" ")
n = int(nm[0])
m = int(nm[1])

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        return get_root(pars[x])


def combine(x, y):
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for i in range(m):
    pair = input().split(" ")
    x = int(pair[0]) - 1 # 入力が1スタートなので
    y = int(pair[1]) - 1 # 入力が1スタートなので
    combine(x, y)

max_len = 0
for i in range(n):
    len = size(i)
    if len > max_len:
        max_len = len

print(max_len)

### FIXED CODE ###

import sys


class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

uf = UnionFind(N)
for a, b in info:
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)
a, b, c = map(int, raw_input().split())

if b - a == c - b:
    print "YES"
else:
    print "NO"
                

### FIXED CODE ###

n = input()

x = 800 * n
y = (n / 15) * 200
print x - y
n = int(input())
    nStr = str(n)
    number = nStr[len(nStr)-1]
    if number == '3':
        print('bon')
    elif number  == '0'or number=='1'or number =='6'or number =='8':
        print('pon')
    else:
        print('hon')

### FIXED CODE ###

n = int(input()) % 10
if n == 3:
  print("bon")
elif n in(0,1,6,8):
  print("pon")
else:
  print("hon")
N, M = map(int, input().split())
num = ['']*N
valid = True
#create number from input
for i in range(M):
  s, c = map(int, input().split())
  if (num[s-1] == ''):
    num[s-1] = c
  elif (num[s-1] != c):
    valid = False
    break
#check whether 0 is at front
if (N > 1):
  if (num[0]==0):
    valid = False
  
if valid:
  first = True
  #fill the blank parts
  if (num[0]==''):
    num[0]==1
  for i in range(1,N):
    num[i] = 1
  #convert list to number
  answer = 0
  for i in range(N):
    answer *= 10
    answer += num[i]
  print(answer)
else:
  print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
num = ['']*N
valid = True
#create number from input
for i in range(M):
  s, c = map(int, input().split())
  if (num[s-1] == ''):
    num[s-1] = c
  elif (num[s-1] != c):
    valid = False
    break
#check whether 0 is at front
if (N > 1):
  if (num[0]==0):
    valid = False
  
if valid:
  #fill the blank parts
  for i in range(N):
    if (num[i] == ''):
      if (i == 0):
        if (N == 1):
          num[i] = 0
        else:
          num[i] = 1
      else:
      	num[i] = 0
  #convert list to number
  answer = 0
  for i in range(N):
    answer *= 10
    answer += num[i]
  print(answer)
else:
  print(-1)
h,w=map(int,input().split())
a=[""]*h
for i in range(h):
	a[i]=input()

row=[False]*h
col=[False]*w
for i in range(h):
	for i in range(w):
		if a[i][j]=="#":
			row[i]=True
			col[j]=True
			
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j],end='')
				print()

### FIXED CODE ###

h,w=map(int,input().split())
a=[""]*h
for i in range(h):
	a[i]=input()

row=[False]*h
col=[False]*w
for i in range(h):
	for j in range(w):
		if a[i][j]=="#":
			row[i]=True
			col[j]=True
			
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j],end='')
		print()
a,b = map(int,input().split())
c= (b-a+1)*(a+b)//2
if c>0:
    print("Positive")
elif c=0:
    print("Zero")
else:
    print("Negative")

### FIXED CODE ###

a,b = map(int,input().split())
if a*b<=0:
    print("Zero")
elif b<0 and(b-a)%2==0:
    print("Negative")
else:
    print("Positive")
n=int(input())
b=0
c=0
for h in map(int, input.split()):
  if b<=h:
    b=h
    c+=1
print(c)

### FIXED CODE ###

n=int(input())
b=0
c=0
for h in map(int,input().split()):
  if b<=h:
    b=h
    c+=1
print(c)
import operator

def get_mincost(M_left, cost, i):
    cost += sorted_d[i][0] * min(sorted_d[i][1], M_left)
    M_left -= min(sorted_d[i][1], M_left)
    i += 1
    if M_left == 0:
        return cost
    return get_mincost(M_left, cost, i)

N, M = map(int, input().split())
M_left = M
cost = 0
i = 0

#dict {A_i(price), B_i(num)}
d = dict(map(int, input().split()) for i in range(N))
global sorted_d
sorted_d = sorted(d.items(), key=operator.itemgetter(0))

print(int(get_mincost(M_left, cost, i)))

### FIXED CODE ###

N, M = map(int, input().split())
p_list = []

res = M
total_p = 0
for i in range(N):
    a, b = map(int, input().split())
    p_list.append(a)
    p_list.append(b)

for price, amount in sorted(zip(p_list[::2], p_list[1::2])):
    total_p += price * min(res, amount)
    res -= amount
    if res <= 0:
        break
        
print(total_p)
k = map(int, input().split())
if k%2==1:
  print((k//2) * (k//2+1))
else:
  print((k//2) * (k//2))


### FIXED CODE ###

k = int(input())
if k % 2 == 1:
    print(k//2 * (k//2+1))
else:
    print(k//2 * k//2)
n = int(input())
v = [int(i) for i in input().split()]
m = n//2

a = [v[2*i] for i in range(0,m)]
b = [v[2*i+1] for i in range(0,m)]

def mode(arr):
        r = [0] * (max(arr) + 1)
        for a in arr:
            r[a] += 1
        return r.index(max(r))

A = mode(a)
B = mode(b)

if v.remove(A) == []:
    print(m)
    exit()
if A == B:
    if a.count(A) < b.count(B):
        C = mode(a.remove(A))
        print(n - a.count(C) - b.count(B))
    else:
        if b.count(B) == m:
            print(n)
        else:
            C = mode(b.remove(B))
            print(n - a.count(A) - b.count(C))
else:
    print(n - a.count(A) - b.count(B))

### FIXED CODE ###

n = int(input())
v = [int(i) for i in input().split()]
m = n//2

a = [v[2*i] for i in range(0,m)]
b = [v[2*i+1] for i in range(0,m)]

def mode(arr):
        r = [0] * (max(arr) + 1)
        for a in arr:
            r[a] += 1
        return r.index(max(r))

A = mode(a)
B = mode(b)

v.remove(A)

if v == []:
    print(m)
    exit()
if A == B:
    if a.count(A) < b.count(B):
        a.remove(A)
        C = mode(a)
        print(n - a.count(C) - b.count(B))
    else:
        if b.count(B) == m:
            print(n - m)
        else:
            if a.count(A) == b.count(B):
                t = a.count(A)
                a.remove(A)
                b.remove(B)
                D = mode(a)
                E = mode(b)
                if a.count(D) > b.count(E):
                    print(n - t - a.count(D))
                else:
                    print(n - t - b.count(E))
            else:
                b.remove(B)
                C = mode(b)
                print(n - a.count(A) - b.count(C))
else:
    print(n - a.count(A) - b.count(B))
a,b,x = map(int,input().split())
import math

if x==1 and a==1 and b==1:
  print(0)
if x//a<=(a*b/2):
  print(90-math.degrees(math.atan((2*x)/(a*(b**2)))))
    
else:
  print(90-math.degrees(math.atan(a/(2*(b-(x/a**2))))))

### FIXED CODE ###

a,b,x = map(int,input().split())
import math

if x==a**2*b:
  print(0)
elif x//a<=(a*b/2):
  print(90-math.degrees(math.atan((2*x)/(a*(b**2)))))
    
else:
  print(90-math.degrees(math.atan(a/(2*(b-(x/a**2))))))
a,b,c = map(int,input().split())
if a - b > c
    print(0)
else
    print(c-a+b)


### FIXED CODE ###

a,b,c = map(int,input().split())
if a - b > c:
    print(0)
else:
    print(c-a+b)
l = []
for i in range(3):
    l.append(int(input()))
l.sort()
print(l[0]+l[1])

### FIXED CODE ###

l = input().split()
l.sort()
print(int(l[0])+int(l[1]))
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc126_d

from collections import namedtuple

DistFrom = namedtuple('DistFrom', ['f', 'dist'])

def main():
    # input
    n, = [int(s) for s in input().split()]
    fs = [[int(s) for s in input().split()] for _ in range(n-1)]
    # getans
    getters = [None] * n
    for i in range(n):
        getters[i] = list()
    for x, y, d in fs:
        x -= 1
        y -= 1
        getters[x].append((y, d))
        getters[y].append((x, d))
    distlist = [None] * n
    def search(cur_i, prev, dist):
        distlist[cur_i] = dist
        for i, d in getters[cur_i]:
            if i != prev:
                search(i, cur_i, dist+d)
    distlist[0] = 0
    for i, d in getters[0]:
        search(i, 0, d)
    ans = [d%2 for d in distlist]
    # output
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10**5)

n = int(input())
p = [list() for _ in range(n)]
for i in range(n-1):
    u, v, w = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    w %= 2
    p[u].append((v, w))
    p[v].append((u, w))

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

for i in range(n):
    print(costs[i])
import math
a,b,c,d=map(int,input().split())

p=c*d//(math.gcd(c,d))

x = (a-1) - ((a-1)//c + (a-1)//d - (a-1)//p)
y = b - (b//c + b//d - b//p)


print(y-x)


### FIXED CODE ###

a,b,c,d=map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
p=c*d//gcd(c,d)

x = (a-1) - ((a-1)//c + (a-1)//d - (a-1)//p)
y = b - (b//c + b//d - b//p)


print(y-x)
n,m,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
ans = 0
time = 0
a_time = 0
temp = 0
if a[0] > k:
    j = 0
    while time <= k:
        time += b[j]
        j += 1
        ans += 1
else:
    for i in range(n):
        a_time += a[i]
        if a_time > k:
            break
        else:
            time = a_time
            j = 0
            while time <= k:
                time += b[j]
                j += 1
            temp = i + 1 + j            
            if temp > ans:
                ans = temp
                
print(ans)

### FIXED CODE ###

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

sum_a = [0]
sum_b = [0]

for i in range(n):
    sum_a.append(sum_a[i] + a[i])
for j in range(m):
    sum_b.append(sum_b[j] + b[j])

temp = 0
j = m
ans = 0
for i in range(n+1):
    if sum_a[i] > k:
        temp = i -1
        if temp > ans:
            ans = temp
        break
    else:
        while k - sum_a[i] < sum_b[j]:
            j -= 1
        temp = i + j
        if temp > ans:
            ans = temp
            
print(ans)
N=map(int, input())
list=list(map(str, input().split()))
answer=[]
for i in range(1, N+1):
	answer.append(list.count(i))
a_s='\n'.join(answer)
print(a_s)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=[0]*N
for a in A:
  ans[a-1]+=1
for n in ans:
  print(n)
s=input()
flag=1
if list(s)[2]==list(s)[3]:
  if list(s)[4]==list(s)[5]:
    flag=0
if flag=0:
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

s=input()
flag=1
if list(s)[2]==list(s)[3]:
  if list(s)[4]==list(s)[5]:
    flag=0
if flag==0:
  print("Yes")
else:
  print("No")
a,b=map(int,input().split())


if a//10!=0:
    print(-1)

elif b//10!=0:
    print(-1)

else:
    print(a*b)


### FIXED CODE ###

n=int(input())
flag=False

for i in range(1,10):
    for j in range(1,10):
        if i*j==n:
            flag=True

if flag==True:
    print('Yes')
else:
    print('No')
n = int(input())
a = list(map(int, input().split())) 
if a.count(1) == 0:
    print(-1)
else:
    t = 0
    for i in range(1, n):
        if not a.count(i) == 0:
            s = a.index(i)
            for j in range(t, s+1):
                a[j] = 0
            t = s
        else:
            y = i-1
            break
    print(n-y)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split())) 
a = tuple(a)
if a.count(1) == 0:
    print(-1)
else:
    s = 0
    t = 1
    for i in range(n):
        if a[i] == t:
            t += 1
        else: s += 1
    print(s)
import numpy as n;print([input(),n.gcd.reduce(list(map(int,input().split())))][1])

### FIXED CODE ###

from fractions import gcd
print [input(),reduce(gcd,map(int,raw_input().split()))][1]
N = int(input())

# 長さが10で英小文字の文字列リスト
str_list = [input() for i in range(N)]

import itertools as iter
comb_list = list(iter.combinations(str_list, 2))

def from_cache(cache_dict, word):
    if word in cache_dict.keys():
        return cache_dict

    cnt_dict = {}
    for s in list(word):
        if s not in cnt_dict.keys():
            cnt_dict[s] = 0
        cnt_dict[s] += 1
    cache_dict[word] = sorted(cnt_dict.items(), key=lambda x:x[0])
    return cache_dict


cache_dict = {}
cnt = 0
for comb_str in comb_list:
    w1, w2 = comb_str[0], comb_str[1]

    cache_dict = from_cache(cache_dict, w1)
    cache_dict = from_cache(cache_dict, w2)

    if cache_dict[w1].keys() != cache_dict[w2].keys():
        continue

    if cache_dict[w1].values() != cache_dict[w2].values():
        continue

    cnt += 1


print(cnt)

### FIXED CODE ###


N = int(input())

cnt_dict = {}

for i in range(N):
    s_list = list(input())
    s_list.sort()
    s_str = "".join(s_list)
    if s_str not in cnt_dict.keys():
        cnt_dict[s_str] = 1
        continue
    cnt_dict[s_str] += 1

import itertools
comb = itertools.combinations

total = 0
for key in cnt_dict.keys():
    cnt = cnt_dict[key]
    if cnt < 2:
        continue
    total += cnt * (cnt - 1) // 2

print(total)
_ = input()
S = input()
print(len(S.split("ABC") - 1))

### FIXED CODE ###

_ = input()
S = input()
print(len(S.split("ABC")) - 1)
def soinsu(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
a=soinsu(n)
c=[]
if n>=2:
    for i in range(max(a)):
        c.append(0)
for i in a:
    c[i-1]+=1
z=0
f=max(c)
g=[1]
d=1
e=1
while e<=f:
    d+=1
    e=d*(d+1)/2
    g.append(e)
l=len(g)
for i in c:
    for j in range(l):
        if i<g[j]:
            z+=j
            break
        
print(z)

### FIXED CODE ###

n=int(input())
import math
s=round(math.sqrt(n))+1

i=2
c1=0
c2=1
ans=0
while i<=s:
    if n%i==0:
        n//=i
        c1+=1
        if c1==c2:
            c1=0
            c2+=1
            ans+=1
    else:
        c2=1
        i+=1
        c1=0
if n>s:
    ans+=1
    
print(ans)
input_list = map(int, input().split())
even_list_len = list_len
count = 0
 
while:
  even_list = filter(lambda num: num % 2 , input_list)
  even_list_len = len(even_list)
  if list_len != even_list_len:
    break
  even_list = map(lambda num: num / 2, even_list)
  count += 1
    
print(count)

### FIXED CODE ###

input_list_len = int(input())
input_list = map(int, input().split())
even_list = input_list
even_list_len = input_list_len
count = 0

while True:
    even_list = list(filter(lambda num: num % 2 == 0, even_list))
    even_list_len = len(even_list)
    if input_list_len != even_list_len:
        break
    even_list = map(lambda num: num / 2, even_list)
    count += 1

print(count)
a,b = map(int,input().split())
print("GREATER") if a>b else print("LESS") if a<b else print("EQUAL")

### FIXED CODE ###

a,b = [int(input()) for _ in range(2)]
print("GREATER") if a>b else print("LESS") if a<b else print("EQUAL")