// Longest common subsequence
string LCseq(string& A, string& B)
{
    string str;
    vector<vector<int>> DP(A.size() + 1, vector<int>(B.size() + 1, 0));

    for (int i = 1; i <= A.size(); i++)
    {
        for (int j = 1; j <= B.size(); j++)
        {
            if (A[i - 1] == B[j - 1]) DP[i][j] = DP[i - 1][j - 1] + 1;
            else                      DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
        }
    }

    int i = A.size() - 1, j = B.size() - 1;

    while (i >= 0 && j >= 0)
    {
        if (A[i] == B[j])
        {
            str += A[i];
            i--, j--;
        }

        else
        {
            if (DP[i + 1][j] < DP[i][j + 1]) i--;
            else                            j--;
        }
    }

    reverse(str.begin(), str.end());

    return str;
}