HZNUOJ

解开束缚缠丝

Tags:
Time Limit:  1 s      Memory Limit:   64 MB
Submission:142     AC:26     Score:100.00

Description

双胞胎外星人梅珠朗冒充岸勇副队长,摧毁了TPC月球表面基地卡罗后,回到了地球上的TPC远东总部,把罪行全部推到了疾风队长身上,并调包了总监等人,对胜利队做出种种限制。大古和丽娜队员出发去宇宙寻找疾风队长,在了解到真相后回到地球,揭穿了梅珠朗的阴谋。迪迦奥特曼随后出现,打败了梅珠朗。

打败了双胞胎外星人后,大古一行人回到了总部,准备将被茧困住的众人救出。这时他们发现,怪兽的茧变得坚固无比,无法直接撕开茧,使用枪械又怕伤到里面的人,于是崛井队员开始分析茧的化学式,发现这种茧由多种外星元素组成。现在他要找到茧中比较容易被分解出来的元素,从这里打开茧。

我们已知所有的外星元素均由区分大小写的、数量不超过$6$个的英文字母组成。茧是一种线性结构的物质,其化学式中的元素由'-'(不包括引号)连接。现在崛井队员想知道某个元素是不是其中比较容易被分解出的元素。

我们在给出需要查找的元素$a_1$时,同时会给出另外两个元素$a_2$与$a_3$。我们约定元素$a_1$是比较容易被分解出来的定义如下:

为了解救被缚在茧里的众人,请你帮助崛井队员一起判断元素$a_1$是否是茧中比较容易被分解出来的元素。

线性结构的相关理解在下方Hint中。

Input

第一行包含一个正整数$T(1 \leq T \leq 10)$,代表有$T$组数据。

对于每一组数据:

第一行包含一个正整数$n(1 \leq n \leq 10^3)$,表示茧的化学式中包含的元素个数。

接下来的一行包含一个字符串$s(1 \leq |s| \leq 10^5)$,表示茧的化学式。

随后一行包含$3$个用一个空格隔开的字符串$a_1$,$a_2$,$a_3$,含义如题意所示。

题目保证在最多$10$组数据里,所有茧的化学式的长度(包括'-')的和不超过$10^5$

Output

对于每组数据,输出包含一行。

如果能在茧中找到一个比较容易分解出来的元素$a_1$,则输出这个元素$a_1$以及它左边和右边的第一个元素,用'-'(没有引号)连接。如果$a_1$的左边或右边没有元素,则不用输出对应的元素。如果有多个$a_1$满足条件,则按照输出格式输出从左到右第一个符合条件的$a_1$。如果不能找到符合条件的$a_1$元素,则输出$-1$。

Samples

input
5 4 Au-Ag-Cu-Fe Cu Au Ag 8 Au-Ag-Cu-Fe-Au-Fe-Cu-Fe Cu Au Ag 4 Weiwei-NS-hao-shuai Weiwei shuai ns 8 Lanche-ACM-De-Shen-Zhu-dA-jIa-AK ACM Lanche DE 4 Fa-ha-xi-ki nee k o
output
Ag-Cu-Fe Ag-Cu-Fe Weiwei-NS -1 -1

Hint

你可以将题目中的线性结构类似地理解成数组。对于茧的化学式中的元素,除最后元素之外,其它元素均有唯一的"后继";除第一元素之外,其它元素均有唯一的"前驱"。

当然,只要你看懂了题目,不需要对线性结构有更多的了解也能写出本题。

Author

SHAO, Tiefu