თამაში სტრინგით

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

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

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

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

წყარო: COCI, 2010/11, #2


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

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

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი - საწყისი სტრინგის სიგრძე N (2<=N<=100000). მეორე სტრიქონში - საწყისი სიტყვა. სიტყვა შედგება პატარა ლათინური სიმბოლოებისაგან.

გამოსატანი მონაცემები: პირველ სტრიქონში - სიტყვა "DA", თუკი სლავკო გაიმარჯვებს, და სიტყვა "NE", თუკი სლავკო დამარცხდება. მეორე სტრიქონში - სლავკოს მიერ მიღებული სიტყვა.




მაგალითები

შესატანი მონაცემები
2 ne დაკოპირება
გამოსატანი მონაცემები
NE n დაკოპირება
შესატანი მონაცემები
8 cokolada დაკოპირება
გამოსატანი მონაცემები
DA acko დაკოპირება

შენიშვნა

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

სათამაშო სტრინგი  სლავკოს სიტყვა მირკოს სიტყვა
cokolada    
cokolad   a
cokold a a
cokol a ad
okol ac ad
oko ac adl
oo ack adl
o ack adlo
  acko adlo