Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as 0 and good days as 1. Then, for example, sequences of days 0, 010, 01010 are zebras, while sequences 1, 0110, 0101 are not.

Oleg tells you the story of days he lived in chronological order in form of string consisting of 0 and 1. Now you are interested if it is possible to divide Oleg's life history into several subsequences, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days. 

Input

In the only line of input data there is a non-empty string s consisting of characters 0 and 1, which describes the history of Oleg's life. Its length (denoted as |s|) does not exceed 200 000 characters.

Output

If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer k (1 ≤ k ≤ |s|), the resulting number of subsequences. In the i-th of following k lines first print the integer li (1 ≤ li ≤ |s|), which is the length of the i-th subsequence, and then li indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to n must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print -1.

Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of k.

Examples

Input

0010100


Output

3
3 1 3 4
3 2 5 6
1 7


Input

111


Output

-1

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
s = input()
(arr, zero, one) = ([], [], [])
for i in range(len(s)):
	if s[i] == '0':
		if one:
			idx = one.pop()
			arr[idx].append(i + 1)
			zero.append(idx)
		else:
			zero.append(len(arr))
			arr.append([i + 1])
	else:
		if not zero:
			break
		idx = zero.pop()
		one.append(idx)
		arr[idx].append(i + 1)
if arr and zero and (not one):
	print(len(arr))
	for x in zero:
		print(len(arr[x]), end=' ')
		print(*arr[x])
else:
	print(-1)


import io, os
s = input()
n = len(s)
err = 0
f = []
l = [set(), set()]
cnt = 0
par = 0
for i in range(n):
	if s[i] == '0':
		if len(l[0]) == 0:
			l[1].add(cnt)
			cnt += 1
			f.append([])
			f[-1].append(i + 1)
		else:
			a = l[0].pop()
			l[1].add(a)
			f[a].append(i + 1)
	elif s[i] == '1':
		if len(l[1]) == 0:
			err = 1
			break
		else:
			a = l[1].pop()
			l[0].add(a)
			f[a].append(i + 1)
if err:
	print(-1)
elif len(l[0]) == 0:
	print(len(f))
	for i in f:
		print(len(i), *i)
else:
	print(-1)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1
for _ in range(t):
	l = list(si())
	n = len(l)
	end0 = []
	end1 = []
	cur = 0
	f = 0
	for i in range(n):
		if l[i] == '0':
			if end1 != []:
				x = end1.pop(-1)
				x.append(i + 1)
				end0.append(x)
			else:
				end0.append([i + 1])
		elif end0 == []:
			f = 1
			break
		else:
			x = end0.pop(-1)
			x.append(i + 1)
			end1.append(x)
	if end1 != []:
		f = 1
	if f:
		print(-1)
		continue
	l = []
	for i in end0:
		l.append([len(i)] + i)
	print(len(l))
	for i in l:
		print(*i)


import io
import os
valid = True
s = input()
ze = []
oe = []
for (i, j) in enumerate(s):
	if j == '0':
		if len(oe) != 0:
			x = oe.pop()
			x.append(i + 1)
			ze.append(x)
		else:
			ze.append([i + 1])
	elif len(ze) != 0:
		x = ze.pop()
		x.append(i + 1)
		oe.append(x)
	else:
		print('-1')
		exit()
if len(oe) != 0:
	print(-1)
else:
	print(len(ze))
	for i in ze:
		print(len(i), end=' ')
		print(*i)


zebra = input()
zebra = '0' + zebra
end0lists = []
end1lists = []
lists = []
now = []
cnt = 0
for i in range(1, len(zebra)):
	if zebra[i] == '0':
		if len(end1lists) == 0:
			now = []
			now.append(i)
			lists.append(now)
			end0lists.append(cnt)
			cnt += 1
		else:
			now_id = end1lists.pop()
			now = lists[now_id]
			now.append(i)
			end0lists.append(now_id)
	elif len(end0lists) == 0:
		print(-1)
		exit()
	else:
		now_id = end0lists.pop()
		now = lists[now_id]
		now.append(i)
		end1lists.append(now_id)
if len(end1lists) > 0:
	print(-1)
	exit()
cnt = len(lists)
print(cnt)
print('\n'.join([str(len(list_i)) + ' ' + ' '.join(map(str, list_i)) for list_i in lists]))


from collections import deque
days = input()
goodq = deque()
badq = deque()
ans = []
possible = True
for i in range(len(days)):
	if days[i] == '0':
		if goodq:
			sequence = goodq.pop()
			badq.append(sequence)
			ans[sequence].append(i + 1)
		else:
			badq.append(len(ans))
			ans.append([i + 1])
	elif badq:
		sequence = badq.pop()
		goodq.append(sequence)
		ans[sequence].append(i + 1)
	else:
		possible = False
		break
