CF135E Weak Subsequence

Little Petya very much likes strings. Recently he has received a voucher to purchase a string as a gift from his mother. The string can be bought in the local shop. One can consider that the shop has all sorts of strings over the alphabet of fixed size. The size of the alphabet is equal to $ k $ . However, the voucher has a string type limitation: specifically, the voucher can be used to purchase string $ s $ if the length of string's longest substring that is also its weak subsequence (see the definition given below) equals $ w $ . String $ a $ with the length of $ n $ is considered the weak subsequence of the string $ s $ with the length of $ m $ , if there exists such a set of indexes $ 1

N/A

N/A

In the first sample Petya can buy the following strings: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.