Harryxun/stf_run huggingface dataset:
s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()


for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        ans += la[i]*(3**lq[i])*rc[i]*(3**rq[i]) + lq[i]*(3**(lq[i]-1))*rc[i]*(3**rq[i]) + la[i]*(3**lq[i])*rq[i]*(3**(rq[i]-1)) + lq[i]*(3**(lq[i]-1))*rq[i]*(3**(rq[i]-1))
        ans %= 10**9+7

print(int(ans))


### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:50:56 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

city = [False for i in range(N)]
city[1-1] =True
now = 1

counta1 = 0
while True:
    counta1 += 1
    prev = now
    now = A[now-1]
    print(prev,now,counta1)
    if city[now-1]:
        break
    elif counta1 == K:
        print(now)
        sys.exit()
    else:
        city[now-1] = True

counta = 1
rout = []
rout.append(now)
while now != prev:
    now = A[now-1]
    rout.append(now)
    counta +=1
    print(now,rout,counta)

ans = rout[(K-counta1) % counta]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:50:56 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

city = [False for i in range(N)]
city[1-1] =True
now = 1

counta1 = 0
while True:
    counta1 += 1
    prev = now
    now = A[now-1]
#    print(prev,now,counta1)
    if city[now-1]:
        break
    elif counta1 == K:
        print(now)
        sys.exit()
    else:
        city[now-1] = True

counta = 1
rout = []
rout.append(now)
while now != prev:
    now = A[now-1]
    rout.append(now)
    counta +=1
#    print(now,rout,counta)

ans = rout[(K-counta1) % counta]
print(ans)
s = input()
k = int(input())

s_list = []
times = 0
flow = 0



for i in range(len(s)):
    s_list.append(s[i])


while True:
    if s_list[flow] == s_list[flow + 1]:
        times += 1
        flow += 2
    elif s_list[flow] != s_list[flow + 1]:
        flow += 1

    if flow >= len(s) - 1:
        break

if s.count(s[len(s)-1]) % 2 == 1 :
    if s[0] == s[len(s)-1]:
        times += 1



print(times*k)



### FIXED CODE ###

s = list(input())
k = int(input())
S = s.copy()
S_3 =s.copy()
cnt = 0
cnt_2 = 0
cnt_3 = 0


for i in range(1, len(s)):
    if s[i-1] == s[i]:
        cnt += 1
        s[i] = "A"

# --------------------------

for i in range(len(s)):
    S.append(S[i])

for i in range(1, len(S)):
    if S[i-1] == S[i]:
        cnt_2 += 1
        S[i] = "A"

# if k == 1:
#     print(cnt)
# else:
#     print(cnt + (cnt_2 - cnt) * (k-1))

# ---------------------------------------

for i in range(len(S)):
    S_3.append(S_3[i])

for i in range(1, len(S_3)):
    if S_3[i-1] == S_3[i]:
        cnt_3 += 1
        S_3[i] = "A"

# --------------------------------------

if k == 1:
    print(cnt)
elif k == 2:
    print(cnt_2)
elif k == 3:
    print(cnt_3)
elif cnt_2 - cnt == cnt_3 - cnt_2:
    print(cnt + (cnt_2 - cnt) * (k-1))
else:
    if k % 2 == 0:
        print(int(cnt + (cnt_2 - cnt) * (k / 2) + (cnt_3 - cnt_2) * (k / 2 - 1)))
    else:
        print(int(cnt + (cnt_2 - cnt) * ((k - 1) / 2) + (cnt_3 - cnt_2) * ((k - 1) / 2)))
n = int(input())
a = [int(input()) for i in range(n)]
j = 0
k = 0

if 1 not in a:
    print(-1)
else:   
    for i in range(1,n+1):
        if i in a[k:]:
            j = j + 1
            k = a[k:].index(i) + k
        else:
            break
    print(n-j)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
x = 1
ans = 0

for i in a:
    if i == x:
        ans += 1
        x += 1

if ans == 0:
    print(-1)
else:
    print(len(a)-ans)
