using System;

public class Program

{

     public static string textformatting(string str) {

            int strl = str.Length;

            if (strl == 0) return "/$"; 

            string rt = "/"; //String Baslangici

            for (int i = 0; i < strl; i++) {

                rt += "#" + str.Substring(i, 1);

            }

            rt += "#$"; //String sonu

            return rt;

        }

​

​

        public static string manacher(string str)

        {

                string fstr = textformatting(str); //Alinan yazi

                int strlength = fstr.Length;

                int[] array = new int[strlength];

​

                int C = 0, R = 0;

              for (int i = 1; i < strlength-1; i++) {//Ilk karakter ve son karakter alinmayacak

                int i_mirror = 2*C-i;

                if (R > i) { array[i]= Math.Min(R - i, array[i_mirror]); }

                else{array[i]=0;}

                while (fstr[i + 1 + array[i]] == fstr[i - 1 - array[i]]) { array[i]++; }

                if (i + array[i] > R) {

                  C = i;

                  R = i + array[i];

                }

              }

​

              int maxLen = 0;

              int centerIndex = 0;

              for (int i = 1; i < strlength-1; i++) {

                if (array[i] > maxLen) {

                  maxLen = array[i];

                  centerIndex = i;

                }

              }

              return str.Substring((centerIndex - 1 - maxLen)/2, maxLen);

        }

    public static void Main()

    {

         string text = "qabbbec";

            string final = manacher(text);

            System.Console.WriteLine(final);

    }

}