Authors have come up with the string $s$ consisting of $n$ lowercase Latin letters.

You are given two permutations of its indices (not necessary equal) $p$ and $q$ (both of length $n$). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

For all $i$ from $1$ to $n-1$ the following properties hold: $s[p_i] \le s[p_{i + 1}]$ and $s[q_i] \le s[q_{i + 1}]$. It means that if you will write down all characters of $s$ in order of permutation indices, the resulting string will be sorted in the non-decreasing order.

Your task is to restore any such string $s$ of length $n$ consisting of at least $k$ distinct lowercase Latin letters which suits the given permutations.

If there are multiple answers, you can print any of them.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$) — the length of the string and the number of distinct characters required.

The second line of the input contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct integers from $1$ to $n$) — the permutation $p$.

The third line of the input contains $n$ integers $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$, all $q_i$ are distinct integers from $1$ to $n$) — the permutation $q$.


-----Output-----

If it is impossible to find the suitable string, print "NO" on the first line.

Otherwise print "YES" on the first line and string $s$ on the second line. It should consist of $n$ lowercase Latin letters, contain at least $k$ distinct characters and suit the given permutations.

If there are multiple answers, you can print any of them.


-----Example-----
Input
3 2
1 2 3
1 3 2

Output
YES
abb

Difficulty: introductory

Starter code:

Solutions:
n,k=map(int,input().split())
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
ab="abcdefghijklmnopqrstuvwxyz"
#print(len(ab))
ss={}
j=0
it=[]
for i in aa:
    ss[i]=j
    j+=1
jj=0
for i in bb:
    ind=ss[i]
    j,ind=sorted([jj,ind])
    it.append([j,ind])
  #  print(i,jj,ind)
    jj+=1
    
it.sort()
do=1
ma=it[0][1]
res=[]
st=it[0][0]

for i in it[1:]:
    if i[0]<=ma:
        ma=max(ma,i[1])
        
    else:
        do+=1
        res.append([st,ma])
        st=i[0]
        ma=i[1]

    j+=1
if res==[]:
    res=[[0,n-1]]
else:
    if res[-1][1]!=n-1:
        res.append([res[-1][1]+1,n-1])
if len(res)<k:
    print("NO")
else:
    print("YES")
    if len(res)>k:
      #  print(res[:k-1])
       # print(res)
        res=res[:k-1]+[[res[k-1][0],n-1]]
    kk=-1
    res.sort()
    ll=[0]*n
    for i in res:
        kk+=1
        for j in range(i[0],i[1]+1):
            ll[aa[j]-1]=ab[kk]
    for i in ll:
        print(i,end="")
    print()
    

    


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = list(map(int, input().split()))
d = [0]*(n+5)
for q in range(n):
    d[s[q]] = q
f, q2 = [], 0
for q in range(len(a)):
    if q-1 == q2:
        f.append(q)
    q2 = max(q2, d[a[q]])
f.append(n)
if len(f) < k:
    print('NO')
else:
    print('YES')
    g = [chr(ord('a')+q) for q in range(30)]
    ans = ['' for q in range(n)]
    q1 = 0
    for q in range(n):
        if f[q1] == q:
            q1 += 1
            q1 = min(q1, 25)
        ans[a[q]-1] = g[q1]
    print(''.join(ans))


n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
offs = ord("a")

ans = [chr(offs+k-1)] * n
# ans = ""
pmore = set()
qmore = set()

let = 0
# cnt = 0
for i in range(n):
    # cnt += 1
    pi = p[i]
    qi = q[i]
    if qi in pmore:
        pmore.remove(qi)
    else:
        qmore.add(qi)
    if pi in qmore:
        qmore.remove(pi)
    else:
        pmore.add(pi)

    ans[pi - 1] = chr(let+offs)
    if len(pmore) + len(qmore) == 0:
        
        let += 1
        if let == k:
            break



if let == k:
    # if len(ans) < n:
    #     ans += chr(offs+k-1) * (n- len(ans))
    print("YES")
    print("".join(ans))
else:
    print("NO")

from heapq import *


