Weird Dissimilarity

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

The issue of this problem is to find out how far two strings over alphabet Z are, with respect to one weird definition of dissimilarity. For any two characters c₁ and c₂ from Z consider dissimilarity d(c₁, c₂) of c₁ from c₂ - non-negative integer number. If we take two strings a and b of equal length l, distance from a to b is

You are given two strings s and t. Consider all possible pairs of strings a and b of equal length over Z, such that s is a subsequence of a and t is a subsequence of b (string w of length n is a subsequence of a string v of length m if there exist 1 <= i₁ < i₂ < ... < i_n <= m such that w[j] = v[i_j] for all 1 <= j <= n). Choose among them a' and b' such that dist(a', b') is minimal possible. Dissimilarity of s from t is defined as D(s, t) = dist(a', b').

Your task is to find the dissimilarity of s from t and to provide a' and b' such that D(s, t) = dist(a', b').

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line of the input file contains Z - several different characters that form the alphabet for the strings we consider (1 <= |Z| <= 200, all characters have ASCII code greater than space). Next two lines contain s and t respectively. Length of each of the given strings does not exceed 2000. Next |Z| lines contain |Z| non-negative integer numbers each, j-th number of i-th line contains dissimilarity of i-th character from j-th.

Output

On the first line of the output file print D(s, t). On the second and third lines of the output file print a' and b', such that D(s, t) = dist(a', b'), s is a subsequence of a' and t is a subsequence of b'. Length of each of a' and b' must not exceed 4000.

Sample Input

1

ab
ab
ba
2 1
4 1

Sample Output

4
aba
bba

Submit

Source: Andrew Stankevich's Contest #3