Problem Statement

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

このことに興味を持った高橋君は、$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$ を出力するプログラムを作成せよ。

Input

入力は以下の形式で標準入力から与えられる。

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$ 点が与えられる。

Output

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

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

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