SP6957 PARTPAL - Partial Palindrome

Fernando is president of country named Palindromia. Every two years there are elections in Palindromia, but not normal elections. Elections in Palindromia are preformed in next steps: - Candidate which at the moment isn't president gives to the current president one string **_O,_** which consist only of upper-case letters of english alphabet and character '?', string _**U,**_ which consist only of upper-case letters of english alphabet, and integer **_K_**. - Current president has one day to compute all longest palindromes in the first string by the folowing rules: - Every '?' in _**O**_ is substituted with one letter from _**U**_, _**i**_-th '?' in **_O_** with **_i_**-th letter in _**U**_. - Every time he search for palindromes, he may substitute some '?' with any letter, at most _**K**_-times. - If he finds palindrome, he goes to step 1. - If he doesn't succeed, the candidate becomes the new president - If there are more candidates, go to step one. Fernando wants to stay president for at least two more years, so he asks you to write program which solves his problem. > > >

First line of input will contain string _**O**_ ( 1

In first line of output print integer _**S**_, lenght of the longest palindrome that Fernando could find. In Second and next lines print string _**P** **$ _{i} $**_ and integer **_L $ _{i} $ ,_** longest palindrome and position where it starts. Each _**P** **$ _{i} $**_ must contain only upper-case letters of english alphabet. **Notes:** - you must print all longest palindromes, in alphabeticaly increasing order - if two or more palindromes starts at the same position, print only one of them