#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (q < m) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
vector<lint> z_algorithm(const string &s) {
  vector<lint> ans(s.size());
  ans[0] = s.size();
  int i = 1, j = 0;
  while (i < (int)s.size()) {
    while (i + j < (int)s.size() && s[j] == s[i + j]) ++j;
    ans[i] = j;
    if (!j) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < (int)s.size() && k + ans[k] < j) ans[i + k] = ans[k], ++k;
    i += k;
    j -= k;
  }
  return ans;
}
template <typename TDATA, typename TRET, typename TQUERY>
struct NonrecursiveSegmentTree {
  int N;
  TRET defaultRET;
  virtual TDATA datamerge(const TDATA &, const TDATA &) = 0;
  virtual TRET data2ret(const TDATA &, const TQUERY &) = 0;
  virtual TRET retmerge(const TRET &, const TRET &) = 0;
  std::vector<TDATA> data;
  inline TDATA &at(int i) { return data[i]; }
  inline void _merge(int i) { at(i) = datamerge(at(i << 1), at((i << 1) + 1)); }
  void initialize(const std::vector<TDATA> &seq, TRET RET_ZERO) {
    N = seq.size();
    defaultRET = RET_ZERO;
    data = seq;
    data.insert(data.end(), seq.begin(), seq.end());
    for (int i = N - 1; i; i--) _merge(i);
  }
  NonrecursiveSegmentTree() = default;
  void update(int pos, const TDATA &x) {
    assert(pos >= 0 and pos < N);
    at(pos + N) = x;
    for (int i = pos + N; i > 1;) i >>= 1, _merge(i);
  }
  TRET get(int l, int r, TQUERY query = NULL) {
    assert(l >= 0 and r <= N);
    TRET retl = defaultRET, retr = defaultRET;
    l += N, r += N;
    while (l < r) {
      if (l & 1) retl = retmerge(retl, data2ret(data[l++], query));
      if (r & 1) retr = retmerge(data2ret(data[--r], query), retr);
      l >>= 1, r >>= 1;
    }
    return retmerge(retl, retr);
  }
  template <typename T1, typename T2, typename T3>
  friend std::ostream &operator<<(std::ostream &os,
                                  NonrecursiveSegmentTree<T1, T2, T3> s) {
    os << "[SegmentTree (len: " << s.N << ')';
    for (int i = 0; i < s.N; i++) os << s.at(i + s.N) << ',';
    os << "]";
    return os;
  }
};
template <typename T>
struct CountAndSumLessThan
    : public NonrecursiveSegmentTree<std::vector<std::pair<T, T>>,
                                     std::pair<int, T>, T> {
  using TDATA = std::vector<std::pair<T, T>>;
  using TRET = std::pair<int, T>;
  using TQUERY = T;
  TDATA datamerge(const TDATA &vl, const TDATA &vr) override {
    TDATA ret = vl;
    ret.insert(ret.end(), vr.begin(), vr.end());
    std::sort(ret.begin(), ret.end());
    if (ret.size()) {
      ret[0].second = ret[0].first;
      for (size_t i = 1; i < ret.size(); i++)
        ret[i].second = ret[i - 1].second + ret[i].first;
    }
    return ret;
  }
  TRET data2ret(const TDATA &vec, const TQUERY &q) override {
    int i = std::lower_bound(vec.begin(), vec.end(), std::make_pair(q, q)) -
            vec.begin();
    if (!i)
      return std::make_pair(0, 0);
    else
      return std::make_pair(i, vec[i - 1].second);
  }
  TRET retmerge(const TRET &l, const TRET &r) override {
    return std::make_pair(l.first + r.first, l.second + r.second);
  }
  using SegTree = NonrecursiveSegmentTree<TDATA, TRET, TQUERY>;
  CountAndSumLessThan(const std::vector<T> &seq)
      : SegTree::NonrecursiveSegmentTree() {
    std::vector<TDATA> init;
    for (auto x : seq) init.emplace_back(TDATA{std::pair<T, T>(x, x)});
    SegTree::initialize(init, TRET(0, 0));
  }
};
int main() {
  int N, M;
  string A, B, S;
  cin >> N >> M >> A >> B >> S;
  vector<lint> z1 = z_algorithm(S + "_" + A);
  z1.erase(z1.begin(), z1.begin() + S.length() + 1);
  reverse(S.begin(), S.end());
  reverse(B.begin(), B.end());
  vector<lint> z2 = z_algorithm(S + "_" + B);
  z2.erase(z2.begin(), z2.begin() + S.length() + 1);
  reverse(z2.begin(), z2.end());
  lint NS = S.length();
  for (auto &x : z1) mmin(x, NS - 1);
  for (auto &x : z2) mmin(x, NS - 1);
  CountAndSumLessThan<lint> st(z2);
  lint ret = 0;
  for (int i = (0), i_end_ = (N); i < i_end_; i++)
    if (z1[i]) {
      int m = z1[i];
      int r = min<int>(i + S.length() - 1, N);
      auto tmp = st.get(i, r, S.length() - m);
      ret += (st.get(i, r, 1e9).second - tmp.second -
              1LL * (r - i - tmp.first) * (S.length() - m - 1));
    }
  cout << ret << endl;
}

