# alignment.py: Reads from standard input, the output produced by
# edit_distance.py, i.e., input strings x and y, and the opt matrix. The
# program then recovers an optimal alignment from opt, and writes to
# standard output the edit distance between x and y and the alignment itself.

import stdarray
import stdio

# Read x, y, and opt from standard input.
x = stdio.readString()
y = stdio.readString()
opt = stdarray.readInt2D()

# Compute M and N.
M = len(x)
N = len(y)

# Write edit distance between x and y.
stdio.writef('Edit distance = %1d\n', opt[0][0])

# Recover and write an optimal alignment.
for i in range(0, M + 1):
    for j in range(0, N + 1):
        while i < M and j < N:
            if opt[i][j] == opt[i + 1][j] + 2:
                stdio.writeln(str(x[i]) + ' - 2')
                stdio.writeln('first if statement')
                i += 1
            elif opt[i][j] == opt[i][j + 1] + 2:
                stdio.writeln(str(y[j]) + ' - 2')
                stdio.writeln('first elif statement')
                j += 1
            else:
                if x[i] == y[j]:
                    stdio.writeln(str(x[i]) + ' ' + str(y[j]) + ' 0')
                    stdio.writeln('first else statement')
                    i += 1
                    j += 1
                else:
                    stdio.writeln(str(x[i]) + ' ' + str(y[j]) + ' 1')
                    i += 1
                    j += 1