AT_abc031_d [ABC031D] 語呂合わせ

[problemUrl]: https://atcoder.jp/contests/abc031/tasks/abc031_d 日本には数字と短い文字列を対応させる語呂合わせの文化がある。 このことに興味を持った高橋君は、$ 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 $ 行からなる。$ K $ 行のうち $ i\ (1≦i≦K) $ 行目には文字列 $ s_i $ を出力せよ。 条件を満たす $ K $ 個の文字列の組み合わせが複数存在する場合は、それらの組み合わせのうちどの $ 1 $ つを出力してもよい。 出力の末尾にも改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ K\ ≦\ 3 $ かつ $ w_1 $ から $ w_N $ までのどの文字列も `a`, `b`, `c` のいずれかのみで構成されているデータセット $ 1 $ に正解した場合は、$ 40 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 この入力例では、$ 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 $ の条件を満たさないことに注意せよ。