### Prompt

Please create a solution in CPP to the following problem:

Vasya had three strings a, b and s, which consist of lowercase English letters. The lengths of strings a and b are equal to n, the length of the string s is equal to m. 

Vasya decided to choose a substring of the string a, then choose a substring of the string b and concatenate them. Formally, he chooses a segment [l_1, r_1] (1 ≤ l_1 ≤ r_1 ≤ n) and a segment [l_2, r_2] (1 ≤ l_2 ≤ r_2 ≤ n), and after concatenation he obtains a string a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} … a_{r_1} b_{l_2} b_{l_2 + 1} … b_{r_2}.

Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:

  * segments [l_1, r_1] and [l_2, r_2] have non-empty intersection, i.e. there exists at least one integer x, such that l_1 ≤ x ≤ r_1 and l_2 ≤ x ≤ r_2; 
  * the string a[l_1, r_1] + b[l_2, r_2] is equal to the string s. 

Input

The first line contains integers n and m (1 ≤ n ≤ 500 000, 2 ≤ m ≤ 2 ⋅ n) — the length of strings a and b and the length of the string s.

The next three lines contain strings a, b and s, respectively. The length of the strings a and b is n, while the length of the string s is m.

All strings consist of lowercase English letters.

Output

Print one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.

Examples

Input

6 5
aabbaa
baaaab
aaaaa


Output

4


Input

5 4
azaza
zazaz
azaz


Output

11


Input

9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz


Output

2

Note

Let's list all the pairs of segments that Vasya could choose in the first example:

  1. [2, 2] and [2, 5]; 
  2. [1, 2] and [2, 4]; 
  3. [5, 5] and [2, 5]; 
  4. [5, 6] and [3, 5]; 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (q < m) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
