#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U>
using Pa = pair<T, U>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
class strong_components {
 public:
  vector<vector<int>> v, rv, nv;
  vector<int> rs, visited, cmp, cmp_size;
  vec<int> indeg;
  void dfs(int n) {
    visited[n] = 1;
    for (auto x : v[n])
      if (!visited[x]) dfs(x);
    rs.push_back(n);
  }
  void rdfs(int n, int cnt) {
    visited[n] = 1;
    cmp[n] = cnt;
    for (auto x : rv[n])
      if (!visited[x]) rdfs(x, cnt);
  }
  strong_components(int N, vector<vector<int>>& graph) {
    v = graph;
    rv = vector<vector<int>>(N);
    visited = cmp = cmp_size = indeg = vector<int>(N, 0);
    for (int i = 0; i < N; i++)
      for (auto x : v[i]) rv[x].push_back(i);
    for (int i = 0; i < N; i++)
      if (!visited[i]) dfs(i);
    for (int i = 0; i < N; i++) visited[i] = 0;
    int now = 0;
    for (int i = rs.size() - 1; i >= 0; i--)
      if (!visited[rs[i]]) rdfs(rs[i], now++);
    nv = vector<vector<int>>(now + 1);
    for (int i = 0; i < N; i++) {
      for (auto x : v[i]) {
        if (cmp[i] != cmp[x]) {
          nv[cmp[i]].push_back(cmp[x]);
          indeg[cmp[x]]++;
        }
      }
    }
    for (int i = 0; i < N; i++) cmp_size[cmp[i]]++;
  }
  int find(int n) { return cmp[n]; }
  int size(int n) { return cmp_size[cmp[n]]; }
  int getindeg(int n) { return indeg[cmp[n]]; }
  bool is_same_group(int a, int b) { return cmp[a] == cmp[b]; }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vec<int> P(N), Q(N);
  vvec<int> g(N + 1);
  for (int i = 0; i < N; i++) {
    cin >> P[i];
    if (i != 0) g[P[i - 1]].push_back(P[i]);
  }
  for (int i = 0; i < N; i++) {
    cin >> Q[i];
    if (i != 0) g[Q[i - 1]].push_back(Q[i]);
  }
  strong_components SCC(N + 1, g);
  vec<int> top;
  vec<int> d(N + 1, -1);
  queue<int> que;
  vec<int> indeg = SCC.indeg;
  vec<int> list;
  for (int i = 1; i <= N; i++)
    if (!indeg[SCC.find(i)] && d[SCC.find(i)] == -1) {
      que.push(SCC.find(i));
      list.push_back(SCC.find(i));
      d[SCC.find(i)] = 1;
    }
  vvec<int> D(N + 1);
  while (!que.empty()) {
    int cur = que.front();
    que.pop();
    for (auto& to : SCC.nv[cur]) {
      indeg[to]--;
      if (!indeg[to]) {
        que.push(to);
        list.push_back(to);
      }
    }
  }
  char c = 'a' - 1;
  int cnt = 0;
  vec<char> res(N + 1);
  for (auto v : list) {
    cnt++;
    if (c != 'z') {
      c++;
      res[v] = c;
    } else
      res[v] = c;
  }
  if (cnt < K) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  for (int i = 1; i <= N; i++) cout << res[SCC.find(i)];
  cout << "\n";
}

### Prompt

Create a solution in CPP for the following problem:

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] ≤ s[p_{i + 1}] and s[q_i] ≤ 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 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 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, ..., p_n (1 ≤ p_i ≤ 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, ..., q_n (1 ≤ q_i ≤ 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U>
using Pa = pair<T, U>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
class strong_components {
 public:
  vector<vector<int>> v, rv, nv;
  vector<int> rs, visited, cmp, cmp_size;
  vec<int> indeg;
  void dfs(int n) {
    visited[n] = 1;
    for (auto x : v[n])
      if (!visited[x]) dfs(x);
    rs.push_back(n);
  }
  void rdfs(int n, int cnt) {
    visited[n] = 1;
    cmp[n] = cnt;
    for (auto x : rv[n])
      if (!visited[x]) rdfs(x, cnt);
  }
  strong_components(int N, vector<vector<int>>& graph) {
    v = graph;
    rv = vector<vector<int>>(N);
    visited = cmp = cmp_size = indeg = vector<int>(N, 0);
    for (int i = 0; i < N; i++)
      for (auto x : v[i]) rv[x].push_back(i);
    for (int i = 0; i < N; i++)
      if (!visited[i]) dfs(i);
    for (int i = 0; i < N; i++) visited[i] = 0;
    int now = 0;
    for (int i = rs.size() - 1; i >= 0; i--)
      if (!visited[rs[i]]) rdfs(rs[i], now++);
    nv = vector<vector<int>>(now + 1);
    for (int i = 0; i < N; i++) {
      for (auto x : v[i]) {
        if (cmp[i] != cmp[x]) {
          nv[cmp[i]].push_back(cmp[x]);
          indeg[cmp[x]]++;
        }
      }
    }
    for (int i = 0; i < N; i++) cmp_size[cmp[i]]++;
  }
  int find(int n) { return cmp[n]; }
  int size(int n) { return cmp_size[cmp[n]]; }
  int getindeg(int n) { return indeg[cmp[n]]; }
  bool is_same_group(int a, int b) { return cmp[a] == cmp[b]; }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vec<int> P(N), Q(N);
  vvec<int> g(N + 1);
  for (int i = 0; i < N; i++) {
    cin >> P[i];
    if (i != 0) g[P[i - 1]].push_back(P[i]);
  }
  for (int i = 0; i < N; i++) {
    cin >> Q[i];
    if (i != 0) g[Q[i - 1]].push_back(Q[i]);
  }
  strong_components SCC(N + 1, g);
  vec<int> top;
  vec<int> d(N + 1, -1);
  queue<int> que;
  vec<int> indeg = SCC.indeg;
  vec<int> list;
  for (int i = 1; i <= N; i++)
    if (!indeg[SCC.find(i)] && d[SCC.find(i)] == -1) {
      que.push(SCC.find(i));
      list.push_back(SCC.find(i));
      d[SCC.find(i)] = 1;
    }
  vvec<int> D(N + 1);
  while (!que.empty()) {
    int cur = que.front();
    que.pop();
    for (auto& to : SCC.nv[cur]) {
      indeg[to]--;
      if (!indeg[to]) {
        que.push(to);
        list.push_back(to);
      }
    }
  }
  char c = 'a' - 1;
  int cnt = 0;
  vec<char> res(N + 1);
  for (auto v : list) {
    cnt++;
    if (c != 'z') {
      c++;
      res[v] = c;
    } else
      res[v] = c;
  }
  if (cnt < K) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  for (int i = 1; i <= N; i++) cout << res[SCC.find(i)];
  cout << "\n";
}

```