#include<stdio.h>
#include<string.h>
#define MAX_LEN 1002
 
int partition(char string[], int low, int high) {
char pivot = string[high];
int i = low - 1;
int j;
for (j = low; j <= high - 1; j++) {
if (string[j] >= pivot) {
i++;
char temp = string[j];
string[j] = string[i];
string[i] = temp;
}
}
char temp = string[i + 1];
string[i + 1] = string[high];
string[high] = temp;
return (i + 1);
}
void quickSort(char string[], int low, int high) {
if (low < high) {
int point = partition(string, low, high);
quickSort(string, low, point - 1);
quickSort(string, point + 1, high);
}
}
int main() {
int testCase;
scanf("%d", &testCase);
int t;
for (t = 0; t < testCase; t++) {
char string[MAX_LEN];
scanf("%s", string);
quickSort(string, 0, strlen(string) - 1);
//Printing Result...
char result[strlen(string)];
int mid = strlen(string) / 2;
int low = mid - 1;
int high = mid + 1;
int pointer = 0;
result[mid] = string[pointer++];
while (high < strlen(string) && low >= 0) {
result[high++] = string[pointer++];
result[low--] = string[pointer++];
}
int i;
for (i = 0; i < strlen(string); i++) {
printf("%c", result[i]);
}
printf("\n");
}
return 0;
}

Problem Description

Trico is trying to impress a girl. But the girl is not showing any sign of interest to him. So his best friend suggested him to gift one Grovyle string to her. Grovlye string is a odd length string consisting of only lowercase alphabets arranged in such a way that a number X associated with it is smallest as possible.

X is calculated as : First take absolute distance of each character’s position from the center of the string i.e., (string length/2) and then multiply the distance with its ASCII value. Similarly find all the values and add them.

Example : Given string : aaa

Here only one unique permutation is possible : aaa

distances are : for first a, d1 = 1, second a, d2 =0, third a, d3 = 1;

so X = 1 X 97 + 0 X 97 + 1 X 97 = 194;

So given a string of odd length consisting of only lowercase alphabets, find one permutation of the given string such that X is smallest as possible. And if there are many such strings then print the lexicographically smallest one.

Input: First line contains T, the number of test cases that follow. Next T lines, each contains one odd length string consisting of only lowercase alphabets.

Output: For each test case, print the desired result in separate lines.

Constraints:
1 <= T <= 1000
0 <= String Length <= 1001

• Test Case 1

  Input (stdin)

  2
  aaa
  abc
  

  Expected Output

  aaa
  acb

• Test Case 2

  Input (stdin)

  3
  aaa
  abc
  ccb
  

  Expected Output

  aaa
  acb
  bcc