#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdarg>
#include <cassert>
#include <ctime>
#include <tuple>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi(a, b) for(auto i=a; i<=b; i++)
#define fj(a, b) for(auto j=a; j<=b; j++)
#define fo(a, b) for(auto o=a; o<=b; o++)
#define fy(a) for(auto &y : a)
#define fz(a) for(auto &z : a)
#define fdi(a, b) for(auto i=a; i>=b; i--)
#define fdj(a, b) for(auto j=a; j>=b; j--)
#define fdo(a, b) for(auto o=a; o>=b; o--)
#define clr(x) memset(x, 0, sizeof(x))
#define cpy(x,y) memcpy(x, y, sizeof(y))
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

char __buffer[100000];

#ifdef _DEBUG
#define LOCAL
#endif

#ifdef LOCAL
void err(const char *format, ... ) {
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);

	fprintf(stderr, "\t%s", __buffer);
}
#else
#define err(...) {}
#endif

#ifdef LOCAL
void errln(const char *format, ... ) {
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);

	fprintf(stderr, "\t%s\n", __buffer);
}
#else
#define errln(...) {}
#endif

#ifdef LOCAL
void errln() {
	fprintf(stderr, "\n");
}
#endif

double START_TIME;

void exit() {
#ifdef LOCAL
	cerr << "TIME: " << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;
#endif
	exit(0);
}

template<typename A, typename B>
ostream& operator<<(ostream& os, pair<A, B> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T> v) {
	fi(0, sz(v) - 1) {
		os << v[i] << " ";
	}
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T> t) {
	for (auto z : t) {
		os << z << " ";
	}
	return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, map<T1, T2> t) {
	cerr << endl;
	for (auto z : t) {
		os << "\t" << z.first << " -> " << z.second << endl;
	}
	return os;
}

#ifdef LOCAL
#define dbg(x) {cerr << __LINE__ << "\t" << #x << ": " << (x) << endl;}
#define dbg0(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 0; ABC < n; ABC++) cerr << (x[ABC]) << ' '; cerr << endl;}
#define dbg1(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 1; ABC <= n; ABC++) cerr << (x[ABC]) << ' '; cerr << endl;}
#else
#define dbg(x) {}
#define dbg0(x, n) {}
#define dbg1(x, n) {}
#endif

#ifdef LOCAL
#define ass(x) if (!(x)) { cerr << __LINE__ << "\tassertion failed: " << #x << endl, abort(); }
#else
#define ass(x) assert(x)
#endif

#ifdef LOCAL
#define MAX 101
#else
#define MAX 101000
#endif

char str[MAX];

int n;
int a[MAX];

struct Block {
    int l, r;
    bool operator<(const Block &b) const {
        return l < b.l;
    }
};

ostream& operator<<(ostream& os, Block b) {
    os << "(" << b.l << ", " << b.r << ")";
    return os;
}

vector<Block> b0;

int color[MAX];

bool validate(vector<Block> &v) {
    clr(color);
    fz(v) {
        if (z.l < 1 || z.r > n) return false;
        fi(z.l, z.r) {
            if (color[i]) return false;
            color[i] = 1;
        }
    }
    return true;
}

bool put(int l, int r, int k, vector<Block> &v) {
    if (l > r) return false;
    if (k >= 1 && (r - l) % 2 == 0) {
        for (int i = l; i <= r; i += 2) {
            v.pb({i, i});
        }
        return true;
    }
    if (k >= 2) {
        v.pb({l, l + 1});
        for (int i = l + 3; i <= r; i += 2) {
            v.pb({i, i});
        }
        return true;
    }
    return false;
}

void solve(int k) {
    vector<Block> left, right;
    fz(b0) {
        left.pb({z.l - k, z.r});
        right.pb({z.l, z.r + k});
    }
    errln();
    dbg(k);
    dbg(left);
    dbg(right);
    if (!validate(left)) return;
    if (!validate(right)) return;
    errln("Validated!!!");
    vector<Block> to_add;
    int last = -1;
    fz(left) {
        int x = z.l;
        int L = last;
        int R = x;
        if (R - L > 2) {
            if (!put(L + 2, R - 2, k, to_add)) return;
        }
        last = z.r;
    }

    if (last != n - k) {
        if (!put(last + 2, n - k, k, to_add)) return;
    }

    fz(to_add) {
        left.pb(z);
    }
    sort(all(left));
    vi ans;
    fz(left) {
        ans.pb(z.r - z.l + 1);
    }
    printf("%d\n", sz(ans));
    fz(ans) {
        printf("%d ", z);
    }
    printf("\n");
    exit(0);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	START_TIME = (double)clock();
#endif

    scanf("%s", str);

    n = strlen(str);
    fi(1, n) {
        a[i] = (str[i - 1] == '#');
    }

    dbg1(a, n);

    fi(1, n) {
        if (a[i]) {
            fj(i, n) {
                if (!a[j + 1]) {
                    b0.pb({i, j});
                    i = j;
                    break;
                }
            }
        }
    }

    if (!sz(b0)) {
        printf("0\n");
        return 0;
    }

    dbg(b0);

    fi(0, 3) {
        solve(i);
    }

    printf("-1");

	exit();
	return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Joseph really likes the culture of Japan. Last year he learned Japanese traditional clothes and visual arts and now he is trying to find out the secret of the Japanese game called Nonogram.

In the one-dimensional version of the game, there is a row of n empty cells, some of which are to be filled with a pen. There is a description of a solution called a profile — a sequence of positive integers denoting the lengths of consecutive sets of filled cells. For example, the profile of [4, 3, 1] means that there are sets of four, three, and one filled cell, in that order, with at least one empty cell between successive sets.

<image>

A suitable solution for n = 12 and p = [4, 3, 1]. 

<image>

A wrong solution: the first four filled cells should be consecutive. 

<image>

A wrong solution: there should be at least one empty cell before the last filled cell. 

Joseph found out that for some numbers n and profiles p there are lots of ways to fill the cells to satisfy the profile. Now he is in the process of solving a nonogram consisting of n cells and a profile p. He has already created a mask of p — he has filled all the cells that must be filled in every solution of the nonogram.

<image>

The mask for n = 12 and p = [4, 3, 1]: all the filled cells above are filled in every solution. 

After a break, he lost the source profile p. He only has n and the mask m. Help Joseph find any profile p' with the mask m or say that there is no such profile and Joseph has made a mistake.

Input

The only line contains a string m — the mask of the source profile p. The length of m is n (1 ≤ n ≤ 100 000). The string m consists of symbols # and _ — denoting filled and empty cells respectively.

Output

If there is no profile with the mask m, output the number -1. Otherwise, on the first line, output an integer k — the number of integers in the profile p'. On the second line, output k integers of the profile p'.

Examples

Input


__#_____


Output


2
3 2 


Input


_#


Output


-1


Input


___


Output


0

### Response

```cpp
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdarg>
#include <cassert>
#include <ctime>
#include <tuple>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi(a, b) for(auto i=a; i<=b; i++)
#define fj(a, b) for(auto j=a; j<=b; j++)
#define fo(a, b) for(auto o=a; o<=b; o++)
#define fy(a) for(auto &y : a)
#define fz(a) for(auto &z : a)
#define fdi(a, b) for(auto i=a; i>=b; i--)
#define fdj(a, b) for(auto j=a; j>=b; j--)
#define fdo(a, b) for(auto o=a; o>=b; o--)
#define clr(x) memset(x, 0, sizeof(x))
#define cpy(x,y) memcpy(x, y, sizeof(y))
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

char __buffer[100000];

#ifdef _DEBUG
#define LOCAL
#endif

#ifdef LOCAL
void err(const char *format, ... ) {
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);

	fprintf(stderr, "\t%s", __buffer);
}
#else
#define err(...) {}
#endif

#ifdef LOCAL
void errln(const char *format, ... ) {
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);

	fprintf(stderr, "\t%s\n", __buffer);
}
#else
#define errln(...) {}
#endif

#ifdef LOCAL
void errln() {
	fprintf(stderr, "\n");
}
#endif

double START_TIME;

void exit() {
#ifdef LOCAL
	cerr << "TIME: " << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;
#endif
	exit(0);
}

template<typename A, typename B>
ostream& operator<<(ostream& os, pair<A, B> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T> v) {
	fi(0, sz(v) - 1) {
		os << v[i] << " ";
	}
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T> t) {
	for (auto z : t) {
		os << z << " ";
	}
	return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, map<T1, T2> t) {
	cerr << endl;
	for (auto z : t) {
		os << "\t" << z.first << " -> " << z.second << endl;
	}
	return os;
}

#ifdef LOCAL
#define dbg(x) {cerr << __LINE__ << "\t" << #x << ": " << (x) << endl;}
#define dbg0(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 0; ABC < n; ABC++) cerr << (x[ABC]) << ' '; cerr << endl;}
#define dbg1(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 1; ABC <= n; ABC++) cerr << (x[ABC]) << ' '; cerr << endl;}
#else
#define dbg(x) {}
#define dbg0(x, n) {}
#define dbg1(x, n) {}
#endif

#ifdef LOCAL
#define ass(x) if (!(x)) { cerr << __LINE__ << "\tassertion failed: " << #x << endl, abort(); }
#else
#define ass(x) assert(x)
#endif

#ifdef LOCAL
#define MAX 101
#else
#define MAX 101000
#endif

char str[MAX];

int n;
int a[MAX];

struct Block {
    int l, r;
    bool operator<(const Block &b) const {
        return l < b.l;
    }
};

ostream& operator<<(ostream& os, Block b) {
    os << "(" << b.l << ", " << b.r << ")";
    return os;
}

vector<Block> b0;

int color[MAX];

bool validate(vector<Block> &v) {
    clr(color);
    fz(v) {
        if (z.l < 1 || z.r > n) return false;
        fi(z.l, z.r) {
            if (color[i]) return false;
            color[i] = 1;
        }
    }
    return true;
}

bool put(int l, int r, int k, vector<Block> &v) {
    if (l > r) return false;
    if (k >= 1 && (r - l) % 2 == 0) {
        for (int i = l; i <= r; i += 2) {
            v.pb({i, i});
        }
        return true;
    }
    if (k >= 2) {
        v.pb({l, l + 1});
        for (int i = l + 3; i <= r; i += 2) {
            v.pb({i, i});
        }
        return true;
    }
    return false;
}

void solve(int k) {
    vector<Block> left, right;
    fz(b0) {
        left.pb({z.l - k, z.r});
        right.pb({z.l, z.r + k});
    }
    errln();
    dbg(k);
    dbg(left);
    dbg(right);
    if (!validate(left)) return;
    if (!validate(right)) return;
    errln("Validated!!!");
    vector<Block> to_add;
    int last = -1;
    fz(left) {
        int x = z.l;
        int L = last;
        int R = x;
        if (R - L > 2) {
            if (!put(L + 2, R - 2, k, to_add)) return;
        }
        last = z.r;
    }

    if (last != n - k) {
        if (!put(last + 2, n - k, k, to_add)) return;
    }

    fz(to_add) {
        left.pb(z);
    }
    sort(all(left));
    vi ans;
    fz(left) {
        ans.pb(z.r - z.l + 1);
    }
    printf("%d\n", sz(ans));
    fz(ans) {
        printf("%d ", z);
    }
    printf("\n");
    exit(0);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	START_TIME = (double)clock();
#endif

    scanf("%s", str);

    n = strlen(str);
    fi(1, n) {
        a[i] = (str[i - 1] == '#');
    }

    dbg1(a, n);

    fi(1, n) {
        if (a[i]) {
            fj(i, n) {
                if (!a[j + 1]) {
                    b0.pb({i, j});
                    i = j;
                    break;
                }
            }
        }
    }

    if (!sz(b0)) {
        printf("0\n");
        return 0;
    }

    dbg(b0);

    fi(0, 3) {
        solve(i);
    }

    printf("-1");

	exit();
	return 0;
}

```