#include <iostream>
using namespace std;

int main() {
	// your code goes here
	return 0;
}

using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;


string lcs(const string& x, const string& y) {
    if (x.length() == 0 || y.length() == 0) return "";
    int n = x.length(), m = y.length();

    auto dp = vvs (n + 1, vs (m + 1, ""));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (x[i] == y[j]) dp[i + 1][j + 1] = dp[i][j] + string(1, x[i]);
            else dp[i+1][j+1] = dp[i][j+1].size() > dp[i+1][j].size() ? dp[i][j+1] : dp[i+1][j];
        }
    }

    return dp[n][m];
}