该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

复合词查找

题目描述

给定一个按字典序排列的小写单词字典，请你找出其中所有的双词复合词。 双词复合词的定义为：该单词本身存在于字典中，且恰好可以由字典中另外两个存在的单词首尾拼接而成。

输入格式

标准输入包含若干行，每行一个仅由小写英文字母组成的单词，所有单词按字典序升序排列。 输入的单词总数不超过 120000 个。

输出格式

请输出所有符合条件的双词复合词，每行一个，按字典序升序排列。

样例输入 1

a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra

样例输出 1

alien
newborn

样例输入 2

a
air
airport
at
b
bed
bedroom
c
cat
d
do
dog
ed
g
in
input
out
output
port
put
room
t

样例输出 2

at
airport
bed
bedroom
cat
dog
input
output

数据范围与提示

• 每个单词仅由小写英文字母构成，无空格、特殊符号等其他字符。
• 输入保证严格按字典序升序给出，无需额外对输入进行排序。
• 拆分后的两个单词，允许是同一个单词（例如字典中存在 a 和 aa，则 aa 符合复合词定义）。