პრეფიქსსუფიქსი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 19, ეტაპი 3


ამ დავალებაში განვიხილავთ ინგლისური ანბანის პატარა ასოებისგან შემდგარ სტრინგებს. მოცემული სტრინგის პრეფიქსი ვუწოდოთ ამ სტრიგნის სათავიდან დაწყებულ ნებისმიერ ქვესტრინგს. მოცემული სტრინგის სუფიქსი ვუწოდოთ ამ სტრინგის ბოლოთი დამთავრებულ ნებისმიერ ქვესტრინგს. ცარიელი სტრინგი არის ნებისმიერი სტრინგის პრეფიქსიც და სუფიქსიც. ორ სტრინგს ვუწოდოთ ციკლურად ექვივალენტური, თუკი შეგვიძლია ერთი სტრინგის რომელიმე კონკრეტული სუფიქსი ამავე სტრინგის სათავეში გადავიტანოთ და შედეგად მეორე სტრინგი მივიღოთ.

მაგალითად, სტრინგები ababba და abbaab ციკლურად ექვივალენტურია, ხოლო სტრინგები ababba და ababab არ არის ციკლურად ექვივალენტური. ასევე, თითოეული სტრინგი ციკლურად ექვივალენტურია საკუთარი თავის.

მოცემულია სტრიგნი t, რომელიც შედგება n ცალი ასოსგან. უნდა მოვძებნოთ მისი s სუფიქსი და p პრეფიქსი, რომლებსაც აქვთ ერთნაირი სიგრძე და აქვთ შემდეგი მახასიათებლები:

     p და s არიან ციკლურად ექვივალენტურები

     არც p და არც s სიგრძით არ აღემატება n/2-ს (ესე იგი t სტრინგში p პრეფიქსი და s სუფიქსი არ თანაიკვეთებიან)

     p და s-ის სიგრძე არის რაც შეიძლება დიდი

შემავალი მონაცემები:

პირველი ხაზი შეიცავს ერთ მთელ რიცხვს n (1≤ n ≤ 1 000 000), რომელიც აღნიშნავს მოცემული t სტრინგის სიგრძეს. მეორე ხაზი შეიცავს t სტრინგს, რომელიც შედგება ინგლისური ანბანის n ცალი პატარა ასოსგან.

ქულის 30%-ს შეადგენს ისეთი ტესტები, სადაც n ≤ 500

ქულის 50%-ს შეადგენს ისეთი ტესტები, სადაც n ≤ 5 000

გამოსატანი მონაცემები:

პროგრამამ უნდა დაბეჭდოს ერთადერთი მთელი რიცხვი, რომელიც აღნიშნავს საძიებელი p პრეფიქსის და s სუფიქსის სიგრძეს.




მაგალითები

შესატანი მონაცემები
15 ababbabababbaab დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება