시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 128 MB 61 5 3 30.000%

문제

문자열이 주어졌을 때, 이 문자열을 다른 문자열로 바꾸는 편집 스크립트를 작성하려고 한다. 편집 스크립트에서 사용할 수 있는 명령은 아래와 같이 총 네 가지가 있다.

추가 ('a'): 한 글자를 출력한다. 이 명령은 입력 문자열을 건드리지 않는다.

삭제 ('d'): 한 글자를 삭제한다. 이 명령은 입력 문자열에서 한 글자를 삭제하고, 아무것도 출력하지 않는다.

수정 ('m'): 한 글자를 수정한다. 즉, 입력 문자열에서 한 글자를 삭제하고, 바꾼 글자를 출력한다.

복사 ('c'): 한 글자를 복사한다. 입력에서 한 글자를 삭제하고, 삭제한 그 글자를 출력한다.

가장 짧은 편집 스크립트란, 추가, 삭제, 수정을 가장 적게 사용한 스크립트이다.

두 문자열이 주어졌을 때, 첫 번째 문자열을 두 번째 문자열로 바꾸는 가장 짧은 편집 스크립트를 작성하는 프로그램을 작성하시오. 

입력

두 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 영문알파벳과 숫자로만 이루어져 있으며, 길이는 1보다 크거나 같고, 17000보다 작거나 같다.

출력

가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자나 삭제할 글자)

가장 짧은 편집 스크립트가 여러가지인 경우에는 아무거나 출력하면 된다.

예제 입력

abcde
xabzdey

예제 출력

a x
c a
c b
m z
c d
c e
a y

힌트