Description

勇者闯达到了魔王宫，经过多方观察，得到了一些有用的情报，现在他打算把这些情报传递出去。但是勇者的写作水平不高，他容易写错单词(如：is写成iz，there写成therr，所以传递情报的任务就交给了圣者航。圣者航需要将勇者的情报翻译成正确的文章并传递出去。

正确的文章的写作格式是：

1.文章第一行开头有两个空格。

2.如果有单词位于行末，由于单词长度太长，剩下的地方不够写完该单词，则将单词分成两个部分，并用‘-’符号进行连接。

比如当前行还剩4个字符，become 则会变成 beco-回车me

3.每句句首单词的第一个字母大写。

4.括号内的字母大写。

5.除了第一行，其他行首没有空格

6.同一行的每两个单词之间被且仅被一个空格隔开。

7.除括号(指 ‘(’ 和 ‘)’)外的所有标点符号(指除了字母外的所有字符)后都要跟一个空格，文章结尾处的标点符号后不能有空格。当该标点符号的右边相邻的是 ‘)’ 时，该标点符号后不需要跟空格。(如：(yes.))

8.当一个成对的括号外的左端或右端有字母时，相应的位置要有且只有一个空格(如：yes (no) yes和yes. (no). yes和(yes)(no)等情况)。

9.除上述情况外其他位置不存在空格。

勇者在写字时会放飞自己，因为在放松的情况下才能写出好文章，每两个单词间的距离可能非常长(两个单词间可能存在多个空格)。

圣者航找到了一份易错单词总结，里面记载了勇者会写错的单词。

勇者现在已经按照自己的习惯写出了一篇情报，现在圣者航需要根据他写出的情报、他平时的日常习惯，和勇者的易错单词总结，写出一份正确的文章。

勇者不会把单词记混，只会把单词记错。比如他会把to记成tw，tw为一个不存在的单词。单词的前后缀不算单词。

题目默认如果未出现在勇者易错单词总结中的单词勇者全部都知道如何拼写，并且会拼写正确。

你能帮贤者航翻译成一个正确的文章吗？

Input Format

第一行会输入一个正整数T(1≤T≤100)，表示题目有t组测试样例。

对于每组测试样例

第一行会输入三个正整数n（0≤n≤1e5），m(1≤m ≤ 1e5)，k（10≤k≤1e5）。n表示有n对勇者总结的易错单词。m表示接下来有m行输入，代表着勇者的情报有m行。k表示这标准文章每行允许的字符数量。每个单词不会超过20个字符。

接下来n行，每行有两个单词，表示容易易把后者写成前者，及后者为正确形式。

接下来m行，每行包括一个字符串，代表为勇者情报的正文。正文中保证只会出现以下几种字符，小写字母字符 a-z ，英文句号 ‘.’ 英文逗号 ‘,’ ，英文问号 ‘?’ ，英文括号 ‘(’ 和 ‘)’ 。

题目保证正文中每行输入的最后一个单词是完整的一个单词，并且每行至少会输入任意一个字符，不会出现括号的嵌套现象，括号一定会成对出现。

对于每组测试样例李华的作文的总作文字符数不会超过1e5。

Output Format

对于每组测试样例

输出圣者航翻译的正确的文章，每行应该有k个字符。

每组测试样例后要输出一个空行。

注意：用来连接单词的字符‘-’不计入k个字符数量中，此外，空格以及所有其他出现的字符都将计入k个字符的数量中。

2
4 5 90
hew how
justy justify
yets yet
tw to
hew can the train operators possibly justy yets another increase tw rail passenger fares?
it has become a grimly reliable annual ritual every January the cost of travelling by train rises
imposing a significant extra burden on those who have no option but tw use the rail network tw get tw work or otherwise.
this year is rise an average of there per cent may be a fraction lower than last year is
but it is still well above the official consumer price index (cpi)(cpi) measure of inflation.
5 7 130
af of
educatin education
ad and
cinee chinese
tradition traditional
as a result af globalization ad convenient interaction among different nations, a variety af native cultures are being or have been lost .
it is true af cinee culture as well .
we may easily recognize all sorts af english courses in college educatin curriculum but few af cinee culture.
(and these indicate that cinee traditional culture has been ignored in college education ?).
as we all know , traditional culture represents (the accumulated wisdom )of our ancestors downthrough the ages ad is a rich heritage to every chinese.
for college students , successors af modernization construction, mastering af Chinese
cultureis particularly of significance.

How can the train operators possibly justify yet another increase to rail passenger fare-
s? It has become a grimly reliable annual ritual every January the cost of travelling by t-
rain rises imposing a significant extra burden on those who have no option but to use the
rail network to get to work or otherwise. This year is rise an average of there per cent m-
ay be a fraction lower than last year is but it is still well above the official consumer
price index (CPI)(CPI) measure of inflation.

As a result of globalization and convenient interaction among different nations, a variety of native cultures are being or have
been lost. It is true of chinese culture as well. We may easily recognize all sorts of english courses in college education curric-
ulum but few of chinese culture. (AND THESE INDICATE THAT CHINESE TRADITIONAL CULTURE HAS BEEN IGNORED IN COLLEGE EDUCATION?). As
we all know, traditional culture represents (THE ACCUMULATED WISDOM) of our ancestors downthrough the ages and is a rich heritage
to every chinese. For college students, successors of modernization construction, mastering of Chinese cultureis particularly of s-
ignificance.

Source

1816 Online Judge 10.100.0.232