在组织大型活动时,主办方经常需要处理一些超出其专业范围的琐事。例如,EUC 2025 的首席裁判必须为活动的官方吉祥物取一个名字,同时满足以下限制条件:
- 该名字必须包含特定的单词作为子序列*,例如活动名称和地点。给定 $n$ 个必须包含的单词列表 $s_1, s_2, \dots, s_n$。
- 该名字不得包含去年的吉祥物名称 $t$ 作为子序列*。
请帮助首席裁判找到一个合法的吉祥物名称,或者确定不存在这样的名字。
- 如果字符串 $x$ 可以通过删除字符串 $y$ 中的某些字符(在任意位置)并保持剩余字符的顺序不变而得到,则称 $x$ 是 $y$ 的子序列。例如,
abc是axbycz的子序列,但不是acbxyz的子序列。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 200\,000$),表示必须作为子序列出现的单词数量。
接下来的 $n$ 行中,第 $i$ 行包含字符串 $s_i$ ($1 \le |s_i| \le 200\,000$,$s_i$ 由小写英文字母组成),表示必须作为子序列出现的单词列表中的第 $i$ 个单词。这些单词的总长度不超过 $200\,000$,即 $|s_1| + |s_2| + \dots + |s_n| \le 200\,000$。
最后一行包含字符串 $t$ ($1 \le |t| \le 200\,000$,$t$ 由小写英文字母组成),表示去年吉祥物的名称。
输出格式
如果存在合法的吉祥物名称,输出 YES。否则,输出 NO。
如果存在合法的名称,在下一行输出一个合法的名称。你输出的字符串长度必须不超过 $1\,000\,000$,且必须由小写英文字母组成。可以证明,如果存在合法的吉祥物名称,则一定存在满足这些额外约束的名称。
如果存在多个解,输出其中任意一个即可。
样例
输入 1
2 porto euc prague
输出 1
YES poretuco
说明 1
必须作为子序列出现的单词是 porto 和 euc,而不得作为子序列出现的单词是 prague。吉祥物有许多合法的名称,例如 poretuco 或 xxxpppeortoucyyyy。
如果选择 poretuco 作为吉祥物的名称,可以观察到 porto 和 euc 确实是其子序列(分别在 POReTucO 和 porEtUCo 中高亮显示),而 prague 不是,符合要求。
字符串 poretuc 不是合法的吉祥物名称,因为它不包含 porto 作为子序列。同样,字符串 poretucoague 也不是合法的吉祥物名称,因为它包含 prague 作为子序列。
输入 2
6 credit debit money rich bank capitalism trap
输出 2
YES moncrdebditeychankpitalism
输入 3
2 axiom choice io
输出 3
NO
输入 4
4 aaa aab abb bbb ba
输出 4
YES aaabbb