a=[]
s=[]
a[0],a[1],k=map(int(input().split()))
for i in range(max(a)):
  if a[0]%i==0 and a[1]%i==0:
    s.append(i)
print(s[k])

### FIXED CODE ###

a=[0,0]
s=[]
a[0],a[1],k=map(int,input().split())
for i in range(1,min(a)+1):
  if a[0]%i==0 and a[1]%i==0:
    s.append(i)
print(s[len(s)-k])
N = int(input())
H = list(map(int, input().split()))

ans = 0

for i in reversed(range(0, N-1)):
    if H[i] > h[i+1] + 1:
        ans += 1
    elif H[i] == h[i+1] + 1:
        h[i] -= 1

if ans == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

ans = 'Yes'

for i in reversed(range(0, N-1)):
    if H[i] > H[i+1] + 1:
        ans = 'No'
    elif H[i] == H[i+1] + 1:
        H[i] -= 1

print(ans)
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = [list(input()) for _ in range(H)]

counts = np.empty((H, W))
counts.fill(np.inf)


def ok_range(h, w):
    return 0 <= h < H and 0 <= w < W


# 左上から右下へ DP してく
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 左下から右上へ
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 右上から左下
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

# 右下から左上
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

print(int(counts.max()))


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = np.array([list(input()) for _ in range(H)])

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))
a=input()

s=['x','SAT','FRY','THU','WED','TUE','MON','SUN']

print(s.index(a))

### FIXED CODE ###

a=input()

s=['x','SAT','FRI','THU','WED','TUE','MON','SUN']

print(s.index(a))
a,b,c = int(input())
if a < b and b < c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

inp=input().split()
if inp[0] < inp[1] and inp[1] < inp[2]:
    print("Yes")
else:
    print("No")
import math
return math.pi*2*R

### FIXED CODE ###

import math
a = int(input())
print(2 * a * math.pi)
num = int(input())
a = list(map(int, input().split()))
count = 0
while(True):
    for i in range(num):
        if a[i] % 2 != 0:
            break
        else:
            a[i] /= 2
    else:
        count += 1
        continue
    break
print(count)

### FIXED CODE ###

a,b=list(map(int,input().split()))
if a*b%2==0:
  print("Even")
else:
  print("Odd")
N = int(input())

tmp = input().split(" ")

als = [0]*(10**5)

for n in tmp:
    nowNum = int(n)
    als[nowNum - 1] += 1
    als[nowNum] += 1
    als[nowNum + 1] += 1


    
print(max(als))


### FIXED CODE ###

N = int(input())

tmp = input().split(" ")

als = [0]*(10**5 + 10)

for n in tmp:
    nowNum = int(n)
    als[nowNum - 1] += 1
    als[nowNum] += 1
    als[nowNum + 1] += 1


    
print(max(als))
a,b = map(int,input().split())
dp = [0]*(100010)
qp = [0]*(100010)
for i in range(b):
    ta,tb = map(str,input().split())
    ta = int(ta)
    if qp[ta] == 0 :
        if tb == 'WA':dp[ta]+=1
        else qp[ta]=1
print(sum(qp),sum(dp))

### FIXED CODE ###


a,b = map(int,input().split())
dp = [0]*(100010)
qp = [0]*(100010)
for i in range(b):
    ta,tb = map(str,input().split())
    ta = int(ta)
    if qp[ta] == 0 :
        if tb == 'WA':
            dp[ta]+=1
        else :
            qp[ta]=1
ANS = 0
for i, j in zip(dp,qp):
    ANS += i*j
print(sum(qp),ANS)
import numpy
import math
import collections
from decimal import *
import sys

def main():
    n = int(input())
    a = sorted(input_list())
    max_n = 10 ** 18
    ans = 1
    for v in a:
        ans *= v
        if ans > max_n:
            ans = -1
            break
        if ans == 0:
            break
    print(ans)


def yogen(a, b, angle):
    coss = math.cos((angle/180)*math.pi)
    return math.sqrt(a**2 + b**2 - 2*a*b*coss)


def get_angle(hour, minute):
    h = (hour * 360) / 12 + (minute * 360) / (12 * 60)
    m = (minute * 360) / 60
    angle = abs(h-m)
    return min(angle, 360-angle)

