Sequence Alignment
-------- ---------

Sequence alignment algorithms are at the heart of DNA
sequencing.  Here we give a simplified sequence
alignment problem.

You are given two sequences, each a string of capital
letters.  To align them, you insert dashes (-) into the
strings to make them the same length, and then put them
next to each other and compute a score for the align-
ment.  You seek an alignment with the best score.

The dashes can be put before or after a string, or
between letters.  Several dashes may be put between
two letters.

After inserting dashes the positions in each string are
numbered 1, 2, 3, ..., and the two modified strings have
identical lengths.  Then the score is computed from
three parameters, A, B, and C, as follows

  + A	For every position in which the two strings
        have matching letters.

  - B	For every position in which one string has
  	`-' and the other a letter and the `-' is
	not before all letters in its string or after
	all letters in its string.

  - C	For every position in which the two strings
  	have different letters.

Alignments that have a position where both aligned
strings have `-' are NOT permitted.

For example, given the strings

    ABCXDEA
    ACYDEDE

and the alignment

    ABCXDEA--
    A-CYDE-DE

the score of the alignment is +A -B +A -C +A +A -B or
4A-2B-C.


Input 
-----

For each of several test cases, a line containing just
the test case name, followed by a line containing

    N A B C

followed by N pairs of lines, each pair containing two
strings.  Strings are at most 1,000 characters long and
contain only upper case letters.  A, B, and C are float-
ing point numbers.

  0 <= A,B,C <= 1
  sum over all string pairs in an input file of (I+J)^2
      <= 100,000,000
  where I and J are the lengths of the two strings

The test case name line is at most 80 characters long.
Input ends with an end of file.


Output
------

For each test case, first an exact copy of the test case
name line, then for each string pair two lines contain-
ing the alignment that has the best score.  The input
will be such that this alignment is always unique.


Sample Input
------ -----

** SAMPLE 1 **
1 1.0 0.7 0.9
ABCXDEA
ACYDEDE
** SAMPLE 2 **
1 1.0 0.7 0.9
ABCDEFGHIJK
ABCXEFHIJKIJK
** SAMPLE 3 **
2 0.5 1.0 0.5
CGATGTATCGAATGTATACG
CGATGTATGGATTGATACG
CGTGAGAGTACGCTATGCTCGA
CTTGGAGTACCTATGTCGA


Sample Output
------ ------

** SAMPLE 1 **
ABCXDEA--
A-CYDE-DE
** SAMPLE 2 **
ABCDEFGHIJK---
ABCXEF-HIJKIJK
** SAMPLE 3 **
CGATGTATCGAATGTATACG
CGATGTATGGATTG-ATACG
CGTGAGAGTACGCTATGCTCGA
CTTG-GAGTAC-CTATG-TCGA


File:	   alignment.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sat Oct  6 03:01:08 EDT 2018

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.