问题描述

日本有一种将数字与短字符串对应的发音文化。

高橋君对这个事情很感兴趣，他想从由正整数 $v_1$, $v_2$, ..., $v_N$ 和对应的字符串 $w_1$, $w_2$, ..., $w_N$ 构成的组合 ($v_1$, $w_1$), ($v_2$, $w_2$), ..., ($v_N$, $w_N$) 中推断出每个数字对应的字符串。

也就是说，我们要找到满足以下条件的 $K$ 个字符串 $s_1$, $s_2$, ..., $s_K$：

• 对于满足 $1≦i≦K$ 的任意整数 $i$，有 $1≦|s_i|≦3$。
• 对于满足 $1≦i≦N$ 的任意整数 $i$，将整数 $v_i$ 按位分解得到数字 $d_1$, $d_2$, ..., $d_l$，则将字符串 $s_{d_1}$, $s_{d_2}$, ..., $s_{d_l}$ 连接起来得到的字符串与 $w_i$ 相等。

请编写一个程序输出 $K$ 个字符串 $s_1$, $s_2$, ..., $s_K$。

输入

输入数据从标准输入读取。

输入的格式如下所示：

$K$ $N$

$v_1$ $w_1$

$v_2$ $w_2$

...

$v_N$ $w_N$

• 第一行包含两个整数 $K (1≦K≦9)$ 和 $N (1≦N≦50)$，以空格分隔。
• 第二行到第 $N$ 行包含数字和字符串对的信息。第 $i$ 行 $(1≦i≦N)$ 包含一个整数 $v_i (1≦v_i≦10^9)$ 和一个只包含小写字母的字符串 $w_i (1≦|w_i|≦27)$，以空格分隔。
• $1$ 到 $K$ 内的任何数字都将出现在 $v_1$, $v_2$, ..., $v_N$ 中的至少一个数字中。
• 提供的输入保证至少存在满足条件的 $K$ 个字符串 $s_1$, $s_2$, ..., $s_K$。

部分分

本问题包含部分分。

• 如果 $K ≤ 3$ 并且从 $w_1$ 到 $w_N$ 的所有字符串都由 a, b, c 组成，则对于数据集 $1$ 的正确答案将获得 $40$ 分。
• 如果没有附加约束的数据集 $2$ 得到正确答案，则将额外获得 $60$ 分。

输出

输出包含 $K$ 行。第 $i$ 行 $(1≦i≦K)$ 包含字符串 $s_i$。

如果满足条件的 $K$ 个字符串有多个组合，则可以输出其中的任何一个组合。

在输出的末尾添加换行符。

示例

输入示例1

6 4
356 migoro
461 yoroi
2 ni
12 ini

输出示例1

i
ni
mi
yo
go
ro

在此示例中，我们可以将 $s_1 =$ i，$s_2 =$ ni，$s_3 =$ mi，$s_4 =$ yo，$s_5 =$ go，$s_6 =$ ro，从而满足问题的条件。事实上，

• 当将 $v_1 = 356$ 按位分解时得到数字 $3$, $5$, $6$，将字符串 mi，go，ro 连接起来得到的字符串 migoro 与 $w_1$ 相等。
• 当将 $v_2 = 461$ 按位分解时得到数字 $4$, $6$, $1$，将字符串 yo，ro，i 连接起来得到的字符串 yoroi 与 $w_2$ 相等。
• 当将 $v_3 = 2$ 按位分解时得到数字 $2$，字符串 ni 与 $w_3$ 相等。
• 当将 $v_4 = 12$ 按位分解时得到数字 $1$, $2$，将字符串 i，ni 连接起来得到的字符串 ini 与 $w_4$ 相等。

注意，这个示例中的输入不满足数据集 $1$ 的条件。

输入示例2

3 4
21 aaa
12 aaa
123 aaaaaa
13 aaaa

输出示例2

a
aa
aaa

输入示例3

2 3
12211 abcaaaaabcabc
2121 aaabcaaabc
222221 aaaaaaaaaaabc

输出示例3

abc
aa

输入示例4

2 1
12 abcab

输出示例4

ab
cab