Update appNew update is available. Click here to update.

Split Concatenated String

Posted: 7 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given ‘N’ strings. You could concatenate these strings into one where for each string you cloud reverse it or not. Among all the possible strings you need to find a lexicographically largest string by cutting and making one point in any part of the string which will make the looped string into a regular one starting from the breakpoint character.

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ..., x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ..., xr = yr and xr + 1 > yr + 1.

Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2T’ lines represent the ‘T’ test cases. 

The first line of each test case contains one integers ‘N’ denoting the number of strings.

The second line contains N space-separated strings.
Output Format :
For each test case print the lexicographically biggest string.
Constraints :
1 <= T <= 50
1 <= N <= 100
1 <= length of string(si) <= 100  for all  1 <= i < = n 

Time Limit: 1sec