Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

N = int(input())
VW = [[int(x)-1 for x in input().split()] for _ in range(N-1)]

"""
直径に次数1の頂点が生えている
"""

graph = [[] for _ in range(N)]
deg = [0] * N
for v,w in VW:
    graph[v].append(w)
    graph[w].append(v)
    deg[v] += 1
    deg[w] += 1

def dijkstra(start):
    INF = 10**10
    dist = [INF] * N
    q = [(start,0)]
    while q:
        qq = []
        for v,d in q:
            dist[v] = d
            for w in graph[v]:
                if dist[w] == INF:
                    qq.append((w,d+1))
        q = qq
    return dist

dist = dijkstra(0)
v = dist.index(max(dist))
dist = dijkstra(v)
w = dist.index(max(dist))
diag = v,w

def create_perm(v,parent,next_p,arr):
    next_v = None
    V1 = []
    V2 = []
    for w in graph[v]:
        if w == parent:
            continue
        if deg[w] == 1:
            V1.append(w)
        else:
            V2.append(w)
    if len(V1) == 0 and len(V2) == 0:
        arr.append(next_p)
        return
    if len(V2) > 0:
        next_v = V2[0]
    else:
        next_v = V1.pop()
    arr += list(range(next_p+1,next_p+len(V1)+1))
    arr.append(next_p)
    next_p += len(V1)+1
    create_perm(next_v,v,next_p,arr)

P = []
create_perm(diag[1],None,1,P)

Q = []
create_perm(diag[0],None,1,Q)

if len(P) != N:
    answer = -1
else:
    if P > Q:
        P = Q
    answer = ' '.join(map(str,P))
print(answer)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N = int(input())
VW = [[int(x)-1 for x in input().split()] for _ in range(N-1)]

"""
直径に次数1の頂点が生えている
"""

graph = [[] for _ in range(N)]
deg = [0] * N
for v,w in VW:
    graph[v].append(w)
    graph[w].append(v)
    deg[v] += 1
    deg[w] += 1

def dijkstra(start):
    INF = 10**10
    dist = [INF] * N
    q = [(start,0)]
    while q:
        qq = []
        for v,d in q:
            dist[v] = d
            for w in graph[v]:
                if dist[w] == INF:
                    qq.append((w,d+1))
        q = qq
    return dist

dist = dijkstra(0)
v = dist.index(max(dist))
dist = dijkstra(v)
w = dist.index(max(dist))
diag = v,w

def create_perm(start):
    arr = []
    v = start
    parent = None
    next_p = 1
    while True:
        n = 0
        next_v = None
        for w in graph[v]:
            if w == parent:
                continue
            if next_v is None or deg[next_v] < deg[w]:
                next_v = w
            if deg[w] == 1:
                n += 1
        if next_v is None:
            return arr + [next_p]
        if deg[next_v] == 1:
            n -= 1
        arr += list(range(next_p+1,next_p+n+1))
        arr.append(next_p)
        next_p += n+1
        parent = v
        v = next_v

P = create_perm(diag[1])

Q = create_perm(diag[0])

if len(P) != N:
    answer = -1
else:
    if P > Q:
        P = Q
    answer = ' '.join(map(str,P))
print(answer)
n = int(input())
aaa = list(map(int,input().split()))
def hantei(n,aaa):
    dp = [0]*(n+1)
    dp[0] = 0
    dp[1] = abs(aaa[1]-aaa[0])
    for i in range(n-2):
        dp[i+2] = min(dp[i+1]+abs(aaa[i+2]-aaa[i+1]),dp[i]+abs(aaa[i+2]-aaa[i]))
    return dp[n-1]
hantei(n)

### FIXED CODE ###

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

def hantei(n,aaa):
	dp = [0]*(n+1)
	dp[0] = 0
	dp[1] = abs(aaa[1]-aaa[0])
	for i in range(n-2):
		dp[i+2] = min(dp[i+1]+abs(aaa[i+2]-aaa[i+1]),dp[i]+abs(aaa[i+2]-aaa[i]))
	return dp[n-1]

print(hantei(n,aaa))
from collections import defaultdict
N = int(input())
##
v = defaultdict(lambda: [])
d = defaultdict(lambda: defaultdict(lambda: 0))
##
for i in range(N-1):
    a,b,c = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
##
reached = defaultdict(lambda: 0)
def f(p,pcd):
    global v,d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in v[p]:
        if reached[c] == 0:
            f(c, pcd+d[p][c])