if not possible or len(goodq) > 0:
	print(-1)
else:
	print(len(ans))
	print('\n'.join(['%d %s' % (len(a), ' '.join(map(str, a))) for a in ans]))


def read_int():
	return int(input())

def read_str():
	return input()

def read_list(t=int):
	return list(map(t, input().split()))

def print_list(x):
	print(len(x), ' '.join(map(str, x)))

def work(num_seqs):
	ans = [[] for i in range(num_seqs)]
	need = {'0': deque([]), '1': deque([])}
	need['0'].extend(range(num_seqs))
	for i in range(len(s)):
		if not len(need[s[i]]):
			return False
		si = need[s[i]].popleft()
		need[chr(ord('0') + ord('1') - ord(s[i]))].append(si)
		ans[si].append(i + 1)
	return ans
from collections import deque
s = read_str()
num_seqs = s.count('0') - s.count('1')
if num_seqs <= 0:
	print(-1)
else:
	ans = work(num_seqs)
	if not work(num_seqs):
		print(-1)
	else:
		print(num_seqs)
		for seq in ans:
			print_list(seq)


a = [int(x) for x in input().strip()]
len0 = len([x for x in a if x == 0])
len1 = len(a) - len0
m = len0 - len1
if m <= 0:
	ans = -1
else:
	(n, pt) = (0, -1)
	ans = []
	for (i, x) in enumerate(a):
		if x == 0:
			if n < m:
				ans.append([i + 1])
				n += 1
			else:
				if pt < 0 or pt >= n:
					ans = -1
					break
				ans[pt].append(i + 1)
				pt -= 1
		else:
			pt += 1
			if pt >= n or pt < 0:
				ans = -1
				break
			ans[pt].append(i + 1)
if ans == -1:
	print(-1)
else:
	print(n)
	out = []
	for line in ans:
		out.append(' '.join([str(x) for x in [len(line)] + line]))
	print('\n'.join(out))


(s, r, f, p) = (input(), [], 0, -1)
try:
	for i in range(len(s)):
		j = i + 1
		if s[i] == '0':
			if p > -1:
				r[p].append(j)
				p -= 1
			else:
				r.append([j])
		else:
			p += 1
			r[p].append(j)
except:
	f = 1
if f or p > -1:
	print(-1)
else:
	print(len(r))
	for x in r:
		print(len(x), *x)


s = input()
c0 = s.count('0')
c1 = s.count('1')
qs = c0 - c1
if qs <= 0:
	print(-1)
	exit()
ans = [[] for i in range(qs)]
n1 = []
n0 = [i for i in range(qs)]
p0 = 0
p1 = 0
for i in range(len(s)):
	l = s[i]
	if l == '0':
		if len(n0) <= p0:
			print(-1)
			exit()
		f = n0[p0]
		p0 += 1
		n1.append(f)
		ans[f].append(i + 1)
	else:
		if len(n1) <= p1:
			print(-1)
			exit()
		f = n1[p1]
		p1 += 1
		n0.append(f)
		ans[f].append(i + 1)
for q in ans:
	if len(q) % 2 != 1:
		print(-1)
		exit()
print(qs)
for q in ans:
	print(' '.join([str(len(q)), ' '.join([str(i) for i in q])]))


(s, a, i, p) = (input(), [], -1, True)
for j in range(len(s)):
	if s[j] == '0':
		if i == -1:
			a.append([j])
		else:
			a[i].append(j)
			i -= 1
	else:
		i += 1
		if i == len(a):
			p = False
			break
		else:
			a[i].append(j)
if not p or i > -1:
	print(-1)
else:
	print(len(a))
	for k in a:
		print(len(k), *map(lambda x: x + 1, k))


def solve(s):
	lists = [[] for _ in range(len(s))]
	cid = 0
	waitSet = set()
	doneSet = set()
	zeros = set()
	for (i, c) in enumerate(s):
		i += 1
		if c == '1':
			if not doneSet and (not zeros):
				print(-1)
				return
			elif doneSet:
				aid = doneSet.pop()
				lists[aid].append(i)
				waitSet.add(aid)
			else:
				(aid, idx) = zeros.pop()
				lists[aid].append(idx)
				lists[aid].append(i)
				waitSet.add(aid)
		elif waitSet:
			aid = waitSet.pop()
			lists[aid].append(i)
			doneSet.add(aid)
		else:
			zeros.add((cid, i))
			cid += 1
	if waitSet:
		print(-1)
		return
	k = len(doneSet) + len(zeros)
	print(k)
	for i in doneSet:
		zebra = lists[i]
		print('%d %s' % (len(zebra), ' '.join(map(str, zebra))))
	for (aid, idx) in zeros:
		print('1 %d' % idx)
