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