問題文
日本有一种制作双关语的文化,将数字与短字母串相匹配。
对此感兴趣的高桥先生,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