1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace test
{
    class Program
    {
        static int[] buildFail(string part)
        {
            var fail = new int[part.Length];
            var ptr = fail[0] = -1;
            for (var i = 1; i < part.Length; i++)
            {
                while (ptr >= 0 && part[i] != part[ptr + 1])
                {
                    ptr = fail[ptr];
                }
                if (part[ptr + 1] == part[i])
                {
                    ptr++;
                }
                fail[i] = ptr;
            }
            return fail;
        }
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX