D - 語呂合わせ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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

このことに興味を持った高橋君は、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