gistfile1.txt

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAX 4000010
using namespace std;

int Z, n, R[MAX], id, max_value;
char text[MAX], tmp[MAX];

void load_data_and_cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
      load_data_and_cleaning();
      calculate();
      print_data();
    }
  return 0;
}

void load_data_and_cleaning() {
  id = max_value = 0;
  scanf("%s", &tmp);

  n = 2*strlen(tmp)+1;

  for (int i = 0; i < n; i++) {
    text[i] = '#';
    text[i+1] = tmp[i/2];
    i++;
  }
  
  text[strlen(text)-1] = '#';
  n = strlen(text) - 1;
}

void manacher() {
  int l;
  int t = 1;
  R[1] = 0;
  for (int i = 2; i <= n; i++) {
      if (t+R[t] >= i) l = min(t+R[t]-i, R[2*t-i]);
      else l = 0;
  
      while (i+l < n && i-l > 0 && text[i+l] == text[i-l]) l++;
      R[i] = l;
  
      if (l >= max_value && i == l) {
            max_value = l; id = i;
          }
      else if (l >= max_value && i + l == n) {
            max_value = l; id = i;
          }   
  
      if (i+R[i] > t+R[t]) t = i;
    }
}

void puh(char a) {
    if (a != '#') printf("%c", a);
}

void calculate() {
  manacher();

  if (n == 2) {
      for (int i = 0; i < n; i++) puh(text[i]);
  }
  else if (id >= n/2) {
      for (int i = 0; i < n; i++) puh(text[i]);
      for (int i = id - max_value; i > 0; i--) puh(text[i]);
    }
  else {
      for (int i = n; i > 0; i--) if(text[i] != '#') puh(text[i]);
      for (int i = id + max_value + 1; i <= n; i++) puh(text[i]);
    }
}

void print_data() {
  printf("\n");
}