問題文

日本には数字と短い文字列を対応させる語呂合わせの文化がある。

このことに興味を持った高橋君は、$1$ 以上 $K$ 以下の数字のみからなる正整数 $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$

• $1$ 行目には、整数 $K (1≦K≦9)$ と $N (1≦N≦50)$ が空白区切りで与えられる。
• $2$ 行目から $N$ 行には、数字と文字列の組に関する情報が与えられる。$N$ 行のうち $i (1≦i≦N)$ 行目には $1$ 以上 $K$ 以下の数字のみからなる整数 $v_i (1≦v_i≦10^9)$ と半角小文字英字のみからなる文字列 $w_i (1≦|w_i|≦27)$ が空白区切りで与えられる。
• $1$ 以上 $K$ 以下のどの数字も $v_1$, $v_2$, ... , $v_N$ のうち $1$ つ以上に登場する。
• 与えられる入力では、条件を満たす $K$ 個の文字列 $s_1$, $s_2$, ... , $s_K$ は必ず存在する。

部分点

この問題には部分点が設定されている。

• $K ≦ 3$ かつ $w_1$ から $w_N$ までのどの文字列も a, b, c のいずれかのみで構成されているデータセット $1$ に正解した場合は、$40$ 点が与えられる。
• 追加制約のないデータセット $2$ に正解した場合は、上記とは別に $60$ 点が与えられる。

出力

出力は $K$ 行からなる。$K$ 行のうち $i (1≦i≦K)$ 行目には文字列 $s_i$ を出力せよ。

条件を満たす $K$ 個の文字列の組み合わせが複数存在する場合は、それらの組み合わせのうちどの $1$ つを出力してもよい。

出力の末尾にも改行を入れること。

---

入力例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 と置くことによって題意を満たす $K$ 個の文字列とすることができる。実際に、

• $v_1 = 356$ を桁ごとに分解した場合に $3$, $5$, $6$ が得られ、$s_3 =$ mi, $s_5 =$ go, $s_6 =$ ro をこの順に連結した文字列 migoro は $w_1$ に等しい。
• $v_2 = 461$ を桁ごとに分解した場合に $4$, $6$, $1$ が得られ、$s_4 =$ yo, $s_6 =$ ro, $s_1 =$ i をこの順に連結した文字列 yoroi は $w_2$ に等しい。
• $v_3 = 2$ を桁ごとに分解した場合に $2$ が得られ、$s_2 =$ ni は $w_3$ に等しい。
• $v_4 = 12$ を桁ごとに分解した場合に $1$, $2$ が得られ、$s_1 =$ i, $s_2 =$ 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

---