309056: CF1618B. Missing Bigram

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Missing Bigram

题意翻译

有一个长为 $n$ ,仅包含 `a` 和 `b` 的字符串。 我们把该字符串所有长度为 $2$ 的子串称作一个 bigram。Polycarp 从第 $1$ 个字符开始,到第 $n-1$ 个字符结束,每次把以当前字符开头的 bigram 打在一个文件中。比如,`abbaaba` 对应的文件内容是 `ab bb ba aa ab ba`。 然而,Polycarp 一不小心删掉了一个 bigram。请根据剩下的 $n-2$ 个 bigram 推算出原来的字符串。如果有多种答案,输出任意一种即可。

题目描述

Polycarp has come up with a new game to play with you. He calls it "A missing bigram". A bigram of a word is a sequence of two adjacent letters in it. For example, word "abbaaba" contains bigrams "ab", "bb", "ba", "aa", "ab" and "ba". The game goes as follows. First, Polycarp comes up with a word, consisting only of lowercase letters 'a' and 'b'. Then, he writes down all its bigrams on a whiteboard in the same order as they appear in the word. After that, he wipes one of them off the whiteboard. Finally, Polycarp invites you to guess what the word that he has come up with was. Your goal is to find any word such that it's possible to write down all its bigrams and remove one of them, so that the resulting sequence of bigrams is the same as the one Polycarp ended up with. The tests are generated in such a way that the answer exists. If there are multiple answers, you can print any of them.

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 3 \le n \le 100 $ ) — the length of the word Polycarp has come up with. The second line of each testcase contains $ n-2 $ bigrams of that word, separated by a single space. Each bigram consists of two letters, each of them is either 'a' or 'b'. Additional constraint on the input: there exists at least one string such that it is possible to write down all its bigrams, except one, so that the resulting sequence is the same as the sequence in the input. In other words, the answer exists.

输出格式


For each testcase print a word, consisting of $ n $ letters, each of them should be either 'a' or 'b'. It should be possible to write down all its bigrams and remove one of them, so that the resulting sequence of bigrams is the same as the one Polycarp ended up with. The tests are generated in such a way that the answer exists. If there are multiple answers, you can print any of them.

输入输出样例

输入样例 #1

4
7
ab bb ba aa ba
7
ab ba aa ab ba
3
aa
5
bb ab bb

输出样例 #1

abbaaba
abaabaa
baa
bbabb

说明

The first two testcases from the example are produced from the word "abbaaba". As listed in the statement, it contains bigrams "ab", "bb", "ba", "aa", "ab" and "ba". In the first testcase, the $ 5 $ -th bigram is removed. In the second testcase, the $ 2 $ -nd bigram is removed. However, that sequence could also have been produced from the word "abaabaa". It contains bigrams "ab", "ba", "aa", "ab", "ba" and "aa". The missing bigram is the $ 6 $ -th one. In the third testcase, all of "baa", "aab" and "aaa" are valid answers.

Input

题意翻译

有一个长为 $n$ ,仅包含 `a` 和 `b` 的字符串。 我们把该字符串所有长度为 $2$ 的子串称作一个 bigram。Polycarp 从第 $1$ 个字符开始,到第 $n-1$ 个字符结束,每次把以当前字符开头的 bigram 打在一个文件中。比如,`abbaaba` 对应的文件内容是 `ab bb ba aa ab ba`。 然而,Polycarp 一不小心删掉了一个 bigram。请根据剩下的 $n-2$ 个 bigram 推算出原来的字符串。如果有多种答案,输出任意一种即可。

加入题单

上一题 下一题 算法标签: