#include <bits/stdc++.h>
using namespace std;
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3& p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3& p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4& p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2& p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2& p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2& p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2& p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first - r.first, l.second - r.second};
}
ostream& operator<<(ostream& os, const vector<long long>& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
ostream& operator<<(ostream& os, const pair<long long, long long>& PAI) {
  os << PAI.first << " : " << PAI.second;
  return os;
}
ostream& operator<<(ostream& os, const pa3& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z;
  return os;
}
ostream& operator<<(ostream& os, const pa4& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z << " : " << PAI.w;
  return os;
}
ostream& operator<<(ostream& os,
                    const vector<pair<long long, long long> >& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[1100000];
long long inv[1100000];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
vector<long long> G1[1000010], G2[1000010];
vector<long long> zalgo(string s) {
  long long n = s.length();
  vector<long long> z(n, 0);
  z[0] = n;
  long long L = 0;
  long long R = 0;
  for (long long i = 1; i < n; i++) {
    if (i > R) {
      L = i;
      R = i;
      while (R < n && s[R - L] == s[R]) R++;
      z[i] = R - L;
      R--;
    } else {
      long long k = i - L;
      if (z[k] < R - i + 1)
        z[i] = z[k];
      else {
        L = i;
        while (R < n && s[R - L] == s[R]) R++;
        z[i] = R - L;
        R--;
      }
    }
  }
  return z;
}
struct segsum {
 private:
 public:
  long long cor = (1 << 19);
  vector<long long> vec;
  void shoki1() { vec.resize(2 * cor + 3, 0); }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--)
      vec[i] = vec[2 * i] + vec[2 * i + 1];
  }
  void clear() {
    for (long long i = 0; i < (long long)vec.size(); i++) vec[i] = 0;
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x] += w;
    x /= 2;
    while (x) {
      vec[x] = vec[2 * x] + vec[2 * x + 1];
      x /= 2;
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x] = w;
    while (x) {
      x /= 2;
      vec[x] = vec[2 * x] + vec[2 * x + 1];
    }
  }
  long long sum(long long a, long long b) {
    long long hi = 0, mi = 0;
    a += cor, b += cor;
    while (a < b) {
      if (a & 1) {
        hi = hi + vec[a];
        a++;
      }
      if (b & 1) {
        b--;
        mi = vec[b] + mi;
      }
      a /= 2, b /= 2;
    }
    return hi + mi;
  }
  long long lower_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (ima + vec[p] >= x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (ima + vec[p] < x) {
        ima += vec[p];
        p++;
      }
    }
  }
  long long upper_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (ima + vec[p] > x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (ima + vec[p] <= x) {
        ima += vec[p];
        p++;
      }
    }
  }
};
void solve() {
  long long n, m;
  cin >> n >> m;
  string a, b, c;
  cin >> a >> b >> c;
  vector<long long> z1 = zalgo(c + "Z" + a);
  reverse(c.begin(), c.end());
  reverse(b.begin(), b.end());
  vector<long long> z2 = zalgo(c + "Z" + b);
  vector<long long> ve1(n), ve2(n);
  for (long long i = m + 1; i <= m + n; i++) {
    ve1[i - m - 1] = z1[i];
    ve2[n - 1 - (i - m - 1)] = z2[i];
  }
  for (long long i = 0; i < n; i++) {
    ve1[i] = min(ve1[i], m - 1);
    ve2[i] = min(ve2[i], m - 1);
  }
  segsum ss1, ss2;
  ss1.shoki1();
  ss2.shoki1();
  ss1.shoki2();
  ss2.shoki2();
  for (long long i = 0; i < n; i++) {
    G1[ve1[i]].push_back(i);
    G2[ve2[i]].push_back(i);
  }
  long long ans = 0;
  for (long long i = 1; i <= m - 1; i++) {
    if (m - i >= 0)
      for (auto v : G2[m - i]) {
        ss1.updadd(v, m - i);
        ss2.updadd(v, 1);
      }
    for (auto v : G1[i]) {
      ans += ss1.sum(v, min(v + m - 1, ss1.cor)) -
             (m - i - 1) * ss2.sum(v, min(v + m - 1, ss1.cor));
    }
  }
  cout << ans << endl;
}
signed main() {
  mod = 1000000007;
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n = 1;
  for (long long i = 0; i < n; i++) solve();
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3& p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3& p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4& p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2& p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2& p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2& p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2& p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first - r.first, l.second - r.second};
}
ostream& operator<<(ostream& os, const vector<long long>& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
ostream& operator<<(ostream& os, const pair<long long, long long>& PAI) {
  os << PAI.first << " : " << PAI.second;
  return os;
}
ostream& operator<<(ostream& os, const pa3& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z;
  return os;
}
ostream& operator<<(ostream& os, const pa4& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z << " : " << PAI.w;
  return os;
}
ostream& operator<<(ostream& os,
                    const vector<pair<long long, long long> >& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[1100000];
long long inv[1100000];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
vector<long long> G1[1000010], G2[1000010];
vector<long long> zalgo(string s) {
  long long n = s.length();
  vector<long long> z(n, 0);
  z[0] = n;
  long long L = 0;
  long long R = 0;
  for (long long i = 1; i < n; i++) {
    if (i > R) {
      L = i;
      R = i;
      while (R < n && s[R - L] == s[R]) R++;
      z[i] = R - L;
      R--;
    } else {
      long long k = i - L;
      if (z[k] < R - i + 1)
        z[i] = z[k];
      else {
        L = i;
        while (R < n && s[R - L] == s[R]) R++;
        z[i] = R - L;
        R--;
      }
    }
  }
  return z;
}
struct segsum {
 private:
 public:
  long long cor = (1 << 19);
  vector<long long> vec;
  void shoki1() { vec.resize(2 * cor + 3, 0); }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--)
      vec[i] = vec[2 * i] + vec[2 * i + 1];
  }
  void clear() {
    for (long long i = 0; i < (long long)vec.size(); i++) vec[i] = 0;
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x] += w;
    x /= 2;
    while (x) {
      vec[x] = vec[2 * x] + vec[2 * x + 1];
      x /= 2;
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x] = w;
    while (x) {
      x /= 2;
      vec[x] = vec[2 * x] + vec[2 * x + 1];
    }
  }
  long long sum(long long a, long long b) {
    long long hi = 0, mi = 0;
    a += cor, b += cor;
    while (a < b) {
      if (a & 1) {
        hi = hi + vec[a];
        a++;
      }
      if (b & 1) {
        b--;
        mi = vec[b] + mi;
      }
      a /= 2, b /= 2;
    }
    return hi + mi;
  }
  long long lower_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (ima + vec[p] >= x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (ima + vec[p] < x) {
        ima += vec[p];
        p++;
      }
    }
  }
  long long upper_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (ima + vec[p] > x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (ima + vec[p] <= x) {
        ima += vec[p];
        p++;
      }
    }
  }
};
void solve() {
  long long n, m;
  cin >> n >> m;
  string a, b, c;
  cin >> a >> b >> c;
  vector<long long> z1 = zalgo(c + "Z" + a);
  reverse(c.begin(), c.end());
  reverse(b.begin(), b.end());
  vector<long long> z2 = zalgo(c + "Z" + b);
  vector<long long> ve1(n), ve2(n);
  for (long long i = m + 1; i <= m + n; i++) {
    ve1[i - m - 1] = z1[i];
    ve2[n - 1 - (i - m - 1)] = z2[i];
  }
  for (long long i = 0; i < n; i++) {
    ve1[i] = min(ve1[i], m - 1);
    ve2[i] = min(ve2[i], m - 1);
  }
  segsum ss1, ss2;
  ss1.shoki1();
  ss2.shoki1();
  ss1.shoki2();
  ss2.shoki2();
  for (long long i = 0; i < n; i++) {
    G1[ve1[i]].push_back(i);
    G2[ve2[i]].push_back(i);
  }
  long long ans = 0;
  for (long long i = 1; i <= m - 1; i++) {
    if (m - i >= 0)
      for (auto v : G2[m - i]) {
        ss1.updadd(v, m - i);
        ss2.updadd(v, 1);
      }
    for (auto v : G1[i]) {
      ans += ss1.sum(v, min(v + m - 1, ss1.cor)) -
             (m - i - 1) * ss2.sum(v, min(v + m - 1, ss1.cor));
    }
  }
  cout << ans << endl;
}
signed main() {
  mod = 1000000007;
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n = 1;
  for (long long i = 0; i < n; i++) solve();
  return 0;
}

```