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
[{"code": "n,k=map(int,input().split())\naa=list(map(int,input().split()))\nbb=list(map(int,input().split()))\nab=\"abcdefghijklmnopqrstuvwxyz\"\n#print(len(ab))\nss={}\nj=0\nit=[]\nfor i in aa:\n    ss[i]=j\n    j+=1\njj=0\nfor i in bb:\n    ind=ss[i]\n    j,ind=sorted([jj,ind])\n    it.append([j,ind])\n  #  print(i,jj,ind)\n    jj+=1\n    \nit.sort()\ndo=1\nma=it[0][1]\nres=[]\nst=it[0][0]\n\nfor i in it[1:]:\n    if i[0]<=ma:\n        ma=max(ma,i[1])\n        \n    else:\n        do+=1\n        res.append([st,ma])\n        st=i[0]\n        ma=i[1]\n\n    j+=1\nif res==[]:\n    res=[[0,n-1]]\nelse:\n    if res[-1][1]!=n-1:\n        res.append([res[-1][1]+1,n-1])\nif len(res)<k:\n    print(\"NO\")\nelse:\n    print(\"YES\")\n    if len(res)>k:\n      #  print(res[:k-1])\n       # print(res)\n        res=res[:k-1]+[[res[k-1][0],n-1]]\n    kk=-1\n    res.sort()\n    ll=[0]*n\n    for i in res:\n        kk+=1\n        for j in range(i[0],i[1]+1):\n            ll[aa[j]-1]=ab[kk]\n    for i in ll:\n        print(i,end=\"\")\n    print()\n    \n\n    \n", "passed": true, "time": 0.14, "memory": 14348.0, "status": "done"}, {"code": "n, k = list(map(int, input().split()))\na = list(map(int, input().split()))\ns = list(map(int, input().split()))\nd = [0]*(n+5)\nfor q in range(n):\n    d[s[q]] = q\nf, q2 = [], 0\nfor q in range(len(a)):\n    if q-1 == q2:\n        f.append(q)\n    q2 = max(q2, d[a[q]])\nf.append(n)\nif len(f) < k:\n    print('NO')\nelse:\n    print('YES')\n    g = [chr(ord('a')+q) for q in range(30)]\n    ans = ['' for q in range(n)]\n    q1 = 0\n    for q in range(n):\n        if f[q1] == q:\n            q1 += 1\n            q1 = min(q1, 25)\n        ans[a[q]-1] = g[q1]\n    print(''.join(ans))\n", "passed": true, "time": 0.14, "memory": 14424.0, "status": "done"}, {"code": "n, k = [int(i) for i in input().split()]\np = [int(i) for i in input().split()]\nq = [int(i) for i in input().split()]\noffs = ord(\"a\")\n\nans = [chr(offs+k-1)] * n\n# ans = \"\"\npmore = set()\nqmore = set()\n\nlet = 0\n# cnt = 0\nfor i in range(n):\n    # cnt += 1\n    pi = p[i]\n    qi = q[i]\n    if qi in pmore:\n        pmore.remove(qi)\n    else:\n        qmore.add(qi)\n    if pi in qmore:\n        qmore.remove(pi)\n    else:\n        pmore.add(pi)\n\n    ans[pi - 1] = chr(let+offs)\n    if len(pmore) + len(qmore) == 0:\n        \n        let += 1\n        if let == k:\n            break\n\n\n\nif let == k:\n    # if len(ans) < n:\n    #     ans += chr(offs+k-1) * (n- len(ans))\n    print(\"YES\")\n    print(\"\".join(ans))\nelse:\n    print(\"NO\")", "passed": true, "time": 0.23, "memory": 14384.0, "status": "done"}, {"code": "n,k=[int(x) for x in input().split()]\na=[int(x) for x in input().split()]\nb=[int(x) for x in input().split()]\np=set()\nq=set()\nliterals=['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']\nit=0\ns=[0]*n\nfor i in range(n):\n    p.add(a[i])\n    q.add(b[i])\n    s[a[i]-1]=literals[it]\n    if a[i] in q:\n        q.remove(a[i])\n        p.remove(a[i])\n    if b[i] in p:\n        p.remove(b[i])\n        q.remove(b[i])\n    if not p and (not q):\n        it=min(it+1,25)\n        k-=1\nif k<=0:\n    arr=''\n    print('YES')\n    for item in s:\n        arr+=item\n    print(arr)\nelse:\n    print('NO')\n", "passed": true, "time": 0.14, "memory": 14396.0, "status": "done"}, {"code": "import sys\n\n\ndef main():\n    n, m = [int(x) for x in sys.stdin.readline().strip().split()]\n    p = [int(x) for x in sys.stdin.readline().strip().split()]\n    q = [int(x) for x in sys.stdin.readline().strip().split()]\n\n    sp = set()\n    hashp = 0\n    sq = set()\n    hashq = 0\n\n    res = ['z' for _ in range(n)]\n    x = 0\n\n    for c1, c2 in zip(p, q):\n        sp.add(c1)\n        hashp += c1 * c1\n        sq.add(c2)\n        hashq += c2 * c2\n\n        if hashp == hashq and sp == sq:\n            c = chr(ord('a') + x)\n            x += 1\n            for pos in sp:\n                res[pos - 1] = c\n\n            if x == m:\n                print('YES')\n                print(''.join(res))\n                return\n\n            sp.clear()\n            hashp = 0\n            sq.clear()\n            hashq = 0\n\n\n    print('NO')\n\n\nmain()\n", "passed": true, "time": 1.39, "memory": 14264.0, "status": "done"}, {"code": "from sys import stdin\nfrom sys import setrecursionlimit as SRL; SRL(10**7)\nrd = stdin.readline\nrrd = lambda: list(map(int, rd().strip().split()))\n\nlat = [chr(ord('a')+i) for i in range(26)]\n\n\nn,k = rrd()\n\np = list(rrd())\nq = list(rrd())\n\ncnt = [0]*200005\n\nct = 0\n\nans = ['a']*n\n\n\nnow = 0\nfor i in range(n):\n    if q[i] == p[i]:\n        if ct == 0 and i:\n            now += 1\n            now = min(now,25)\n        ans[q[i]-1] = lat[now]\n\n    else:\n        if ct == 0 and i:\n            now += 1\n            now = min(now,25)\n\n        cnt[q[i]]+=1\n        cnt[p[i]]+=1\n\n        if cnt[q[i]] == 2:\n            ct -= 1\n        else:\n            ct += 1\n        if cnt[p[i]] == 2:\n            ct -= 1\n        else:\n            ct += 1\n\n        ans[p[i]-1] = lat[now]\n        ans[q[i]-1] = lat[now]\n\n\n\n\n\nif now+1 >= k:\n    print(\"YES\")\n    print(\"\".join(ans))\nelse:\n    print(\"NO\")\n\n\n\n\n\n", "passed": true, "time": 0.15, "memory": 15076.0, "status": "done"}, {"code": "n, k = map(int, input().split())\np = list(map(int,input().split()))\nq = list(map(int, input().split()))\nsp = set()\nsq = set()\nchuj = 0\nodp = [chr(96 + 26) for i in range(n)]\nfor i in range(n):\n    odp[p[i] - 1] = chr(97 + chuj)\n    if p[i] - 1 in sq:\n        sq.remove(p[i] - 1)\n    else:\n        sp.add(p[i] - 1)\n    if q[i] - 1 in sp:\n        sp.remove(q[i] - 1)\n    else:\n        sq.add(q[i] - 1)\n    if len(sp) + len(sq) == 0:\n        chuj += 1\n    if chuj == 26:\n        break\nif chuj < k:\n    print(\"NO\")\nelse:\n    print(\"YES\")\n    print(\"\".join(odp))", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}, {"code": "n, k = [int(i) for i in input().split()]\np = [int(i) for i in input().split()]\nq = [int(i) for i in input().split()]\noffs = ord(\"a\")\n \nans = [chr(offs+k-1)] * n\n# ans = \"\"\npmore = set()\nqmore = set()\n \nlet = 0\n# cnt = 0\nfor i in range(n):\n    # cnt += 1\n    pi = p[i]\n    qi = q[i]\n    if qi in pmore:\n        pmore.remove(qi)\n    else:\n        qmore.add(qi)\n    if pi in qmore:\n        qmore.remove(pi)\n    else:\n        pmore.add(pi)\n \n    ans[pi - 1] = chr(let+offs)\n    if len(pmore) + len(qmore) == 0:\n        \n        let += 1\n        if let == k:\n            break\n \n \n \nif let == k:\n    # if len(ans) < n:\n    #     ans += chr(offs+k-1) * (n- len(ans))\n    print(\"YES\")\n    print(\"\".join(ans))\nelse:\n    print(\"NO\")", "passed": true, "time": 0.23, "memory": 14244.0, "status": "done"}, {"code": "n, k = list(map(int, input().split()))\ns = [0] * n\nfor i, v in enumerate(map(int, input().split())):\n    s[v-1] = i\nt = [0] * n\nfor i, v in enumerate(map(int, input().split())):\n    t[v-1] = i\np = [0] * n\nfor u, v in zip(s, t):\n    if u == v: continue\n    elif v < u: u, v = v, u\n    p[u] += 1\n    p[v] -= 1\nr = [0] * n\ncur = 0\nnxt = -1\nfor i, v in enumerate(p):\n    if cur == 0 and nxt < 25: nxt += 1\n    r[i] = nxt\n    cur += v\n\nif nxt < k-1:\n    print(\"NO\")\nelse:\n    print(\"YES\")\n    print(\"\".join([chr(ord('a')+r[x]) for x in s]))\n\n", "passed": true, "time": 0.14, "memory": 14232.0, "status": "done"}, {"code": "import math\nn = 3\nk = 2\n \np = [1,2,3]\nq = [1,3,2]\n \nn,k = [int(x) for x in input().split(' ')]\np = [int(x) -1 for x in input().split(' ')]\nq = [int(x) -1 for x in input().split(' ')]\n \n\ngroup_ids = []\n\n \np_ids = set()\nq_ids = set()\nfor i in range(n):\n    if p[i] in q_ids:\n        q_ids.remove(p[i])\n    else:\n        p_ids.add(p[i])\n\n    if q[i] in p_ids:\n        p_ids.remove(q[i])\n    else:\n        q_ids.add(q[i])\n\n    if not bool(p_ids) and not bool(q_ids):\n        group_ids.append(i)\n\nif len(group_ids) < k:\n    print('NO')\n    return\n \ndef get_letter(_id):\n    alphabet = 'abcdefghijklmnopqrstuvwxyz'\n    return alphabet[min(_id, len(alphabet)-1)]\n\n\nprint('YES')\nresult = [None] * n\nl = 0\nfor i in range(len(group_ids)):\n    r = group_ids[i]\n    letter = get_letter(i)\n    for it in range(l, r+1):\n        result[p[it]] = letter\n    l = r+1\n\n\n \nprint(''.join(result))", "passed": true, "time": 0.14, "memory": 14304.0, "status": "done"}, {"code": "def main():\n    n, m = list(map(int, input().split()))\n    abc = list('zyxwvutsrqponmlkjihgfedcba'[26 - m:])\n    res = [abc[0]] * (n + 1)\n    res[0], pool, f = 'YES\\n', [False] * (n + 1), 0\n    for p, q in zip(list(map(int, input().split())),\n                    list(map(int, input().split()))):\n        if pool[p]:\n            f -= 1\n        else:\n            pool[p] = True\n            f += 1\n        if pool[q]:\n            f -= 1\n        else:\n            pool[q] = True\n            f += 1\n        res[p] = abc[-1]\n        if not f:\n            del abc[-1]\n            if not abc:\n                break\n    print('NO' if abc else ''.join(res))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "passed": true, "time": 0.15, "memory": 14292.0, "status": "done"}, {"code": "import sys\n\ninp = [int(x) for x in sys.stdin.read().split()]\n\nn = inp[0]\nk = inp[1]\nP = inp[2:n + 2]\nQ = inp[n + 2: n + n + 2]\n\nletters = 'abcdefghijklmnopqrstuvwxyz'\n\nindex = [0] * n\nfor i in range(n):\n    P[i] -= 1\n    Q[i] -= 1\n    index[P[i]] = i\n\nintervals = []\nfor i in range(n - 1):\n    if index[Q[i]] > index[Q[i + 1]]:\n        intervals.append((index[Q[i + 1]], index[Q[i]]))\n\nintervals.sort()\ncolor = [0] * n\ncur_color = 0\ninterval_idx = 0\nlast = -1\nfor i in range(n):\n    if last < i:\n        cur_color += 1\n    color[i] = cur_color\n    while interval_idx < len(intervals) and intervals[interval_idx][0] == i:\n        last = max(last, intervals[interval_idx][1])\n        interval_idx += 1\n\nif cur_color < k:\n    print('NO')\nelse:\n    ans = ['a'] * n\n    for i in range(n):\n        ans[P[i]] = letters[min(25, color[i] - 1)]\n    print('YES')\n    print(''.join(ans))\n    \n", "passed": true, "time": 0.15, "memory": 14380.0, "status": "done"}, {"code": "import sys\n\ninp = [int(x) for x in sys.stdin.read().split()]\n\nn = inp[0]\nk = inp[1]\nP = inp[2:n + 2]\nQ = inp[n + 2: n + n + 2]\n\nindex = [0] * n\nfor i in range(n):\n    P[i] -= 1\n    Q[i] -= 1\n    index[P[i]] = i\n\nintervals = []\nfor i in range(n - 1):\n    if index[Q[i]] > index[Q[i + 1]]:\n        intervals.append((index[Q[i + 1]], index[Q[i]]))\n\nintervals.sort()\ncolor = [0] * n\ncur_color = 0\ninterval_idx = 0\nlast = -1\nfor i in range(n):\n    if last < i:\n        cur_color += 1\n    color[i] = cur_color\n    while interval_idx < len(intervals) and intervals[interval_idx][0] == i:\n        last = max(last, intervals[interval_idx][1])\n        interval_idx += 1\n\nif cur_color < k:\n    print('NO')\nelse:\n    ans = ['a'] * n\n    for i in range(n):\n        ans[P[i]] = chr(min(25, color[i] - 1) + ord('a'))\n    print('YES')\n    print(''.join(ans))\n    \n", "passed": true, "time": 0.14, "memory": 14356.0, "status": "done"}, {"code": "# https://codeforces.com/contest/1213/problem/F\n\nn, k = map(int, input().split())\np = list(map(int, input().split()))\nq = list(map(int, input().split()))\n\ndef get(cur):\n    if cur>=97+25:\n        return chr(97+25)\n    return chr(cur)\n\npos = [0] * (n+1)\nfor i, x in enumerate(q):\n    pos[x] = i\n    \nseg =[0]\ncnt = 0\nmax_=-1\n\nfor i, x in enumerate(p):\n    max_ = max(max_, pos[x])    \n    if i == max_:\n        cnt+=1\n        seg.append(i+1)\n        \nif len(seg)-1<k:\n    print('NO')\nelse:\n    cur = 97 \n    S   = []\n    for s, e in zip(seg[:-1], seg[1:]):\n        for i in range(s, e):\n            S.append(cur)\n        cur+=1    \n    \n    print('YES')\n    print(''.join([get(S[pos[x]]) for x in range(1, n+1)]))        ", "passed": true, "time": 0.14, "memory": 14288.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nfrom operator import itemgetter\n\nN, K = map(int, input().split())\ninP = list(map(int, input().split()))\ninQ = list(map(int, input().split()))\n\n\nP = [None]*N\nfor i, p in enumerate(inP):\n    P[p-1] = i+1\n\nQ = [None]*N\nfor i, q in enumerate(inQ):\n    Q[q-1] = i+1\n\nNUM = []\nfor i, (p, q) in enumerate(zip(P, Q)):\n    NUM.append((i, p, q))\n\ngraph = [-1]*(N+1)\nNUM.sort(key=itemgetter(2))\nfor i in range(N-1):\n    pre = NUM[i][1]\n    fow = NUM[i+1][1]\n    graph[fow] = pre\n\nNUM.sort(key=itemgetter(1))\nColor = [-1]*(N+1)\ncolor = 0\nMAX = 1\nfor (ind, p, q) in NUM:\n    if Color[p] == -1 and p > MAX:\n        color += 1\n    tmp = p\n    while tmp != -1 and Color[tmp] == -1:\n        MAX = max(MAX, tmp)\n        Color[tmp] = color\n        tmp = graph[tmp]\n\nif color >= K-1:\n    print(\"YES\")\n    ans = [None]*N\n    for ind, p, q in NUM:\n        c = Color[p]\n        ans[ind] = chr(97+min(c, 25))\n    print(\"\".join(ans))\nelse:\n    print(\"NO\")", "passed": true, "time": 0.14, "memory": 14436.0, "status": "done"}]