s = input()
solve(s)


life_log = input()
result = list()

def possible():
	ones = 0
	zeros = 0
	for k in life_log:
		if k == '0':
			if ones > 0:
				ones -= 1
			zeros += 1
		else:
			zeros -= 1
			ones += 1
		if zeros < 0:
			return False
	if ones > 0:
		return False
	return True

def compute():
	ones = 0
	for k in range(len(life_log)):
		char = life_log[k]
		if char == '0':
			if ones == 0:
				result.append([k + 1])
			else:
				result[ones - 1].append(k + 1)
				ones -= 1
		else:
			result[ones].append(k + 1)
			ones += 1
if possible():
	compute()
	print(len(result))
	print('\n'.join([str(len(sub)) + ' ' + ' '.join(map(str, sub)) for sub in result]))
else:
	print(-1)


def read_int():
	return int(input())

def read_str():
	return input()

def read_list(t=int):
	return list(map(t, input().split()))

def print_list(x):
	print(len(x), ' '.join(map(str, x)))

def work(seqs):
	ans = [[] for i in range(seqs)]
	si = 0
	need0 = deque(range(seqs))
	need1 = deque([])
	for i in range(len(s)):
		if s[i] == '0':
			if not len(need0):
				return False
			si = need0.popleft()
			need1.append(si)
		if s[i] == '1':
			if not len(need1):
				return False
			si = need1.popleft()
			need0.append(si)
		ans[si].append(i + 1)
	return ans
from collections import deque
s = read_str()
seqs = s.count('0') - s.count('1')
if seqs <= 0:
	print(-1)
	exit(0)
ans = work(seqs)
if not work(seqs):
	print(-1)
else:
	print(seqs)
	for seq in ans:
		print_list(seq)


days = input()
goodq = set()
badq = set()
ans = []
possible = True
for i in range(len(days)):
	if days[i] == '0':
		if goodq:
			sequence = goodq.pop()
			badq.add(sequence)
			ans[sequence].append(i + 1)
		else:
			badq.add(len(ans))
			ans.append([i + 1])
	elif badq:
		sequence = badq.pop()
		goodq.add(sequence)
		ans[sequence].append(i + 1)
	else:
		possible = False
		break
if not possible or len(goodq) > 0:
	print(-1)
else:
	print(len(ans))
	print('\n'.join(['%d %s' % (len(a), ' '.join(map(str, a))) for a in ans]))


import sys
import bisect
t = 1
mod = 10 ** 9 + 7
for _ in range(t):
	s = input()
	d = {}
	for i in range(len(s) + 1):
		d[i] = []
	z = []
	nz = []
	l3 = []
	upto = 1
	for i in range(len(s)):
		ch = 1
		if s[i] == '0':
			if len(nz) > 0:
				index = nz.pop()
				d[index].append(i + 1)
				z.append(index)
			else:
				z.append(upto)
				d[upto].append(i + 1)
				upto += 1
		elif len(z) > 0:
			index = z.pop()
			d[index].append(i + 1)
			nz.append(index)
		else:
			ch = 0
			break
		if ch == 0:
			break
	if ch == 0 or len(nz) > 0:
		print(-1)
	else:
		print(upto - 1)
		for i in range(1, upto):
			print(len(d[i]), *d[i])


s = input()
(res, p) = ([], -1)
for i in range(len(s)):
	j = i + 1
	if s[i] == '0':
		if p > -1:
			res[p].append(j)
			p -= 1
		else:
			res.append([j])
	else:
		p += 1
		if p >= len(res):
			print(-1)
			exit()
		res[p].append(j)
if p != -1:
	print(-1)
	exit()
print(len(res))
for x in res:
	print(len(x), *x)


s = input()
seqs = []
zero = set()
one = set()
impossible = False
for i in range(len(s)):
	day = i + 1
	if s[i] == '0':
		if len(one) > 0:
			ends_with_one = one.pop()
			seqs[ends_with_one].append(day)
			zero.add(ends_with_one)
		else:
			seqs.append([day])
			ends_with_zero = len(seqs) - 1
			zero.add(ends_with_zero)
	elif len(zero) > 0:
		ends_with_zero = zero.pop()
		seqs[ends_with_zero].append(day)
		one.add(ends_with_zero)
	else:
		impossible = True
		break
	if impossible:
		break
if len(one) > 0:
	impossible = True
if impossible:
	print(-1)
