Lexicographically Minimal Trie Labeling

A trie is defined as follows:

• A trie of size \(n\) is a rooted tree with \(n\) vertices and \(n-1\) edges, where each edge is marked with a lowercase English letter.
• Each vertex \(x\) represents a string \(s(x)\). The root represents the empty string.
• If \(u\) is the parent of \(v\) and the edge connecting them is marked with character \(c\), then \(s(v)=s(u)+c\) (string concatenation).
• All strings represented by the vertices are distinct. In particular, the outgoing edges from any vertex must be labeled with distinct letters.

You are given a rooted tree with \(n+1\) vertices numbered \(0,1,\dots,n\) (vertex 0 is the root). There are \(m\) key vertices among them, denoted by \(k_1,k_2,\dots,k_m\). It is guaranteed that all leaves are key vertices.

Your task is to assign a lowercase English letter to each edge (i.e. for each vertex \(v\neq0\), assign a letter to the edge from its parent to \(v\)) such that the tree becomes a trie, and the following criterion is met:

Let \(A = \{ s(k_1), s(k_2), \dots, s(k_m) \}\) be the sequence of strings represented by the key vertices, and let \(B = \{ w_1, w_2, \dots, w_m \}\) be these strings sorted in lexicographic order (using the usual definition and using lexicographic ordering). Among all possible valid assignments, you should choose one that minimizes the sequence \(B\) in lexicographic order; that is, if \(F = \{ f_1,f_2,\dots,f_m \}\) is the sorted key string sequence obtained by your assignment and \(G = \{ g_1,g_2,\dots,g_m \}\) is that obtained by another valid assignment, then \(F\) is smaller than \(G\) if there exists an index \(t\) (\(1 \le t \le m\)) such that \(f_i = g_i\) for all \(1 \le i < t\) and \(f_t < g_t\) in lexicographic order.

Input Format:

1. The first line contains two integers \(n\) and \(m\) (note that the tree has \(n+1\) vertices).
2. The second line contains \(m\) distinct integers \(k_1,k_2,\dots,k_m\) indicating the key vertices.
3. The following \(n\) lines describe the tree. For each vertex \(i\) with \(1 \le i \le n\), a single integer \(p_i\) is given, meaning that vertex \(p_i\) is the parent of vertex \(i\). It is guaranteed that \(0 \le p_i < i\).

Output Format:

Output a single string of length \(n\). The \(i\)th character of the string (for \(1\le i\le n\)) should be the letter assigned to the edge connecting vertex \(p_i\) and vertex \(i\).

Note: In your assignment, for each vertex, the edges toward its children must receive distinct letters. For children that eventually lead to a key vertex (i.e. contain at least one key in their subtree), it is optimal to assign letters in increasing order (starting from a) based on the minimum distance (in edges) from the child to a key vertex. For children from which no key is reachable, any assignment works because they do not affect the sorted sequence \(B\).

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(n+1\) being the total number of vertices and \(m\) the number of key vertices).

The second line contains \(m\) distinct integers \(k_1, k_2, \ldots, k_m\), the indices of the key vertices.

Then \(n\) lines follow. The \(i\)th of these lines (for \(i=1,2,\ldots,n\)) contains a single integer \(p_i\) (\(0 \le p_i < i\)) indicating the parent of vertex \(i\).

outputFormat

Output a single string of length \(n\). The \(i\)th character is the letter on the edge from vertex \(p_i\) to vertex \(i\), for \(i=1,2,\ldots,n\).

sample

2 2
1 2
0
0

ab