CF149E Martian Strings

During the study of the Martians Petya clearly understood that the Martians are absolutely lazy. They like to sleep and don't like to wake up. Imagine a Martian who has exactly $ n $ eyes located in a row and numbered from the left to the right from $ 1 $ to $ n $ . When a Martian sleeps, he puts a patch on each eye (so that the Martian morning doesn't wake him up). The inner side of each patch has an uppercase Latin letter. So, when a Martian wakes up and opens all his eyes he sees a string $ s $ consisting of uppercase Latin letters. The string's length is $ n $ . "Ding dong!" — the alarm goes off. A Martian has already woken up but he hasn't opened any of his eyes. He feels that today is going to be a hard day, so he wants to open his eyes and see something good. The Martian considers only $ m $ Martian words beautiful. Besides, it is hard for him to open all eyes at once so early in the morning. So he opens two non-overlapping segments of consecutive eyes. More formally, the Martian chooses four numbers $ a $ , $ b $ , $ c $ , $ d $ , ( $ 1

N/A

N/A

Let's consider the sample test. There the Martian can get only the second beautiful string if he opens segments of eyes $ a=1,b=2 $ and $ c=4,d=5 $ or of he opens segments of eyes $ a=1,b=2 $ and $ c=6,d=7 $ .