#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 45LL);
const long long MAXLL = 9223372036854775807LL;
const unsigned long long MAXULL = 18446744073709551615LLU;
const long long MOD = 1000000007;
const long double DELTA = 0.000000001L;
inline long long fmm(long long a, long long b, long long m = MOD) {
  long long r = 0;
  a %= m;
  b %= m;
  while (b > 0) {
    if (b & 1) {
      r += a;
      r %= m;
    }
    a += a;
    a %= m;
    b >>= 1;
  }
  return r % m;
}
inline long long fme(long long a, long long b, long long m = MOD) {
  long long r = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) {
      r *= a;
      r %= m;
    }
    a *= a;
    a %= m;
    b >>= 1;
  }
  return r % m;
}
inline long long sfme(long long a, long long b, long long m = MOD) {
  long long r = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) r = fmm(r, a, m);
    a = fmm(a, a, m);
    b >>= 1;
  }
  return r % m;
}
std::vector<long long> primes;
long long primsiz;
std::vector<long long> fact;
std::vector<long long> invfact;
inline void sieve(long long n) {
  long long i, j;
  std::vector<bool> a(n);
  a[0] = true;
  a[1] = true;
  for (i = 2; i * i < n; ++i) {
    if (!a[i]) {
      for (j = i * i; j < n; j += i) {
        a[j] = true;
      }
    }
  }
  for (i = 2; i < n; ++i)
    if (!a[i]) primes.push_back(i);
  primsiz = primes.size();
}
inline void sieve() {
  long long n = 1010000, i, j, k = 0;
  std::vector<bool> a(n);
  primes.resize(79252);
  a[0] = a[1] = true;
  for (i = 2; (j = (i << 1)) < n; ++i) a[j] = true;
  for (i = 3; i * i < n; i += 2) {
    if (!a[i]) {
      k = (i << 1);
      for (j = i * i; j < n; j += k) a[j] = true;
    }
  }
  k = 0;
  for (i = 2; i < n; ++i)
    if (!a[i]) primes[k++] = i;
  primsiz = k;
}
inline bool isPrimeSmall(unsigned long long n) {
  if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3)) return false;
  for (unsigned long long k = 1; 36 * k * k - 12 * k < n; ++k)
    if ((n % (6 * k + 1) == 0) || (n % (6 * k - 1) == 0)) return false;
  return true;
}
bool _p(unsigned long long a, unsigned long long n) {
  unsigned long long t, u, i, p, c = 0;
  u = n / 2, t = 1;
  while (!(u & 1)) {
    u /= 2;
    ++t;
  }
  p = fme(a, u, n);
  for (i = 1; i <= t; ++i) {
    c = (p * p) % n;
    if ((c == 1) && (p != 1) && (p != n - 1)) return 1;
    p = c;
  }
  if (c != 1) return 1;
  return 0;
}
inline bool isPrime(unsigned long long n) {
  if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3)) return 0;
  if (n < 1373653) {
    for (unsigned long long k = 1; (((36 * k * k) - (12 * k)) < n); ++k)
      if ((n % (6 * k + 1) == 0) || (n % (6 * k - 1) == 0)) return 0;
    return 1;
  }
  if (n < 9080191) {
    if (_p(31, n) || _p(73, n)) return 0;
    return 1;
  }
  if (_p(2, n) || _p(7, n) || _p(61, n)) return 0;
  return 1;
}
unsigned long long nCk(long long n, long long k, unsigned long long m = MOD) {
  if (k < 0 || k > n || n < 0) return 0;
  if (k == 0 || k == n) return 1;
  if (fact.size() >= (unsigned long long)n && isPrime(m)) {
    return (((fact[n] * invfact[k]) % m) * invfact[n - k]) % m;
  }
  unsigned long long i = 0, j = 0, a = 1;
  k = ((k) < (n - k) ? (k) : (n - k));
  for (; i < (unsigned long long)k; ++i) {
    a = (a * (n - i)) % m;
    while (j < (unsigned long long)k && (a % (j + 1) == 0)) {
      a = a / (j + 1);
      ++j;
    }
  }
  while (j < (unsigned long long)k) {
    a = a / (j + 1);
    ++j;
  }
  return a % m;
}
void nCkInit(unsigned long long m = MOD) {
  long long i, mx = 1010000;
  fact.resize(mx + 1);
  invfact.resize(mx + 1);
  fact[0] = 1;
  for (i = 1; i <= mx; ++i) {
    fact[i] = (i * fact[i - 1]) % m;
  }
  invfact[mx] = fme(fact[mx], m - 2, m);
  for (i = mx - 1; i >= 0; --i) {
    invfact[i] = (invfact[i + 1] * (i + 1)) % m;
  }
}
template <class T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  long long x1, y1;
  extGCD(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
}
inline void get(long long &x) {
  int n = 0;
  x = 0;
  char c = getchar_unlocked();
  if (c == '-') n = 1;
  while (c < '0' || c > '9') {
    c = getchar_unlocked();
    if (c == '-') n = 1;
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar_unlocked();
  }
  if (n) x = -x;
}
inline int get(char *p) {
  char c = getchar_unlocked();
  int i = 0;
  while (c != '\n' && c != '\0' && c != ' ' && c != '\r' && c != EOF) {
    p[i++] = c;
    c = getchar_unlocked();
  }
  p[i] = '\0';
  return i;
}
inline void put(long long a) {
  int n = (a < 0 ? 1 : 0);
  if (n) a = -a;
  char b[20];
  int i = 0;
  do {
    b[i++] = a % 10 + '0';
    a /= 10;
  } while (a);
  if (n) putchar_unlocked('-');
  i--;
  while (i >= 0) putchar_unlocked(b[i--]);
  putchar_unlocked(' ');
}
inline void putln(long long a) {
  int n = (a < 0 ? 1 : 0);
  if (n) a = -a;
  char b[20];
  int i = 0;
  do {
    b[i++] = a % 10 + '0';
    a /= 10;
  } while (a);
  if (n) putchar_unlocked('-');
  i--;
  while (i >= 0) putchar_unlocked(b[i--]);
  putchar_unlocked('\n');
}
const int K = 3;
std::vector<std::vector<long long> > mul(std::vector<std::vector<long long> > a,
                                         std::vector<std::vector<long long> > b,
                                         unsigned long long m = MOD) {
  std::vector<std::vector<long long> > c(K, std::vector<long long>(K));
  for (long long ii = 0; ii < (K); ++ii)
    for (long long jj = 0; jj < (K); ++jj)
      for (long long kk = 0; kk < (K); ++kk)
        c[ii][jj] = (c[ii][jj] + a[ii][kk] * b[kk][jj]) % m;
  return c;
}
std::vector<std::vector<long long> > fme(std::vector<std::vector<long long> > a,
                                         unsigned long long n,
                                         unsigned long long m = MOD) {
  if (n == 1) return a;
  if (n & 1) return mul(a, fme(a, n - 1, m), m);
  std::vector<std::vector<long long> > x = fme(a, n / 2, m);
  return mul(x, x, m);
}
string str;
long long n, dp[3030][3030];
bool done[3030][3030];
inline bool cons(char c) {
  return ((c != 'a') && (c != 'e') && (c != 'i') && (c != 'o') && (c != 'u'));
}
long long solve(long long pos, long long last) {
  if (pos == n) return 0;
  if (done[pos][last]) return dp[pos][last];
  long long n1 = INF;
  bool ok = true;
  long long x = pos - 1;
  if (pos >= 1 && last >= 1 && pos < n - 1 && cons(str[x]) &&
      cons(str[x + 1]) && cons(str[x + 2]) &&
      (!(str[x] == str[x + 1] && str[x + 1] == str[x + 2])))
    ok = false;
  if (ok) n1 = solve(pos + 1, last + 1);
  long long n2 = 1 + solve(pos + 1, 0);
  dp[pos][last] = ((n1) < (n2) ? (n1) : (n2));
  done[pos][last] = true;
  return dp[pos][last];
}
void trace(long long pos, long long last) {
  if (pos == n) return;
  cout << str[pos];
  long long n1 = INF;
  bool ok = true;
  long long x = pos - 1;
  if (pos >= 1 && last >= 1 && pos < n - 1 && cons(str[x]) &&
      cons(str[x + 1]) && cons(str[x + 2]) &&
      (!(str[x] == str[x + 1] && str[x + 1] == str[x + 2])))
    ok = false;
  if (ok) n1 = solve(pos + 1, last + 1);
  long long n2 = 1 + solve(pos + 1, 0);
  if (n1 <= n2)
    trace(pos + 1, last + 1);
  else {
    cout << ' ';
    trace(pos + 1, 0);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  long long t = 0, m = 0, maxx = 0, minn = 0, curr = 0, k = 0, num = 0, siz = 0,
            n1 = 0, n2 = 0, n3 = 0, n4 = 0, ind = 0;
  long long root = 0, sum = 0, diff = 0, q = 0, choice = 0, d = 0, len = 0,
            begg = 0, endd = 0, pos = 0, cnt = 0, lo = 0, hi = 0, mid = 0,
            ans = 0;
  bool flag = false;
  std::string s1, s2, s3;
  char ch, ch1, ch2, ch3, *ptr;
  double dub = 0;
  cin >> str;
  n = str.size();
  solve(0, 0);
  trace(0, 0);
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Beroffice text editor has a wide range of features that help working with text. One of the features is an automatic search for typos and suggestions of how to fix them.

Beroffice works only with small English letters (i.e. with 26 letters from a to z). Beroffice thinks that a word is typed with a typo if there are three or more consonants in a row in the word. The only exception is that if the block of consonants has all letters the same, then this block (even if its length is greater than three) is not considered a typo. Formally, a word is typed with a typo if there is a block of not less that three consonants in a row, and there are at least two different letters in this block.

For example:

  * the following words have typos: "hellno", "hackcerrs" and "backtothefutttture"; 
  * the following words don't have typos: "helllllooooo", "tobeornottobe" and "oooooo". 



When Beroffice editor finds a word with a typo, it inserts as little as possible number of spaces in this word (dividing it into several words) in such a way that each of the resulting words is typed without any typos.

Implement this feature of Beroffice editor. Consider the following letters as the only vowels: 'a', 'e', 'i', 'o' and 'u'. All the other letters are consonants in this problem.

Input

The only line contains a non-empty word consisting of small English letters. The length of the word is between 1 and 3000 letters.

Output

Print the given word without any changes if there are no typos.

If there is at least one typo in the word, insert the minimum number of spaces into the word so that each of the resulting words doesn't have any typos. If there are multiple solutions, print any of them.

Examples

Input

hellno


Output

hell no 


Input

abacaba


Output

abacaba 


Input

asdfasdf


Output

asd fasd f 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 45LL);
const long long MAXLL = 9223372036854775807LL;
const unsigned long long MAXULL = 18446744073709551615LLU;
const long long MOD = 1000000007;
const long double DELTA = 0.000000001L;
inline long long fmm(long long a, long long b, long long m = MOD) {
  long long r = 0;
  a %= m;
  b %= m;
  while (b > 0) {
    if (b & 1) {
      r += a;
      r %= m;
    }
    a += a;
    a %= m;
    b >>= 1;
  }
  return r % m;
}
inline long long fme(long long a, long long b, long long m = MOD) {
  long long r = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) {
      r *= a;
      r %= m;
    }
    a *= a;
    a %= m;
    b >>= 1;
  }
  return r % m;
}
inline long long sfme(long long a, long long b, long long m = MOD) {
  long long r = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) r = fmm(r, a, m);
    a = fmm(a, a, m);
    b >>= 1;
  }
  return r % m;
}
std::vector<long long> primes;
long long primsiz;
std::vector<long long> fact;
std::vector<long long> invfact;
inline void sieve(long long n) {
  long long i, j;
  std::vector<bool> a(n);
  a[0] = true;
  a[1] = true;
  for (i = 2; i * i < n; ++i) {
    if (!a[i]) {
      for (j = i * i; j < n; j += i) {
        a[j] = true;
      }
    }
  }
  for (i = 2; i < n; ++i)
    if (!a[i]) primes.push_back(i);
  primsiz = primes.size();
}
inline void sieve() {
  long long n = 1010000, i, j, k = 0;
  std::vector<bool> a(n);
  primes.resize(79252);
  a[0] = a[1] = true;
  for (i = 2; (j = (i << 1)) < n; ++i) a[j] = true;
  for (i = 3; i * i < n; i += 2) {
    if (!a[i]) {
      k = (i << 1);
      for (j = i * i; j < n; j += k) a[j] = true;
    }
  }
  k = 0;
  for (i = 2; i < n; ++i)
    if (!a[i]) primes[k++] = i;
  primsiz = k;
}
inline bool isPrimeSmall(unsigned long long n) {
  if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3)) return false;
  for (unsigned long long k = 1; 36 * k * k - 12 * k < n; ++k)
    if ((n % (6 * k + 1) == 0) || (n % (6 * k - 1) == 0)) return false;
  return true;
}
bool _p(unsigned long long a, unsigned long long n) {
  unsigned long long t, u, i, p, c = 0;
  u = n / 2, t = 1;
  while (!(u & 1)) {
    u /= 2;
    ++t;
  }
  p = fme(a, u, n);
  for (i = 1; i <= t; ++i) {
    c = (p * p) % n;
    if ((c == 1) && (p != 1) && (p != n - 1)) return 1;
    p = c;
  }
  if (c != 1) return 1;
  return 0;
}
inline bool isPrime(unsigned long long n) {
  if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3)) return 0;
  if (n < 1373653) {
    for (unsigned long long k = 1; (((36 * k * k) - (12 * k)) < n); ++k)
      if ((n % (6 * k + 1) == 0) || (n % (6 * k - 1) == 0)) return 0;
    return 1;
  }
  if (n < 9080191) {
    if (_p(31, n) || _p(73, n)) return 0;
    return 1;
  }
  if (_p(2, n) || _p(7, n) || _p(61, n)) return 0;
  return 1;
}
unsigned long long nCk(long long n, long long k, unsigned long long m = MOD) {
  if (k < 0 || k > n || n < 0) return 0;
  if (k == 0 || k == n) return 1;
  if (fact.size() >= (unsigned long long)n && isPrime(m)) {
    return (((fact[n] * invfact[k]) % m) * invfact[n - k]) % m;
  }
  unsigned long long i = 0, j = 0, a = 1;
  k = ((k) < (n - k) ? (k) : (n - k));
  for (; i < (unsigned long long)k; ++i) {
    a = (a * (n - i)) % m;
    while (j < (unsigned long long)k && (a % (j + 1) == 0)) {
      a = a / (j + 1);
      ++j;
    }
  }
  while (j < (unsigned long long)k) {
    a = a / (j + 1);
    ++j;
  }
  return a % m;
}
void nCkInit(unsigned long long m = MOD) {
  long long i, mx = 1010000;
  fact.resize(mx + 1);
  invfact.resize(mx + 1);
  fact[0] = 1;
  for (i = 1; i <= mx; ++i) {
    fact[i] = (i * fact[i - 1]) % m;
  }
  invfact[mx] = fme(fact[mx], m - 2, m);
  for (i = mx - 1; i >= 0; --i) {
    invfact[i] = (invfact[i + 1] * (i + 1)) % m;
  }
}
template <class T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  long long x1, y1;
  extGCD(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
}
inline void get(long long &x) {
  int n = 0;
  x = 0;
  char c = getchar_unlocked();
  if (c == '-') n = 1;
  while (c < '0' || c > '9') {
    c = getchar_unlocked();
    if (c == '-') n = 1;
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar_unlocked();
  }
  if (n) x = -x;
}
inline int get(char *p) {
  char c = getchar_unlocked();
  int i = 0;
  while (c != '\n' && c != '\0' && c != ' ' && c != '\r' && c != EOF) {
    p[i++] = c;
    c = getchar_unlocked();
  }
  p[i] = '\0';
  return i;
}
inline void put(long long a) {
  int n = (a < 0 ? 1 : 0);
  if (n) a = -a;
  char b[20];
  int i = 0;
  do {
    b[i++] = a % 10 + '0';
    a /= 10;
  } while (a);
  if (n) putchar_unlocked('-');
  i--;
  while (i >= 0) putchar_unlocked(b[i--]);
  putchar_unlocked(' ');
}
inline void putln(long long a) {
  int n = (a < 0 ? 1 : 0);
  if (n) a = -a;
  char b[20];
  int i = 0;
  do {
    b[i++] = a % 10 + '0';
    a /= 10;
  } while (a);
  if (n) putchar_unlocked('-');
  i--;
  while (i >= 0) putchar_unlocked(b[i--]);
  putchar_unlocked('\n');
}
const int K = 3;
std::vector<std::vector<long long> > mul(std::vector<std::vector<long long> > a,
                                         std::vector<std::vector<long long> > b,
                                         unsigned long long m = MOD) {
  std::vector<std::vector<long long> > c(K, std::vector<long long>(K));
  for (long long ii = 0; ii < (K); ++ii)
    for (long long jj = 0; jj < (K); ++jj)
      for (long long kk = 0; kk < (K); ++kk)
        c[ii][jj] = (c[ii][jj] + a[ii][kk] * b[kk][jj]) % m;
  return c;
}
std::vector<std::vector<long long> > fme(std::vector<std::vector<long long> > a,
                                         unsigned long long n,
                                         unsigned long long m = MOD) {
  if (n == 1) return a;
  if (n & 1) return mul(a, fme(a, n - 1, m), m);
  std::vector<std::vector<long long> > x = fme(a, n / 2, m);
  return mul(x, x, m);
}
string str;
long long n, dp[3030][3030];
bool done[3030][3030];
inline bool cons(char c) {
  return ((c != 'a') && (c != 'e') && (c != 'i') && (c != 'o') && (c != 'u'));
}
long long solve(long long pos, long long last) {
  if (pos == n) return 0;
  if (done[pos][last]) return dp[pos][last];
  long long n1 = INF;
  bool ok = true;
  long long x = pos - 1;
  if (pos >= 1 && last >= 1 && pos < n - 1 && cons(str[x]) &&
      cons(str[x + 1]) && cons(str[x + 2]) &&
      (!(str[x] == str[x + 1] && str[x + 1] == str[x + 2])))
    ok = false;
  if (ok) n1 = solve(pos + 1, last + 1);
  long long n2 = 1 + solve(pos + 1, 0);
  dp[pos][last] = ((n1) < (n2) ? (n1) : (n2));
  done[pos][last] = true;
  return dp[pos][last];
}
void trace(long long pos, long long last) {
  if (pos == n) return;
  cout << str[pos];
  long long n1 = INF;
  bool ok = true;
  long long x = pos - 1;
  if (pos >= 1 && last >= 1 && pos < n - 1 && cons(str[x]) &&
      cons(str[x + 1]) && cons(str[x + 2]) &&
      (!(str[x] == str[x + 1] && str[x + 1] == str[x + 2])))
    ok = false;
  if (ok) n1 = solve(pos + 1, last + 1);
  long long n2 = 1 + solve(pos + 1, 0);
  if (n1 <= n2)
    trace(pos + 1, last + 1);
  else {
    cout << ' ';
    trace(pos + 1, 0);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  long long t = 0, m = 0, maxx = 0, minn = 0, curr = 0, k = 0, num = 0, siz = 0,
            n1 = 0, n2 = 0, n3 = 0, n4 = 0, ind = 0;
  long long root = 0, sum = 0, diff = 0, q = 0, choice = 0, d = 0, len = 0,
            begg = 0, endd = 0, pos = 0, cnt = 0, lo = 0, hi = 0, mid = 0,
            ans = 0;
  bool flag = false;
  std::string s1, s2, s3;
  char ch, ch1, ch2, ch3, *ptr;
  double dub = 0;
  cin >> str;
  n = str.size();
  solve(0, 0);
  trace(0, 0);
  return 0;
}

```