Problem Description

In Japan, there is a culture of wordplay where numbers are associated with short strings.

Takahashi, who is interested in this, decided to infer which numbers correspond to which strings from the pairs of positive integers \( v_1, v_2, \ldots, v_N \) consisting only of digits from 1 to \( K \) and their corresponding strings \( w_1, w_2, \ldots, w_N \) (i.e., pairs \( (v_1, w_1), (v_2, w_2), \ldots, (v_N, w_N) \)).

That is, he wants to find \( K \) strings \( s_1, s_2, \ldots, s_K \) that satisfy the following conditions:

• For any integer \( i \) satisfying \( 1 \leq i \leq K \), \( 1 \leq |s_i| \leq 3 \).
• For any integer \( i \) satisfying \( 1 \leq i \leq N \), when the integer \( v_i \) is decomposed digit by digit to get numbers \( d_1, d_2, \ldots, d_l \) from top to bottom, the concatenated string of \( s_{d_1}, s_{d_2}, \ldots, s_{d_l} \) in this order equals \( w_i \).

Write a program that outputs the \( K \) strings \( s_1, s_2, \ldots, s_K \).

Input Format

The input is given from the standard input in the following format:

\( K \) \( N \) \( v_1 \) \( w_1 \) \( v_2 \) \( w_2 \) : \( v_N \) \( w_N \)

• The first line contains the integers \( K \) (\( 1 \leq K \leq 9 \)) and \( N \) (\( 1 \leq N \leq 50 \)) separated by a space.
• The next \( N \) lines contain information about the pairs of numbers and strings. The \( i \)-th line (\( 1 \leq i \leq N \)) contains the integer \( v_i \) (\( 1 \leq v_i \leq 10^9 \)) consisting only of digits from 1 to \( K \) and the string \( w_i \) (\( 1 \leq |w_i| \leq 27 \)) consisting only of lowercase English letters, separated by a space.
• Every number from 1 to \( K \) appears in \( v_1, v_2, \ldots, v_N \) at least once.
• For the given input, there always exists a set of \( K \) strings \( s_1, s_2, \ldots, s_K \) that satisfy the conditions.

Output Format

The output consists of \( K \) lines. The \( i \)-th line (\( 1 \leq i \leq K \)) should contain the string \( s_i \).

If there are multiple combinations of \( K \) strings that satisfy the conditions, you may output any one of them.

Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

6 4
356 migoro
461 yoroi
2 ni
12 ini

Sample Output #1

i
ni
mi
yo
go
ro

Sample Input #2

3 4
21 aaa
12 aaa
123 aaaaaa
13 aaaa

Sample Output #2

a
aa
aaa

Sample Input #3

2 3
12211 abcaaaaabcabc
2121 aaabcaaabc
222221 aaaaaaaaaaabc

Sample Output #3

abc
aa

Sample Input #4

2 1
12 abcab

Sample Output #4

ab
cab

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where \( K \leq 3 \) and all strings from \( w_1 \) to \( w_N \) are composed only of a, b, or c, you will be awarded 40 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 60 points.

Sample Explanation 1

In this input example, by setting \( s_1 = \) i, \( s_2 = \) ni, \( s_3 = \) mi, \( s_4 = \) yo, \( s_5 = \) go, \( s_6 = \) ro, you can satisfy the problem's requirements. Indeed:

• Decomposing \( v_1 = 356 \) gives 3, 5, 6, and concatenating \( s_3 = \) mi, \( s_5 = \) go, \( s_6 = \) ro results in the string migoro, which equals \( w_1 \).
• Decomposing \( v_2 = 461 \) gives 4, 6, 1, and concatenating \( s_4 = \) yo, \( s_6 = \) ro, \( s_1 = \) i results in the string yoroi, which equals \( w_2 \).
• Decomposing \( v_3 = 2 \) gives 2, and \( s_2 = \) ni equals \( w_3 \).
• Decomposing \( v_4 = 12 \) gives 1, 2, and concatenating \( s_1 = \) i, \( s_2 = \) ni results in the string ini, which equals \( w_4 \).

Note that this input example does not satisfy the conditions of dataset 1.

见题面 Input 部分

见题面 Output 部分