else:
	print(len(seqs))
	for se in seqs:
		print(len(se), ' '.join([str(e) for e in se]))


from sys import stdin
n0 = set()
n1 = set()
res = []
i = 1
c = '-'
while c != '':
	c = stdin.read(1)
	if c == '0':
		if len(n1) > 0:
			ind = n1.pop()
		else:
			ind = len(res)
			res.append([])
		res[ind].append(i)
		n0.add(ind)
	elif c == '1':
		if len(n0) < 1:
			res = -1
			break
		ind = n0.pop()
		n1.add(ind)
		res[ind].append(i)
	i += 1
if res == -1 or len(n1) > 0:
	print(-1)
else:
	print(len(res))
	for ar in res:
		print(len(ar), end=' ')
		for el in ar:
			print(el, end=' ')
		print()


s = input()
black = set()
white = set()
subs = []
possible = True
for i in range(len(s)):
	if s[i] == '1':
		if not black:
			possible = False
			break
		k = black.pop()
		white.add(k)
		subs[k].append(i + 1)
	elif white:
		k = white.pop()
		black.add(k)
		subs[k].append(i + 1)
	else:
		black.add(len(subs))
		subs.append([i + 1])
if possible and (not white):
	print(len(subs))
	print('\n'.join([str(len(sub)) + ' ' + ' '.join(map(str, sub)) for sub in subs]))
else:
	print(-1)


import configparser
import math
import sys
input = sys.stdin.readline

def main():
	s = input().strip()
	one = []
	zero = []
	adj = [[] for i in range(len(s))]
	for i in range(len(s)):
		if s[i] == '0':
			if len(one) == 0:
				zero.append(i)
			else:
				adj[one.pop()].append(i)
				zero.append(i)
		elif len(zero) == 0:
			print(-1)
			return
		else:
			adj[zero.pop()].append(i)
			one.append(i)
	if len(one) != 0:
		print(-1)
		return
	groups = []
	vis = [False for i in range(len(s))]
	for i in range(len(vis)):
		if not vis[i]:
			cur_node = i
			cur_g = [cur_node]
			vis[cur_node] = True
			while True:
				if len(adj[cur_node]) == 0:
					break
				else:
					cur_node = adj[cur_node][0]
					cur_g.append(cur_node)
					vis[cur_node] = True
			groups.append(cur_g)
	print(len(groups))
	for i in groups:
		print(len(i), end=' ')
		for j in i:
			print(j + 1, end=' ')
		print()
main()


import io
import os
input = lambda : io.BytesIO(os.read(0, os.fstat(0).st_size)).readline().strip()
valid = True
s = input()
ze = []
oe = []
for (i, j) in enumerate(s):
	if j == 48:
		if len(oe) != 0:
			x = oe.pop()
			x.append(i + 1)
			ze.append(x)
		else:
			ze.append([i + 1])
	elif len(ze) != 0:
		x = ze.pop()
		x.append(i + 1)
		oe.append(x)
	else:
		print('-1')
		exit()
if len(oe) != 0:
	print(-1)
else:
	print(len(ze))
	for i in ze:
		print(len(i), end=' ')
		print(*i)


temp = [int(x) for x in list(input())]
b = []
cnt = -1
skip = False
for i in range(len(temp)):
	if temp[i] == 0:
		if cnt == -1:
			b.append([i + 1])
		else:
			b[cnt] += [i + 1]
			cnt -= 1
	else:
		cnt += 1
		if cnt == len(b):
			skip = True
			break
		else:
			b[cnt].append(i + 1)
if skip or cnt != -1:
	print(-1)
else:
	print(len(b))
	for i in b:
		print(str(len(i)) + ' ' + ' '.join([str(x) for x in i]))


from sys import stdin, stdout

def main():
	life = stdin.readline()
	zeroes = []
	ones = []
	zebras = []
	fail = False
	for i in range(1, len(life) + 1):
		day = life[i - 1]
		if day == '0':
			if len(ones) != 0:
				one = ones.pop()
				zebras[one].append(i)
				zeroes.append(one)
			else:
				zebras.append([i])
				zeroes.append(len(zebras) - 1)
		elif day == '1':
			if len(zeroes) != 0:
				zero = zeroes.pop()
				zebras[zero].append(i)
				ones.append(zero)
			else:
				fail = True
				break
	if len(ones) != 0:
		fail = True
	if fail:
		stdout.write(str('-1\n'))
	else:
		stdout.write(str(len(zebras)) + '\n')
		for i in zebras:
			stdout.write(str(len(i)) + ' ' + ' '.join([str(k) for k in i]) + '\n')
main()