vector<lint> z_algorithm(const string &s) {
  vector<lint> ans(s.size());
  ans[0] = s.size();
  int i = 1, j = 0;
  while (i < (int)s.size()) {
    while (i + j < (int)s.size() && s[j] == s[i + j]) ++j;
    ans[i] = j;
    if (!j) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < (int)s.size() && k + ans[k] < j) ans[i + k] = ans[k], ++k;
    i += k;
    j -= k;
  }
  return ans;
}
template <typename TDATA, typename TRET, typename TQUERY>
struct NonrecursiveSegmentTree {
  int N;
  TRET defaultRET;
  virtual TDATA datamerge(const TDATA &, const TDATA &) = 0;
  virtual TRET data2ret(const TDATA &, const TQUERY &) = 0;
  virtual TRET retmerge(const TRET &, const TRET &) = 0;
  std::vector<TDATA> data;
  inline TDATA &at(int i) { return data[i]; }
  inline void _merge(int i) { at(i) = datamerge(at(i << 1), at((i << 1) + 1)); }
  void initialize(const std::vector<TDATA> &seq, TRET RET_ZERO) {
    N = seq.size();
    defaultRET = RET_ZERO;
    data = seq;
    data.insert(data.end(), seq.begin(), seq.end());
    for (int i = N - 1; i; i--) _merge(i);
  }
  NonrecursiveSegmentTree() = default;
  void update(int pos, const TDATA &x) {
    assert(pos >= 0 and pos < N);
    at(pos + N) = x;
    for (int i = pos + N; i > 1;) i >>= 1, _merge(i);
  }
  TRET get(int l, int r, TQUERY query = NULL) {
    assert(l >= 0 and r <= N);
    TRET retl = defaultRET, retr = defaultRET;
    l += N, r += N;
    while (l < r) {
      if (l & 1) retl = retmerge(retl, data2ret(data[l++], query));
      if (r & 1) retr = retmerge(data2ret(data[--r], query), retr);
      l >>= 1, r >>= 1;
    }
    return retmerge(retl, retr);
  }
  template <typename T1, typename T2, typename T3>
  friend std::ostream &operator<<(std::ostream &os,
                                  NonrecursiveSegmentTree<T1, T2, T3> s) {
    os << "[SegmentTree (len: " << s.N << ')';
    for (int i = 0; i < s.N; i++) os << s.at(i + s.N) << ',';
    os << "]";
    return os;
  }
};
template <typename T>
struct CountAndSumLessThan
    : public NonrecursiveSegmentTree<std::vector<std::pair<T, T>>,
                                     std::pair<int, T>, T> {
  using TDATA = std::vector<std::pair<T, T>>;
  using TRET = std::pair<int, T>;
  using TQUERY = T;
  TDATA datamerge(const TDATA &vl, const TDATA &vr) override {
    TDATA ret = vl;
    ret.insert(ret.end(), vr.begin(), vr.end());
    std::sort(ret.begin(), ret.end());
    if (ret.size()) {
      ret[0].second = ret[0].first;
      for (size_t i = 1; i < ret.size(); i++)
        ret[i].second = ret[i - 1].second + ret[i].first;
    }
    return ret;
  }
  TRET data2ret(const TDATA &vec, const TQUERY &q) override {
    int i = std::lower_bound(vec.begin(), vec.end(), std::make_pair(q, q)) -
            vec.begin();
    if (!i)
      return std::make_pair(0, 0);
    else
      return std::make_pair(i, vec[i - 1].second);
  }
  TRET retmerge(const TRET &l, const TRET &r) override {
    return std::make_pair(l.first + r.first, l.second + r.second);
  }
  using SegTree = NonrecursiveSegmentTree<TDATA, TRET, TQUERY>;
  CountAndSumLessThan(const std::vector<T> &seq)
      : SegTree::NonrecursiveSegmentTree() {
    std::vector<TDATA> init;
    for (auto x : seq) init.emplace_back(TDATA{std::pair<T, T>(x, x)});
    SegTree::initialize(init, TRET(0, 0));
  }
};
int main() {
  int N, M;
  string A, B, S;
  cin >> N >> M >> A >> B >> S;
  vector<lint> z1 = z_algorithm(S + "_" + A);
  z1.erase(z1.begin(), z1.begin() + S.length() + 1);
  reverse(S.begin(), S.end());
  reverse(B.begin(), B.end());
  vector<lint> z2 = z_algorithm(S + "_" + B);
  z2.erase(z2.begin(), z2.begin() + S.length() + 1);
  reverse(z2.begin(), z2.end());
  lint NS = S.length();
  for (auto &x : z1) mmin(x, NS - 1);
  for (auto &x : z2) mmin(x, NS - 1);
  CountAndSumLessThan<lint> st(z2);
  lint ret = 0;
  for (int i = (0), i_end_ = (N); i < i_end_; i++)
    if (z1[i]) {
      int m = z1[i];
      int r = min<int>(i + S.length() - 1, N);
      auto tmp = st.get(i, r, S.length() - m);
      ret += (st.get(i, r, 1e9).second - tmp.second -
              1LL * (r - i - tmp.first) * (S.length() - m - 1));
    }
  cout << ret << endl;
}

```