def solve(a, b):

    b_map = {i: idx for idx, i in enumerate(a)}

    intervals = []

    for idx, i in enumerate(b):
        f = b_map[i]
        intervals.append(sorted([f, idx]))

    intervals.sort(reverse=True)
    res = []
    endings = []
    for i in range(len(a)):
        while endings and endings[0] < i:
            heappop(endings)

        if not res:
            res.append(97)
        elif not endings:
            res.append(res[-1] + 1)
        else:
            res.append(res[-1])

        while intervals and intervals[-1][0] <= i:
            s, e = intervals.pop()
            heappush(endings, e)

    def build(k, r):
        res = [0] * len(k)

        for idx, i in enumerate(k):

            res[i - 1] = r[idx]

        return res
    # print(res)
    return build(a, res)


n, k = [int(i) for i in input().split()]

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

b = solve(a, b)
string = ''.join(chr(min(i, 97 + 25)) for i in b)
if len(set(string)) < k: print("NO")
else:
    print("YES")
    print(string)

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
p=set()
q=set()
literals=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
it=0
s=[0]*n
for i in range(n):
    p.add(a[i])
    q.add(b[i])
    s[a[i]-1]=literals[it]
    if a[i] in q:
        q.remove(a[i])
        p.remove(a[i])
    if b[i] in p:
        p.remove(b[i])
        q.remove(b[i])
    if not p and (not q):
        it=min(it+1,25)
        k-=1
if k<=0:
    arr=''
    print('YES')
    for item in s:
        arr+=item
    print(arr)
else:
    print('NO')


import sys


def main():
    n, m = [int(x) for x in sys.stdin.readline().strip().split()]
    p = [int(x) for x in sys.stdin.readline().strip().split()]
    q = [int(x) for x in sys.stdin.readline().strip().split()]

    sp = set()
    hashp = 0
    sq = set()
    hashq = 0

    res = ['z' for _ in range(n)]
    x = 0

    for c1, c2 in zip(p, q):
        sp.add(c1)
        hashp += c1 * c1
        sq.add(c2)
        hashq += c2 * c2

        if hashp == hashq and sp == sq:
            c = chr(ord('a') + x)
            x += 1
            for pos in sp:
                res[pos - 1] = c

            if x == m:
                print('YES')
                print(''.join(res))
                return

            sp.clear()
            hashp = 0
            sq.clear()
            hashq = 0


    print('NO')


main()


from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: list(map(int, rd().strip().split()))

lat = [chr(ord('a')+i) for i in range(26)]


n,k = rrd()

p = list(rrd())
q = list(rrd())

cnt = [0]*200005

ct = 0

ans = ['a']*n


now = 0
for i in range(n):
    if q[i] == p[i]:
        if ct == 0 and i:
            now += 1
            now = min(now,25)
        ans[q[i]-1] = lat[now]

    else:
        if ct == 0 and i:
            now += 1
            now = min(now,25)

        cnt[q[i]]+=1
        cnt[p[i]]+=1

        if cnt[q[i]] == 2:
            ct -= 1
        else:
            ct += 1
        if cnt[p[i]] == 2:
            ct -= 1
        else:
            ct += 1

        ans[p[i]-1] = lat[now]
        ans[q[i]-1] = lat[now]





if now+1 >= k:
    print("YES")
    print("".join(ans))
else:
    print("NO")







n, k = map(int,input().split())
l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))
d = {}
j = 1
for i in l1:
    d[i] = j
    j += 1
l = [d[i] for i in l2]
#l is the list that forces shit
wei = [0] * (n+2)
right = [0] * (n+2)
for i in range(n -1):
    #look at l[i], l[1+1]
    if l[i] < l[i+1]:
        continue
    wei[l[i+1]] += 1
    wei[l[i] + 1] -= 1
    right[l[i]] += 1
odcinki = []
l = 1
r = 1
pref = [0] * (n + 2)
for i in range(1, n+2):
    pref[i] = pref[i-1] + wei[i]
for i in range(1, n + 2):
    if pref[i] == 0:
        odcinki.append([l,r])
        l = i + 1
        r = i + 1
    else:
        if pref[i] == right[i]:
            odcinki.append([l,r])
            l = i + 1
            r = i + 1
 
        else:
            r += 1
if odcinki[0] == [1,1]:
	odcinki = odcinki[1:]
if odcinki[-1][0] == odcinki[-1][1] and odcinki[-1][0] > n:
	odcinki = odcinki[:-1]
 
lewe = [0] * (n+1)
prawe = [0] * (n+1)
for i in odcinki:
	lewe[i[0]] = 1
	prawe[i[1]] = 1
odp = [0] * (n+3)
i = -1
indx = 1
reg = 0
odp = [-1] * (n+3)
count = 0
while indx < n + 1:
	#i stays the same iff [5,6,7,8,9] we are 6,7,8,9
	if prawe[indx-1] == 1:
		reg = 0
	if lewe[indx] == 1:
		reg = 1
		count = 0
	odp[indx] = i
	#kiedy i += 1
	if count == 0 or reg == 0:
		i += 1
	count += 1
	odp[indx] = i
	indx += 1
odpp = [0] * (n + 3)
for i in range(n):
    odpp[l1[i]] = odp[i + 1]
odpp = odpp[1:-2]
if max(odpp) + 1 < k:
	print("NO")
else:
	print("YES")
	for i in range(n):
		print(chr(97+min(25, odpp[i])), end = "")

n, k = map(int, input().split())
p = list(map(int,input().split()))
q = list(map(int, input().split()))
sp = set()
sq = set()
chuj = 0
odp = [chr(96 + 26) for i in range(n)]
for i in range(n):
    odp[p[i] - 1] = chr(97 + chuj)
    if p[i] - 1 in sq:
        sq.remove(p[i] - 1)
    else:
        sp.add(p[i] - 1)
    if q[i] - 1 in sp:
        sp.remove(q[i] - 1)
    else:
        sq.add(q[i] - 1)
    if len(sp) + len(sq) == 0:
        chuj += 1
    if chuj == 26:
        break
if chuj < k:
    print("NO")
else:
    print("YES")
    print("".join(odp))

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
offs = ord("a")
 
ans = [chr(offs+k-1)] * n
# ans = ""
pmore = set()
qmore = set()
 
let = 0
# cnt = 0
for i in range(n):
    # cnt += 1
    pi = p[i]
    qi = q[i]
    if qi in pmore:
        pmore.remove(qi)
    else:
        qmore.add(qi)
    if pi in qmore:
        qmore.remove(pi)
    else:
        pmore.add(pi)
 
    ans[pi - 1] = chr(let+offs)
    if len(pmore) + len(qmore) == 0:
        
        let += 1
        if let == k:
            break
 
 
 
if let == k:
    # if len(ans) < n:
    #     ans += chr(offs+k-1) * (n- len(ans))
    print("YES")
    print("".join(ans))
else:
    print("NO")

n, k = list(map(int, input().split()))
s = [0] * n
for i, v in enumerate(map(int, input().split())):
    s[v-1] = i
t = [0] * n
for i, v in enumerate(map(int, input().split())):
    t[v-1] = i
p = [0] * n
for u, v in zip(s, t):
    if u == v: continue
    elif v < u: u, v = v, u
    p[u] += 1
    p[v] -= 1
r = [0] * n
cur = 0
nxt = -1
for i, v in enumerate(p):
    if cur == 0 and nxt < 25: nxt += 1
    r[i] = nxt
    cur += v

if nxt < k-1:
    print("NO")
else:
    print("YES")
    print("".join([chr(ord('a')+r[x]) for x in s]))



import math
n = 3
k = 2
 
p = [1,2,3]
q = [1,3,2]
 
n,k = [int(x) for x in input().split(' ')]
p = [int(x) -1 for x in input().split(' ')]
q = [int(x) -1 for x in input().split(' ')]
 

group_ids = []

 
p_ids = set()
q_ids = set()
for i in range(n):
    if p[i] in q_ids:
        q_ids.remove(p[i])
    else:
        p_ids.add(p[i])

    if q[i] in p_ids:
        p_ids.remove(q[i])
    else:
        q_ids.add(q[i])

    if not bool(p_ids) and not bool(q_ids):
        group_ids.append(i)

if len(group_ids) < k:
    print('NO')
    return
 
def get_letter(_id):
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    return alphabet[min(_id, len(alphabet)-1)]


print('YES')
result = [None] * n
l = 0
for i in range(len(group_ids)):
    r = group_ids[i]
    letter = get_letter(i)
    for it in range(l, r+1):
        result[p[it]] = letter
    l = r+1


 
print(''.join(result))

def main():
    n, m = list(map(int, input().split()))
    abc = list('zyxwvutsrqponmlkjihgfedcba'[26 - m:])
    res = [abc[0]] * (n + 1)
    res[0], pool, f = 'YES\n', [False] * (n + 1), 0
    for p, q in zip(list(map(int, input().split())),
                    list(map(int, input().split()))):
        if pool[p]:
            f -= 1
        else:
            pool[p] = True
            f += 1
        if pool[q]:
            f -= 1
        else:
            pool[q] = True
            f += 1
        res[p] = abc[-1]
        if not f:
            del abc[-1]
            if not abc:
                break
    print('NO' if abc else ''.join(res))


