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 following 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.

Input

First line of input will contain string O (1 <= length of O <= 5 * 10^5), string which Fernando must compute to stay president. O will consist only of upper-case letters of English alphabet and character '?'. You may assume there is at least one '?' in O.

Second line will contain string U, string with leads for '?'s. i-th letter in U correspond to i-th '?' in O. U will consist only of upper-case letters of English alphabet.

Third line will contain integer K (0 <= K <= 300), number of replacements.

It is guaranteed that there will be not more than 300 '?'s.

Output

In first line of output print integer S, length of the longest palindrome that Fernando could find.

In Second and next lines print string Pi and integer Li, longest palindrome and position where it starts. Each Pi must contain only upper-case letters of English alphabet.

Notes:

  • you must print all longest palindromes, in alphabetically increasing order
  • if two or more palindromes starts at the same position, print only one of them

Example

Input:
UDOVICAB??IVODUANAVOL?MILOVANA
CCA
1

Output:
15
ANAVOLIMILOVANA 16
UDOVICABACIVODU 1

Note that both palindromes have 1 letter which Fernando has changed.

Input:
ABCDE??ABCDE??
ABCD
1

Output:
5
CBABC 6
Input:
ABCDE??ABCDEFG
FG
0

Output:
1
A 1
A 8
B 2
B 9
C 10
C 3
D 4
D 11
E 5
E 12
F 13
F 6
G 7
G 14

Added by:Zvonimir Medic
Date:2010-07-20
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET

hide comments
2022-12-02 05:46:19 [Rampage] Blue.Mary
Test data is weak, O(NK) solution can pass. (N is the length of the string O).
2015-02-05 14:18:14 Scott Shepherd
I don't understand the 1st example. How do you get ANAVOLIMILOVANA from ANAVOL?MILOVANA if "I" isn't one of the letters in U?

Last edit: 2015-02-05 14:18:34
2010-10-20 17:37:25 Zvonimir Medic
It is O with lenght 5*10^5 with one '?' and K=0.

Last edit: 2010-10-20 17:38:35
2010-10-20 15:56:53 Nima Cao
How the hell huge is the 30th input?

Last edit: 2010-10-20 15:58:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.