def has(v, l):
    for vl in l:
        if v == vl:
            return True
    return False

def input_list():
    return list(map(int, sys.stdin.readline().split()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy
import math
import sys

def main():
    n = int(input())
    a = sorted(input_list())
    max_n = 10 ** 18
    ans = 1
    for v in a:
        ans *= v
        if ans > max_n:
            ans = -1
            break
        if ans == 0:
            break
    print(ans)


def yogen(a, b, angle):
    coss = math.cos((angle/180)*math.pi)
    return math.sqrt(a**2 + b**2 - 2*a*b*coss)


def get_angle(hour, minute):
    h = (hour * 360) / 12 + (minute * 360) / (12 * 60)
    m = (minute * 360) / 60
    angle = abs(h-m)
    return min(angle, 360-angle)

def has(v, l):
    for vl in l:
        if v == vl:
            return True
    return False

def input_list():
    return list(map(int, sys.stdin.readline().split()))


if __name__ == '__main__':
    main()
S = map(int,input().split)
a = 0
while a >= 4:
    if S = "+":
        a += 1
    else:
        a -= 1    
print(a)        

### FIXED CODE ###

S = input()
print(S.count("+")-S.count("-"))
# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    get_ln_inputs()
    rates = get_ln_int_inputs()

    colors = list()
    for _ in range(8):
        colors.append(0)

    free_colors = 0
    for rate in rates:
        if rate >= 3200:
            free_colors += 1
        else:
            colors[rate // 400] = 1
    fixed_colors = sum(colors)

    print(str(fixed_colors) + " " + str(fixed_colors + free_colors))


main()

### FIXED CODE ###

# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    if int("".join(get_ln_inputs())) % 4 == 0:
        print("YES")
    else:
        print("NO")


main()
k = list(map(int,input().split()))
t = k[0] // k[3]
a = k[2] // k[1]
if t >= k:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

k = list(map(int, input().split() ) )
t = 1
while k[0] > 0 and k[2] > 0:
  if t == 1:
    k[2] -= k[1]
    t=2
  else:
    k[0] -= k[3]
    t=1
if t==2:
  print("Yes")
else:
  print("No")
from math import sqrt

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

L = []

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    for j in L:
        if i%j==0: 
            break
    else:
        if G%i==0: 
            L.append(i)

print(len(L)+1)   


### FIXED CODE ###


n = int(input())

if n%2==0:
    print(0.5)
else:
    print((n//2+1)/n)
n=int(input())
data=[[0]*30 for i in range(30)]

for i in range(n):
    s=input()
    l=len(s)
    num=0
    sho=0
    keta=1
    for i in range(l):
        if(s[l-i-1]!='.'):
            num+=keta*int(s[l-i-1])
            keta*=10
        else:
            sho=i
    #print(num,sho)
    two=-sho
    five=-sho
    for i in range(100):
        if(num%2==0):
            two+=1
            num//=2
        else:
            break
    for i in range(100):
        if(num%5==0):
            five+=1
            num//=5
        else:
            break
    #print(two,five)
    data[two+9][five+9]+=1


ans=0
for i in range(30):
    for j in range(30):
        jibun=data[i][j]
        if(jibun==0):
            continue
        aite=0
        for p in range(max(0,18-i),30):
            for q in range(max(0,18-j),30):
                aite+=data[p][q]
                if(p==i and j==q):
                    aite-=1
        ans+=jibun*aite
        #print(i-9,j-9,jibun,aite)

print(ans//2)

### FIXED CODE ###

n=int(input())
data=[[0]*50 for i in range(50)]

for i in range(n):
    s=input()
    l=len(s)
    num=0
    sho=0
    keta=1
    for i in range(l):
        if(s[l-i-1]!='.'):
            num+=keta*int(s[l-i-1])
            keta*=10
        else:
            sho=i
    #print(num,sho)
    two=-sho
    five=-sho
    for i in range(100):
        if(num%2==0):
            two+=1
            num//=2
        else:
            break
    for i in range(100):
        if(num%5==0):
            five+=1
            num//=5
        else:
            break
    #print(two,five)
    data[two+9][five+9]+=1


ans=0
for i in range(50):
    for j in range(50):
        jibun=data[i][j]
        if(jibun==0):
            continue
        aite=0
        for p in range(max(0,18-i),50):
            for q in range(max(0,18-j),50):
                aite+=data[p][q]
                if(p==i and j==q):
                    aite-=1
        ans+=jibun*aite
        #print(i-9,j-9,jibun,aite)

print(ans//2)
x,y = map(int,input().split())
if ord(x)<ord(y):
    print('<')
elif ord(x) == ord(y):
    print('=')
else:
    print('>')


### FIXED CODE ###

x,y = input().split()
if ord(x)<ord(y):
    print('<')
elif ord(x) == ord(y):
    print('=')
else:
    print('>')
import sys, itertools

n = int(sys.stdin.readline())
MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin = 0
m = MM[0][:]
for i in range(n-1):
    amin += m[0]*m[1]*MM[i+1][1]
    m[1]=MM[i+1][1]


for t in itertools.permutations(range(n-1), n-2):

    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-2):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]
        if ans>amin: break
        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1
    else:
        ans += mm[0][0]*mm[0][1]*mm[1][1]
        if amin>ans: amin=ans


print(amin)


### FIXED CODE ###

import sys

n = int(sys.stdin.readline())

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

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

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))
import sys

import os
path = os.getcwd()
path = os.path.join(path,"input.txt")
sys.stdin = open(path)

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

dp = 0
i = 0
while i<N-1:
    if i == N-2:
        dp += abs(H[N-1]-H[i])
        break
    if abs(H[i+1]-H[i]) < abs(H[i+2]-H[i]):
        dp += abs(H[i+1]-H[i])
        i += 1
    else:
        dp += abs(H[i+2]-H[i])
        i += 2
print(dp)
        

### FIXED CODE ###

import sys



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

dp = 0
i = 0
dp = [0]*(N)
for i in range(1,N):
    if i ==1:
        dp[i] = dp[i-1] + abs(H[i]-H[i-1])
        continue
    dp[i] = min(dp[i-1] + abs(H[i]-H[i-1]),dp[i-2] + abs(H[i]-H[i-2]))

print(dp[N-1])
(n,m),*a=[[*map(int,i.split())]for i in open(0)]
c=[0]*-~n
id={}
for p,y in sorted(a,key=lambda x:x[1]):
    c[p]+=1
    id[y]=format(p,"06")+format(c[p],"06")
for _,y in a:
    print(id[y])

### FIXED CODE ###

n,m=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(m)]
c=[0]*-~n
id={}
for p,y in sorted(a,key=lambda x:x[1]):
    c[p]+=1
    id[y]=format(p,"06")+format(c[p],"06")
for _,y in a:
    print(id[y])
N, X = map(int,input().split())

L = input().split()
pos = 0
for i in range(N+1):
  pos += int(L[i])
  if(pos > X):
    break
  
print(i+1)


### FIXED CODE ###

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

L = input().split()
pos = 0
ans = 1
for i in range(N):
  pos += int(L[i])
  if(pos <= X):
    ans +=1
  else:
    break
  
print(ans)
n,k = map(int,input().split())
s = input()

if s[k] == "A":
  s=s[0:k]+"a"+s[k+1:n]
elif s[k] == "B":
  s=s[0:k]+"b"+s[k+1:n]
else:
  s=s[0:k]+"c"+s[k+1:n]
print(s)

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
 
if s[k-1] == "A":
  s=s[0:k-1]+"a"+s[k:n]
elif s[k-1] == "B":
  s=s[0:k-1]+"b"+s[k:n]
else:
  s=s[0:k-1]+"c"+s[k:n]
print(s)
## まきもどし？
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
ceil = math.ceil
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    #print(x,ls)
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    #rewind
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)
#print(ls)
for a in ans :
    print(a)


### 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
ceil = math.ceil
import sys
sys.setrecursionlimit(10**6)
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    #print(x,ls)
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    #rewind
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)
#print(ls)
for a in ans :
    print(a)