def __starting_point():
    main()

__starting_point()

import sys

inp = [int(x) for x in sys.stdin.read().split()]

n = inp[0]
k = inp[1]
P = inp[2:n + 2]
Q = inp[n + 2: n + n + 2]

letters = 'abcdefghijklmnopqrstuvwxyz'

index = [0] * n
for i in range(n):
    P[i] -= 1
    Q[i] -= 1
    index[P[i]] = i

intervals = []
for i in range(n - 1):
    if index[Q[i]] > index[Q[i + 1]]:
        intervals.append((index[Q[i + 1]], index[Q[i]]))

intervals.sort()
color = [0] * n
cur_color = 0
interval_idx = 0
last = -1
for i in range(n):
    if last < i:
        cur_color += 1
    color[i] = cur_color
    while interval_idx < len(intervals) and intervals[interval_idx][0] == i:
        last = max(last, intervals[interval_idx][1])
        interval_idx += 1

if cur_color < k:
    print('NO')
else:
    ans = ['a'] * n
    for i in range(n):
        ans[P[i]] = letters[min(25, color[i] - 1)]
    print('YES')
    print(''.join(ans))
    


import sys

inp = [int(x) for x in sys.stdin.read().split()]

n = inp[0]
k = inp[1]
P = inp[2:n + 2]
Q = inp[n + 2: n + n + 2]

index = [0] * n
for i in range(n):
    P[i] -= 1
    Q[i] -= 1
    index[P[i]] = i

intervals = []
for i in range(n - 1):
    if index[Q[i]] > index[Q[i + 1]]:
        intervals.append((index[Q[i + 1]], index[Q[i]]))

intervals.sort()
color = [0] * n
cur_color = 0
interval_idx = 0
last = -1
for i in range(n):
    if last < i:
        cur_color += 1
    color[i] = cur_color
    while interval_idx < len(intervals) and intervals[interval_idx][0] == i:
        last = max(last, intervals[interval_idx][1])
        interval_idx += 1

if cur_color < k:
    print('NO')
else:
    ans = ['a'] * n
    for i in range(n):
        ans[P[i]] = chr(min(25, color[i] - 1) + ord('a'))
    print('YES')
    print(''.join(ans))
    


# https://codeforces.com/contest/1213/problem/F

n, k = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

def get(cur):
    if cur>=97+25:
        return chr(97+25)
    return chr(cur)

pos = [0] * (n+1)
for i, x in enumerate(q):
    pos[x] = i
    
seg =[0]
cnt = 0
max_=-1

for i, x in enumerate(p):
    max_ = max(max_, pos[x])    
    if i == max_:
        cnt+=1
        seg.append(i+1)
        
if len(seg)-1<k:
    print('NO')
else:
    cur = 97 
    S   = []
    for s, e in zip(seg[:-1], seg[1:]):
        for i in range(s, e):
            S.append(cur)
        cur+=1    
    
    print('YES')
    print(''.join([get(S[pos[x]]) for x in range(1, n+1)]))        

import sys
input = sys.stdin.readline

from operator import itemgetter

N, K = map(int, input().split())
inP = list(map(int, input().split()))
inQ = list(map(int, input().split()))


P = [None]*N
for i, p in enumerate(inP):
    P[p-1] = i+1

Q = [None]*N
for i, q in enumerate(inQ):
    Q[q-1] = i+1

NUM = []
for i, (p, q) in enumerate(zip(P, Q)):
    NUM.append((i, p, q))

graph = [-1]*(N+1)
NUM.sort(key=itemgetter(2))
for i in range(N-1):
    pre = NUM[i][1]
    fow = NUM[i+1][1]
    graph[fow] = pre

NUM.sort(key=itemgetter(1))
Color = [-1]*(N+1)
color = 0
MAX = 1
for (ind, p, q) in NUM:
    if Color[p] == -1 and p > MAX:
        color += 1
    tmp = p
    while tmp != -1 and Color[tmp] == -1:
        MAX = max(MAX, tmp)
        Color[tmp] = color
        tmp = graph[tmp]

if color >= K-1:
    print("YES")
    ans = [None]*N
    for ind, p, q in NUM:
        c = Color[p]
        ans[ind] = chr(97+min(c, 25))
    print("".join(ans))
else:
    print("NO")