#include <bits/stdc++.h>

#define FILENAME "LCKSTR"
#define ll long long 
#define el cout << '\n'
#define ii pair<ll, ll>
#define fi first 
#define se second 
#define pb push_back
#define YES cout << "YES", el
#define NO cout << "NO", el
#define print_type cout
#define print_el print_type << '\n'
#define DEBUG(...) [](auto && ... x) {int i = 0; ((print_type << (i++ ? " " : "") << x), ...), print_el;} (__VA_ARGS__)
#define bit(mask, i) (((mask) >> (i)) & 1)
#define BIT(n) (1ll << (n))

using namespace std;

const bool is_brute = 0;
const bool multi_test = 0;

const int maxn = 180;
const int maxm = 227;
const int maxk = 26;
const int INF = 1e9;

struct Parents
{
    int x, y;
    char c;

    Parents() {};
    Parents(int x, int y, char c) :
        x(x), y(y), c(c) {};
};
struct Child
{
    int k;
    char x, y;

    Child() {};
    Child(int k, char x, char y) :
        k(k), x(x), y(y) {};
    friend ostream & operator << (ostream &cout, Child p)
    {
        cout << p.k << ' ' << p.x << ' ' << p.y;
        return cout;
    }
};

int n, m, q, dp[maxn + 10][maxn + 10], dpa[maxn + 10][maxn + 10], dpb[maxn + 10][maxn + 10];
Child ca[maxn + 10][maxn + 10][maxk + 10], cb[maxn + 10][maxn + 10][maxk + 10]; 
string a, b, c[maxm + 10];
Parents par[maxn + 10][maxn + 10];
vector<string> ansa, ansb;

void DP(int n, string a, int dp[maxn + 10][maxn + 10], Child p[maxn + 10][maxn + 10][maxk + 10])
{
    for (int i = 1; i <= n; i++)
        dp[i][i] |= BIT(a[i] - 'a');
    for (int l = n; l >= 1; l--)
        for (int r = l + 1; r <= n; r++)
        {
            for (int t = 1; t <= q; t++)
            {
                int x = c[t][0] - 'a';
                int y = c[t][1] - 'a';
                int z = c[t][2] - 'a';
                if (bit(dp[l][r], x))
                    continue;
                for (int k = l; k <= r - 1; k++)
                    if (bit(dp[l][k], y) && bit(dp[k + 1][r], z))
                    {
                        p[l][r][x] = Child(k, y + 'a', z + 'a');
                        dp[l][r] |= BIT(x);
                        break;
                    }
            }
        }
}
void TRACE(int l, int r, char e, Child ch[maxn + 10][maxn + 10][maxk + 10], int n, string &a, vector<string> &ans)
{
    if (l == r)
        return ;
    Child t = ch[l][r][e - 'a'];
    TRACE(l, t.k, t.x, ch, n, a, ans);
    TRACE(t.k + 1, r, t.y, ch, n, a, ans);
    auto getString = [=] (string a)
    {
        string ans = "";
        for (int i = 1; i <= n; i++)
            if (a[i] != '#')
                ans += a[i];
        return ans;
    };
    for (int i = l; i <= r; i++)
        a[i] = '#';
    a[l] = e;
    ans.push_back(getString(a));
}

void solve()
{
    cin >> a;
    cin >> b;
    cin >> q;
    for (int i = 1; i <= q; i++)
        cin >> c[i];
    n = a.size();
    m = b.size();
    a = ' ' + a;
    b = ' ' + b;
    DP(n, a, dpa, ca);
    DP(m, b, dpb, cb);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            for (int x = i; x >= 1; x--)
            {
                if (dpa[x][i] == 0)
                    continue;
                for (int y = j; y >= 1; y--)
                {
                    if ((dpa[x][i] & dpb[y][j]) == 0)
                        continue;
                    if (dp[i][j] > dp[x - 1][y - 1] + i - x + j - y)
                    {
                        int c = __builtin_ctz(dpa[x][i] & dpb[y][j]) + 'a';
                        dp[i][j] = dp[x - 1][y - 1] + i - x + j - y;
                        par[i][j] = Parents(x - 1, y - 1, c);
                    }
                }
            }
        }
    cout << dp[n][m] << ' ';
    int tn = n, tm = m;
    string ans = "";
    ansa.push_back(a);
    ansb.push_back(b);
    while (tn && tm)
    {
        Parents pr = par[tn][tm];
        ans.push_back(pr.c);
        TRACE(pr.x + 1, tn, pr.c, ca, n, a, ansa);
        TRACE(pr.y + 1, tm, pr.c, cb, m, b, ansb);
        tn = pr.x;
        tm = pr.y;
    }
    ansa.pop_back();
    ansb.pop_back();
    reverse(ans.begin(), ans.end());
    reverse(ansa.begin(), ansa.end());
    reverse(ansb.begin(), ansb.end());
    cout << ans, el;
    cout << ansa.size();
    for (string resa : ansa)
    {
        if (resa != ansa.back())
            cout << ' ';
        cout << resa;
    }
    el;
    cout << ansb.size();
    for (string resb : ansb)
    {
        if (resb != ansb.back())
            cout << ' ';
        cout << resb;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(FILENAME".INP", "r"))
    {
        freopen(FILENAME".INP", "r", stdin);
        if (is_brute)
            freopen(FILENAME"_TRAU.OUT", "w", stdout);
        else
            freopen(FILENAME".OUT", "w", stdout);
    }

    int ntest;
    if (multi_test)
        cin >> ntest;
    else
        ntest = 1;
    for (int itest = 1; itest <= ntest; itest++)
    {
        // cout << itest, el;
        solve();
    }
}