სიტყვის შაბლონი

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

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

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

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


 

შაბლონი ეწოდება სუტყვას, რომელიც შედგება ლათინური ანბანისაგან (a..z, A..Z) და სიმბოლოებისაგან  ? და . ყოველი სიმბოლო ? შეიძლება შეცვალოთ ნებისმიერი ერთი სიმბოლოთი, ხოლო  * - სიმბოლოთა ნებისმიერი (შესაძლოა ცარიელი) მიმდევრობით. ყოველი სიტყვის შესახებ, რომელიც შეგვიძლია ამ შაბლონისაგან მივიღოთ, იტყვიან, რომ იგი აკმაყოფილებს ამ შაბლონს.

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

შესატანი მონაცემები: ორ სტრიქონში მოცემულია ორი შაბლონი (თითოში - თითო).  თითოეული შაბლონის სიგრძე არ აღემატება 45 სიმბოლოს

გამოსატანი მონაცემები: ერთადერთ სტრიქონში იმ სტრიქონის მინიმალური სიგრძე, რომელიც ორივე შაბლონს აკმაყოფილებს. თუ ასეთი სტრიქონის მოძებნა შეუძლებელია, გამოიტანეთ "NO SOLUTION".




მაგალითები

შესატანი მონაცემები
A* *B დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება