题目背景

wapapapapoo觉得土木迟早药丸，于是改行学生物。

她想编写一个程序，计算限制性内切酶切割DNA链的产物。

限制性内切酶可以匹配DNA链上的特定识别序列，然后在该序列上的切割位点处将DNA链切割。

题目描述

给定一个DNA链的碱基序列，以及若干限制性内切酶的识别序列，计算它们反应完毕后产生了哪些产物。

限制性内切酶并不能完全切割所有的切割位点。

如识别序列为5'-G^AATTC-3'的限制性内切酶切割碱基序列为5'-GAATTC-3'的DNA链时，会产生5'-GAATTC-3'、5'-G-3'和5'-AATTC-3'三种产物。

输入格式

第一行输入一个正整数$n$，代表加入限制性内切酶的种数。

此后$n$行输入$n$个限制性内切酶的识别序列，切割位点用^表示。

最后一行输入DNA链的碱基序列，只考虑单链。

输入的序列均为5'端到3'端。

输出格式

按照字典序顺序，输出所有可能的产物。

样例

1
G^AATTC
TACAGGATGCAACTCCTGTCTTGCATTGCACTAAGTCTTGCACTTGTCACGAATTCG

AATTCG
TACAGGATGCAACTCCTGTCTTGCATTGCACTAAGTCTTGCACTTGTCACG
TACAGGATGCAACTCCTGTCTTGCATTGCACTAAGTCTTGCACTTGTCACGAATTCG

提示说明

DNA链长度不超过1023个碱基，限制性内切酶识别序列不超过8个碱基。

$0\leq n\leq3$，且数据保证匹配的酶切位点不会超过3个。