Problem: In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF.

You are given two strings s1, s2 and another string called virus. Your task is to find the longest common subsequence of s1 and s2, such that it doesn't contain virus as a substring.

Input

The input contains three strings in three separate lines: s1, s2 and virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Each string consists only of uppercase English letters.

Output

Output the longest common subsequence of s1 and s2 without virus as a substring. If there are multiple answers, any of them will be accepted. 

If there is no valid common subsequence, output 0.

Examples

Input

AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ


Output

ORZ


Input

AA
A
A


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long int advceil(long long int num, long long int den) {
  return (num % den == 0 ? num / den : num / den + 1);
}
long long int lstbt(long long int val) {
  long long int msk = val & (val - 1);
  return log2(val ^ msk);
}
long long int modmul(long long int a, long long int b) {
  if (a < 1e9 and b < 1e9) return (a * b) % 1000000007;
  a %= 1000000007;
  b %= 1000000007;
  long long int res = 0;
  while (b > 0) {
    if (b & 1) res = (res + a) % 1000000007;
    a = (a * 2) % 1000000007;
    b /= 2;
  }
  return res;
}
long long int modexpo(long long int a, long long int b) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = modmul(res, a);
    a = modmul(a, a);
    b /= 2;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  return a == 0 ? b : gcd(b % a, a);
}
vector<long long int> CALCfactor(long long int n) {
  vector<long long int> factor(n + 2, 0);
  for (long long int i = 4; i <= n; i += 2) factor[i] = 2;
  for (long long int j = 3; j <= n; j += 2) {
    if (factor[j]) continue;
    for (long long int i = 2 * j; i <= n; i += j) factor[i] = j;
  }
  return factor;
}
vector<long long int> CALCprimeNUM(long long int n) {
  vector<long long int> factor = CALCfactor(n);
  vector<long long int> primeNUM;
  primeNUM.reserve(n + 2);
  for (long long int i = 2; i <= n; i++)
    if (!factor[i]) primeNUM.push_back(i);
  return primeNUM;
}
vector<long long int> CALCprimeFACTOR(long long int n) {
  vector<long long int> factor = CALCfactor(n);
  vector<long long int> ans;
  while (factor[n] != 0) {
    ans.push_back(factor[n]);
    n /= factor[n];
  }
  if (n > 1) ans.push_back(n);
  return ans;
}
vector<long long int> unique(vector<long long int> x) {
  sort(x.begin(), x.end());
  set<long long int> s;
  vector<long long int> ans;
  ans.reserve(x.size());
  for (auto elem : x) s.insert(elem);
  for (auto elem : s) ans.push_back(elem);
  return ans;
}
pair<vector<long long int>, vector<long long int> > getFact(long long int n) {
  vector<long long int> fact(n + 1, 1), invfact(n + 1, 1);
  for (long long int i = 1; i <= n; i++)
    fact[i] = (i * (fact[i - 1])) % 1000000007;
  for (long long int i = 1; i <= n; i++)
    invfact[i] = (modexpo(i, 1000000007 - 2) * invfact[i - 1]) % 1000000007;
  return {fact, invfact};
}
void compress(vector<long long int>& arr, long long int n) {
  map<long long int, vector<long long int> > pos;
  for (long long int i = 1; i <= n; i++) pos[arr[i]].push_back(i);
  long long int cnt = 1;
  for (auto itr : pos) {
    for (auto elem : itr.second) arr[elem] = cnt;
    cnt++;
  }
}
bool rcomp(long long int a, long long int b) { return a > b; }
string s, t, z;
long long int dp[111][111][111] = {};
long long int st[111][111][111] = {};
long long int Dfn(long long int i, long long int j, long long int k,
                  long long int len1, long long int len2, long long int len3) {
  if (i > len1 or j > len2)
    return 0;
  else if (dp[i][j][k] != -1)
    return dp[i][j][k];
  else if (s[i] != t[j]) {
    long long int c1 = Dfn(i + 1, j, k, len1, len2, len3);
    long long int c2 = Dfn(i, j + 1, k, len1, len2, len3);
    if (c1 > c2)
      st[i][j][k] = 1;
    else
      st[i][j][k] = 2;
    return dp[i][j][k] = max(c1, c2);
  }
  long long int ret = 0;
  if (z[k] == s[i]) {
    if (k == len3) {
      st[i][j][k] = 3;
      return dp[i][j][k] = Dfn(i + 1, j + 1, k, len1, len2, len3);
    }
    st[i][j][k] = 4;
    ret = Dfn(i + 1, j + 1, k + 1, len1, len2, len3) + 1;
    if (z[k] == z[1]) {
      long long int xval = Dfn(i + 1, j + 1, 2, len1, len2, len3) + 1;
      if (xval < ret) st[i][j][k] = 5;
      ret = min(ret, xval);
    }
  } else {
    st[i][j][k] = 6;
    ret = Dfn(i + 1, j + 1, (s[i] == z[1] ? 2 : 1), len1, len2, len3) + 1;
  }
  long long int fans = Dfn(i + 1, j + 1, k, len1, len2, len3);
  if (fans > ret) st[i][j][k] = 7;
  ret = max(ret, fans);
  return dp[i][j][k] = ret;
}
string getstring(long long int n, long long int m, long long int l) {
  string ans = "";
  long long int i = 1;
  long long int j = 1;
  long long int k = 1;
  while (i <= n and j <= m) {
    if (st[i][j][k] == 1) {
      i++;
    } else if (st[i][j][k] == 2) {
      j++;
    } else if (st[i][j][k] == 3) {
      i++;
      j++;
    } else if (st[i][j][k] == 4) {
      ans.push_back(s[i]);
      i++;
      j++;
      k++;
    } else if (st[i][j][k] == 5) {
      ans.push_back(s[i]);
      i++;
      j++;
      k = 2;
    } else if (st[i][j][k] == 6) {
      ans.push_back(s[i]);
      k = (s[i] == z[1] ? 2 : 1);
      i++;
      j++;
    } else if (st[i][j][k] == 7) {
      i++;
      j++;
    }
  }
  if (ans.size() == 0) ans = "0";
  return ans;
}
void solve() {
  cin >> s >> t >> z;
  memset(dp, -1, sizeof(dp));
  long long int n = s.size(), m = t.size(), l = z.size();
  s = '$' + s;
  t = '$' + t;
  z = '$' + z;
  Dfn(1, 1, 1, n, m, l);
  cout << getstring(n, m, l) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  auto start1 = high_resolution_clock::now();
  solve();
  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop1 - start1);
}