```#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

short dp[17005][17005];
vector<pair<char, char> > steps;
int main() {
memset(dp, 0x4f, sizeof dp);

string a, b;
cin >> a >> b;

//dp(i,j) := minimum cost of edits required to make a[0:i] -> b[0:j]
//transitions:
//delete dp(i,j) = 1+dp(i-1,j)
//modify dp(i,j) = 1+dp(i-1,j-1)
//copy dp(i,j) = dp(i-1,j-1) (applies only when a[i] = b[j])

int n = a.size(), m = b.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0) {
if (a[i] != b[j]) dp[i][j] = j+1;
else dp[i][j] = j;
} else if (j == 0) {
if (a[i] != b[j]) dp[i][j] = i+1;
else dp[i][j] = i;
} else {
short c1 = 1+dp[i][j-1];
short c2 = 1+dp[i-1][j];
short c3 = 1+dp[i-1][j-1];
if (a[i] == b[j]) {
dp[i][j] = dp[i-1][j-1];
}
dp[i][j] = min(dp[i][j], min(c1, min(c2,c3)));
}

//cout << dp[i][j] << " ";
}
//cout << endl;
}

int i = n-1, j = m-1;
while (i != 0 && j != 0) {
short c1 = 1+dp[i][j-1], c2 = 1+dp[i-1][j];
short c3 = 1+dp[i-1][j-1], c4 = 20000;
if (a[i] == b[j]) {
c4 = dp[i-1][j-1];
}

short c = min(min(c1,c2), min(c3,c4));
if (c1 == c) {
steps.push_back(make_pair('a', b[j--]));
} else if (c2 == c) {
steps.push_back(make_pair('d', a[i--]));
} else if (c3 == c) {
steps.push_back(make_pair('m', b[j--]));
i--;
} else {
steps.push_back(make_pair('c', a[i--]));
j--;
}
}

if (i == 0) {
if (a[i] == b[j]) {
steps.push_back(make_pair('c', a[i--]));
j--;
} else {
steps.push_back(make_pair('m', b[j--]));
i--;
}
while (j >= 0) steps.push_back(make_pair('a', b[j--]));
}

if (j == 0) {
if (a[i] == b[j]) {
steps.push_back(make_pair('c', a[i--]));
j--;
} else {
steps.push_back(make_pair('m', b[j--]));
i--;
}
while (i >= 0) steps.push_back(make_pair('d', a[i--]));
}

for (auto it = steps.rbegin(); it != steps.rend(); it++) {
cout << it->first << " " << it->second << endl;
}
return 0;
}```