#70036. 【例题 3-6】环状序列 Circular Sequence

UVA1584

Some DNA sequences exist in circular forms as in the following figure, which shows a circular sequence “CGAGTCAGCT”, that is, the last symbol “T” in “CGAGTCAGCT” is connected to the first symbol “C”. We always read a circular sequence in the clockwise direction.

Since it is not easy to store a circular sequence in a computer as it is, we decided to store it as a linear sequence. However, there can be many linear sequences that are obtained from a circular sequence by cutting any place of the circular sequence. Hence, we also decided to store the linear sequence that is lexicographically smallest among all linear sequences that can be obtained from a circular sequence.

Your task is to find the lexicographically smallest sequence from a given circular sequence. For the example in the figure, the lexicographically smallest sequence is “AGCTCGAGTC”. If there are two or more linear sequences that are lexicographically smallest, you are to find any one of them (in fact, they are the same).

一些 序列以环状形式存在，如下图所示，其中显示了环状序列 ，即 中的最后一个符号 与第一个符号 相连。我们总是按顺时针方向读取圆形序列。

由于在计算机中存储循环序列并不容易，我们决定将其存储为线性序列。然而，通过切割圆形序列的任何位置，可以从圆形序列中获得许多线性序列。因此，我们还决定存储从循环序列中可以获得的所有线性序列中字典最小的线性序列。

你的任务是从给定的循环序列中找到字典最小的序列。对于图中的示例，词典中最小的序列是 。如果有两个或多个线性序列在字典上最小，你要找到其中任何一个（事实上，它们是相同的）。

The input consists of T test cases. The number of test cases T is given on the first line of the input file. Each test case takes one line containing a circular sequence that is written as an arbitrary linear sequence. Since the circular sequences are DNA sequences, only four symbols, ‘A’, ‘C’, ‘G’ and ‘T’, are allowed. Each sequence has length at least 2 and at most 100.

输入由 个测试用例组成。测试用例的数量 在输入文件的第一行给出。每个测试用例都有一行，其中包含一个循环序列，该序列被写成任意线性序列。由于循环序列是 序列，因此只允许使用四个符号，“”、“”、“”和“”。每个序列的长度至少为 ，最多为 。

Print exactly one line for each test case. The line is to contain the lexicographically smallest sequence for the test case.

为每个测试用例打印一行。该行包含测试用例的字典最小序列。

样例 1

输出样例 1

2
CGAGTCAGCT
CTCC

输出样例 1

AGCTCGAGTC
CCCT