f(K,0)
##
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
D = [0]*(N+1)
def f(v,p,cost):
    global T,K,D
    for C in T[v]:
        if C[0]!=p:
            D[C[0]] = cost+C[1]
            f(C[0],v,cost+C[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x]+D[y])
in_data = input()
data = in_data.split(' ')
A = data[0]
B = data[1]
c = (B - 1) // (A - 1)
 
print(c)

### FIXED CODE ###

in_data = input()
 
data = in_data.split(' ')
A = int(data[0])
B = int(data[1])
if B == 1:
  print("0")
else:
  c = (B - 1) // (A - 1)
  d = (B - 1) / (A - 1)
  if c < d:
    c = c + 1
  print(c)
a_list = []
for i in range(3):
    for j in list(map(int, input().split())):
        a_list.append()

N = int(input())

b_list = []
for i in range(N):
    b_list.append(int(input()))    
        
for b in b_list:
    if b in a_list:
        a_list[a_list.index(b)] = 0
# 123
# 456
# 789
# とした場合のビンゴラインごとのリスト
line_list = [
    a_list[:3],    # 123
    a_list[3:6],   # 456
    a_list[6:9],   # 789
    a_list[::3],   # 147
    a_list[1::3],  # 258
    a_list[2::3],  # 369
    a_list[::4],   # 159
    a_list[2:7:2], # 357    
]
line_sum_list = list(map(sum, line_list))
if 0 in line_sum_list:
    print('Yes')
else:
    print('No') 

### FIXED CODE ###

a_list = []
for i in range(3):
    for j in list(map(int, input().split())):
        a_list.append(j)

N = int(input())

b_list = []
for i in range(N):
    b_list.append(int(input()))    
        
for b in b_list:
    if b in a_list:
        a_list[a_list.index(b)] = 0
# 123
# 456
# 789
# とした場合のビンゴラインごとのリスト
line_list = [
    a_list[:3],    # 123
    a_list[3:6],   # 456
    a_list[6:9],   # 789
    a_list[::3],   # 147
    a_list[1::3],  # 258
    a_list[2::3],  # 369
    a_list[::4],   # 159
    a_list[2:7:2], # 357    
]
line_sum_list = list(map(sum, line_list))
if 0 in line_sum_list:
    print('Yes')
else:
    print('No')
n = 1
while n <= 10000
    x = input('Case {0}:'.format(n))
    if int(x) == 0:
        break


### FIXED CODE ###

for i in range(10000):
    x = input()
    if int(x) == 0:
        break
    print('Case ', i+1, ': ', x, sep='')
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=input()
print([K-1])

### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(list[K-1])
a = int(input())
b = input()
c = int(input())
d = b[c]
for i in range(a):
    if b[i]!=d :
        b = b.replace(b[i],'*')
print(b)

### FIXED CODE ###

a = int(input())
b = input()
c = int(input())
d = b[c-1]
for i in range(a):
    if b[i]!=d :
        b = b.replace(b[i],'*')
print(b)
n = int(input())
p =[int,input().split()for i in range(n)]

m = max(p)/2
print(m+sum(p)-max(p))

### FIXED CODE ###

n = int(input())
p =[int(input())for i in range(n)]

m = max(p)//2
print(m+sum(p)-max(p))
from fractions import gcd
import sys
sys.setrecursionlimit(10**7) 

N,A,B,K=map(int,input().split())
mod = 998244353
#x!のmodP逆元を求めるx^-1=x^(p-2)
table=[1]
a=1
for i in range(1,N+1):
    a=(a*pow(i,mod-2,mod))%mod
    table.append(a)

num=1
for i in range(1,N+1):
    num = (num*i) %mod


number =0
for i in range(N):
    if (K-A*i)%B==0:
        j=(K-A*i)//B
        t = (num*num)%mod
        t = (t*table[i])%mod
        t = (t*table[j])%mod
        t = (t*table[N-i])%mod
        t = (t*table[N-j])%mod
        number = (number+t)%mod
print(number)

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod = 998244353
#x!のmodP逆元を求めるx^-1=x^(p-2)
table=[1]
a=1
for i in range(1,N+1):
    a=(a*pow(i,mod-2,mod))%mod
    table.append(a)

num=1
for i in range(1,N+1):
    num = (num*i) %mod


number =0
for i in range(N+1):
    if (K-A*i)%B==0 and K-A*i>=0:
        j=(K-A*i)//B
        if 0<=j<=N:
            t = (num*num)%mod
            t = (t*table[i])%mod
            t = (t*table[j])%mod
            t = (t*table[N-i])%mod
            t = (t*table[N-j])%mod
            number = (number+t)%mod
print(number)
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
if x<y:
    y=x
    x,y=y,x
if 2y<x:
    print(0)
    exit()
mod=10**9+7
a=(2y-x)//3
b=(2x-y)//3
mx=10**6*2
k=[1]*(mx+1)
def inv(n):
    return pow(n,mod-2,mod)
for i in range(mx):
    k[i+1]=k[i]*(i+1)%mod
ans=(k[w+h]*inv(k[w])*inv(k[h]))%mod
print(ans)

### FIXED CODE ###

x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    exit()
if x<y:
    x,y=y,x
if 2*y<x:
    print(0)
    exit()
mod=10**9+7
a=(2*y-x)//3
b=(2*x-y)//3
mx=10**6
k=[1]*(mx+1)
def inv(n):
    return pow(n,mod-2,mod)
for i in range(mx):
    k[i+1]=k[i]*(i+1)%mod
ans=(k[a+b]*inv(k[a])*inv(k[b]))%mod
print(ans)
a, b, c, d = input().split()
a = int(a)#体力
b = int(b)
c = int(c)#体力
d = int(d)

x = a//d +1
y = c//b

if y == 1:
  if x <= y:
  	print("NO")
  print("No")
else:
  print("Yes")
print(x,y)

### FIXED CODE ###

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

if a > b:
  print('safe')
else:
  print('unsafe')
i = list(map(int,input().split()))
n = i[0]
l = i[1]
 
alist = []
i = 1
 
for i in range(n):
  x = l + i - 1
  alist.append(x)
  
   
j = 0
m = 0
for j in range(n):
  if abs(alist[k]) >= abs(alist[k+1]):
    m = k+1
  
  
print(sum(alist) - alist[m])
 

### FIXED CODE ###

i = list(map(int,input().split()))
n = i[0]
l = i[1]
 
alist = []
j = 0
 
for j in range(n):
  x = l + j
  alist.append(x)
  
   
k = 0
m = 0
for k in range(n-1):
  if abs(alist[k]) >= abs(alist[k+1]):
    m = k+1
  
  
print(sum(alist) - alist[m])
N=input()
if N[-1] in [2,4,5,7,9]:
  print("hon")
elif N[-1] in [0,1,6,8]:
  print("pon"
else:
  print("bon")

### FIXED CODE ###

N=input()
if int(N[-1]) in [2,4,5,7,9]:
  print("hon")
elif int(N[-1]) in [0,1,6,8]:
  print("pon")
else:
  print("bon")
#include<iostream>
using namespace std;

int main(){
    int k;
    int n=7;
    int count=1;

    cin>>k;

    while(n%k != 0){
        if(k%2=0){
            count=-1;
            break;
        }
        else(k%5=0){
            count=-1;
            break;
        }
        n=10*n+7;
        count++;
    }
    cout<<count<<"\n";

}
                                                       

### FIXED CODE ###

k=int(input())
a=[]
judge=0
a.append("")
a.append(7%k)
for i in range(2,k+1):
    a.append((a[i-1]*10+7)%k)
for i in range(1,k+1):
    if a[i]==0:
        print(i)
        judge=1
        break
if judge==0:
    print(-1)
a = list(map(string, input.split()))
res = 0

num = a.pop(0) * 2

for i in range(a):
    if (a[i] == 'BTC'):
        b = int(a[i-1]) * 380000
        res += b
    elif (a[i] == 'JPY'):
        res += int(a[i-1])
    else:
        pass

print(res) 

### FIXED CODE ###

a = int(input())

b = []

for i in range(a):
    b.append(input().split())

res = 0

for i in b:
    if (i[1] == 'BTC'):
        res += float(i[0])*380000
    else:
        res += int(i[0])

print(res)
n=int(input())
for j in range(n):
    p=[float(i) for i in input().split()]
    ab=round((p[3]-p[1])/(p[2]-p[0]),5)
    cd=round((p[7]-p[5])/(p[6]-p[4]),5)
    if ab==cd:
        print("YES")
    else:
        print("NO")



### FIXED CODE ###

n=int(input())
for j in range(n):
    p=[float(i) for i in input().split()]
    if round((p[2]-p[0])*(p[7]-p[5])-(p[3]-p[1])*(p[6]-p[4]),10)==0:
        print("YES")
    else:
        print("NO")
n = int(input())
a = [int(i) for i in input().split()]
count = 0
i = 0
 
while a[i]%2 == 0:
  if a[i]%2 ==0:
    a[i]//=2
  if i == n-1:
    count +=1
    i = 0
  i += 1
print(count)


### FIXED CODE ###

s = input()
 
x = 0
 
 
for i in range(len(s)):
  if s[i] == "1":
    x += 1
  
print(x)
import numpy as np

N, A, B, C = map(int,input().split())
goals = [A,B,C]
for i in range(N):
    ls.append(int(input()))

# goals = [1000,800,100]
# ls = [300,333,400,444,500,555,600,666]
# goals = [100, 90, 80]
# ls = [98, 40,30,21,80]

def count(x,ls):
    try:
        x.index(0)
        x.index(1)
        x.index(2)        
    except:
        return False
    A = np.zeros(len(goals))
    for i,l in enumerate(ls):
        add_ind = x[i]
        if add_ind==3:
            pass
        else:
            A[add_ind] += l
    combine_MP = 0
    for i in range(3):
        combine_MP += 10*(x.count(i)-1)
    return A, combine_MP
    
    
score_min = 100000
for N in range(4**8):
    x = []
    for j in range(len(ls)):
        x.append(N % 4)
        N = N // 4 
    try:
        A, combine_MP = count(x,ls)
        score = np.abs(A-np.array(goals)).sum() + combine_MP
        if score_min >= score:
            score_min = score
    except:
        pass
print(score_min)

### FIXED CODE ###

import numpy as np

N, A, B, C = map(int,input().split())
goals = [A,B,C]
ls = []
for i in range(N):
    ls.append(int(input()))

# goals = [1000,800,100]
# ls = [300,333,400,444,500,555,600,666]
# goals = [100, 90, 80]
# ls = [98, 40,30,21,80]

def count(x,ls):
    try:
        x.index(0)
        x.index(1)
        x.index(2)        
    except:
        return False
    A = np.zeros(len(goals))
    for i,l in enumerate(ls):
        add_ind = x[i]
        if add_ind==3:
            pass
        else:
            A[add_ind] += l
    combine_MP = 0
    for i in range(3):
        combine_MP += 10*(x.count(i)-1)
    return A, combine_MP
    
    
score_min = 100000
for N in range(4**8):
    x = []
    for j in range(len(ls)):
        x.append(N % 4)
        N = N // 4 
    try:
        A, combine_MP = count(x,ls)
        score = np.abs(A-np.array(goals)).sum() + combine_MP
        if score_min >= score:
            score_min = score
    except:
        pass
print(int(score_min))
N,K = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
if a_sum < K:
    print(N)
    exit()
if a_sum == K:
    print(0)
    exit()
count = 0
L = [i for i in a if i < K]
L_sum = sum(L)
if L_sum < K:
    print(len(N))
    exit()
if a_sum == K:
    print(0)
    exit()
for i in L:
    if L_sum - i >= K:
        count += 1
print(count)


### FIXED CODE ###

N,K = map(int,input().split())
a = sorted(map(int,input().split()))

count = N
s = 0
for i in range(N-1,-1,-1):
    if s + a[i] < K:
        s += a[i]
    else:
        count = min(i,count)
print(count)
N=list(int(input()))
cnt=N.count('2')
print(cnt)

### FIXED CODE ###


N=input()
cnt=N.count('2')
print(cnt)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    Min = 2000000000000
    divisors = make_divisors(int(input()))
    if len(divisors)%2==1:
        divisors[len(divisors)] = divisors[len(divisors)-1]
    #print(divisors)
    for i in range(0,len(divisors)-1,2):
        Min = min(divisors[i]+divisors[i+1],Min)
    print(Min-2)

main()

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    Min = 2000000000000
    divisors = make_divisors(int(input()))
    if len(divisors)%2==1:
        divisors.append(divisors[len(divisors)-1])
    #print(divisors)
    for i in range(0,len(divisors)-1,2):
        Min = min(divisors[i]+divisors[i+1],Min)
    print(Min-2)

main()
s=input()
t=input()
a = len(s)
b = len(t)
l = []
for i in range(a-b+1):
    cnt = 0
    c = s[i,i+t]
    for x, y in zip(c, t):
        if x != y:
            cnt +=1
    l.append(cnt)
print(min(l))

### FIXED CODE ###

D,T,S=map(int,input().split())
if S*T >=D:
    print('Yes')
else:
    print('No')
import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=0
for i in range(0,M):
  p.append(list(map(int, input().split())))
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  for j in range(1,min(10,M)):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count+=1
    if count%2==1:
      print("NO")
      sys.exit()
  elif M>10:
    for j in range(M-10,M+1):
      for i in range(0,M):
        if p[i][0]==j or p[i][1]==j:
          count+=1
      if count%2==1:
        print("NO")
        sys.exit()
  else:
    print("YES")

### FIXED CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
for i in range(0,N):
  p.append(0)
for i in range(0,M):
  count=list(map(int, input().split()))
  p[count[0]-1]+=1
  p[count[1]-1]+=1
for i in range(0,M):
  if p[i]%2==1:
    print("NO")
    sys.exit()
print("YES")
c=raw_input()
if c==a or a==e or a==i or a==o or a==u:
  print "vowel"
else:
  print "consonant"

### FIXED CODE ###

c=raw_input()
if c in "a,e,i,o,u":
  print "vowel"
else:
  print "consonant"
import sys

D,T,S = [int(i) for i in sys.stdin.readline()]

if(S*T>=D):
	print("Yes")
else:
	print("No")

### FIXED CODE ###

import sys

D,T,S = [int(i) for i in sys.stdin.readline().split()]

if(S*T>=D):
	print("Yes")
else:
	print("No")
o = "Yes"
for v in collections.Counter(input().strip()).values():
    if v % 2 != 0: o = "No"
print(o)

### FIXED CODE ###

import collections
o = "Yes"
for v in collections.Counter(input().strip()).values():
    if v % 2 != 0: o = "No"
print(o)
import sys
import numpy as np
from numba import njit

#@njit('i8(i8,i8[:],i8[:,:])')
def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE' and 0:
    import numba
    from numba.pycc import CC
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc.export('main', 'i8(i8,i8[:],i8[:,:])')
    cc.compile()

from my_module import main

N = int(input())
S = np.array([ord(_) for _ in input()])
dp = np.zeros((N + 1, N + 1), dtype=int)
print(main(N, S, dp))


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
from collections import deque
s = input()
k = int(input())
a = ord("a")
l = deque(list())
l1 = []
for i in range(len(s)):
    s1 = s[i]
    l.append(((a+26)-ord(s1))%26)
#print(l)
while k!=0:
    if len(l)!=0:
        t = l.popleft()
        if k>=t:
            l1.append("a")
            k -= t
        else:
          if t=="a":
            l1.append(t)
          else:
            l1.append(chr((ord('a')-t+26)))
    else:
        l1[-1] = chr(int(ord(l1[-1])+k))
        k = 0
l2 = []
if len(l)>=1:
  for t in l:
    if t==0:
      l2.append("a")
    else:
      l2.append(chr((ord('a')-t+26)))
  l1 += l2
print("".joiin(l1))

### FIXED CODE ###

from collections import deque
s = input()
k = int(input())
a = ord("a")
l = deque(list())
l1 = []
for i in range(len(s)):
  s1 = s[i]
  l.append(((a+26)-ord(s1))%26)
#print(l)
while k!=0:
    if len(l)!=0:
        t = l.popleft()
        if k>=t:
            l1.append("a")
            k -= t
        else:
          if t=="a":
            l1.append(t)
          else:
            l1.append(chr((ord('a')-t+26)))
    else:
      k %= 26
      l1[-1] = chr(int(ord(l1[-1])+k))
      k = 0
l2 = []
if len(l)>=1:
  for t in l:
    t %= 26
    if t==0:
      l2.append("a")
    else:
      l2.append(chr((ord('a')-t+26)))
  l1 += l2
print("".join(l1))
table=list(map(int,input().split()))
i=2
k=0
if k < i :
    while table[k] > table[k+1] :
        table[k],table[k+1]=table[k+1],table[k]
        k+=1
print(table[0],table[1],table[2])


### FIXED CODE ###

a,b,c=map(int,input().split())
if a > b :
    tmp=a
    a=b
    b=tmp
if b > c :
    tmp=b
    b=c
    c=tmp
if a > b:
    tmp=a
    a=b
    b=tmp
print(a,b,c)
for i in range(n):
  a = input()
  if a[0] == "M":Mnum+=1
  elif a[0] == "A":Anum+=1
  elif a[0] == "R":Rnum+=1
  elif a[0] == "C":Cnum+=1
  elif a[0] == "H":Hnum+=1
alist = []
alist.append(Mnum)
alist.append(Anum)
alist.append(Rnum)
alist.append(Cnum)
alist.append(Hnum)
from itertools import combinations
blist =list(combinations(alist,3))
from functools import reduce
sum = 0
for i in range(len(blist)):
  sum+=reduce(mul,blist)
print(sum)

### FIXED CODE ###

n = int(input())
Mnum = 0
Anum = 0
Rnum = 0
Cnum = 0
Hnum = 0
for i in range(n):
  a = input()
  if a[0] == "M":
    Mnum+=1
  elif a[0] == "A":
    Anum+=1
  elif a[0] == "R":
    Rnum+=1
  elif a[0] == "C":
    Cnum+=1
  elif a[0] == "H":
    Hnum+=1
alist = []
alist.append(Mnum)
alist.append(Anum)
alist.append(Rnum)
alist.append(Cnum)
alist.append(Hnum)
from itertools import combinations
print(sum([a*b*c for a,b,c in combinations(alist,3)]))
n=int(input())
a=list(map(int,input().split(" ")))
deta=[]
error=False
try:
  for i in range(n):
    if error:
      break
    elif a[i] in deta:
      error=True
    
if error:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
deta = set()
error = False

for i in range(n):
    if n == 0:
        pass
    elif error:
        break
    elif a[i] in deta:
        error = True
        break
    deta.add(a[i])
if error:
    print("NO")
else:
    print("YES")
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
a,b = ma()
k2 = abs(b-a)
if k%2==1:
    print(k2//2+min(b,a))
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
a,b = ma()
k2 = abs(b-a)
if k2%2==0:
    print(k2//2+min(b,a))
else:
    print("IMPOSSIBLE")
import math
def nroot(a, n, x=1.0, eps=1e-7):
    while abs(a - x**n) > eps:
        x = ( (n-1)*x + a/(x**(n-1)) ) / n
    return x
a,b,c=map(int,input().split())



if sqrtl(a)+sqrtl(b) < sqrtl(c):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a,b,c=map(int,input().split())
if a+b<c and 4*a*b<(c-a-b)**2:
    print("Yes")
else:
    print("No")
N = int(input())
arr = [int(input()) for i in range(N)]
c = 0
col_min = []

for i in range(N-1, -1, -1):
  if i == N-1:
    col_min.append(arr[i])
    c += 1
  else:
    check = 0
    for k, v in enumerate(col_min):
      if v > arr[i]
      	col_min[k] = arr[i]
        check = 1
        break
    if check == 0:
      col_min.append(arr[i])
      c += 1
print(c)

### FIXED CODE ###

import bisect
N = int(input())
arr = [int(input()) for i in range(N)]
dp = [-1 for _ in range(N)]
for i in arr:
    dp[bisect.bisect_left(dp, i) - 1] = i
print(sum([i >= 0 for i in dp]))
N, K = map(int, input().split())
S=input()
if S[K] == "A":
    ans = S[:K] + "a" + S[K+1:]
elif S[K] == "B":
    ans = S[:K] + "b" + S[K+1:]
else:
    ans = S[:K] + "c" + S[K+1:]
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S=input()
if S[K-1] == "A":
    ans = S[:K-1] + "a" + S[K:]
elif S[K-1] == "B":
    ans = S[:K-1] + "b" + S[K:]
else:
    ans = S[:K-1] + "c" + S[K:]
print(ans)
a = int(input())

b=[]
for i in range(a):
	b.append(int(input()))
x = 0
 
if (a==0) :
	print('DENIED')
elif (b.count(0) > 0):
	print('DENIED')
else:
  for i in b:
      if i % a == 0:
          x += 1
  if x == len(b):
      print('APPROVED')

### FIXED CODE ###

a = int(input())
 
b=list(map(int, input().split())) 
x = 0
c = 0
    
for i in b:
  if ((i % 3 == 0) or (i % 5 == 0)) and (i % 2 == 0):
    x += 1

for t in b:
  if (t%2==0):
    c += 1;

if x == c:
  print('APPROVED')
else :
  print('DENIED')