There is a puzzle to complete by combining 14 numbers from 1 to 9. Complete by adding another number to the given 13 numbers.

The conditions for completing the puzzle are

* You must have one combination of the same numbers.
* The remaining 12 numbers are 4 combinations of 3 numbers.
The combination of three numbers is either three of the same numbers or three consecutive numbers. However, sequences such as 9 1 2 are not considered consecutive numbers.
* The same number can be used up to 4 times.



Create a program that reads a string of 13 numbers and outputs all the numbers that can complete the puzzle in ascending order. If you cannot complete the puzzle by adding any number from 1 to 9, output 0.

For example, if the given string is 3456666777999

If there is a "2", 234 567 666 77 999
If there is a "3", then 33 456 666 777 999
If there is a "5", then 345 567 666 77 999
If there is an "8", then 345 666 678 77 999

And so on, the puzzle is complete when one of the numbers 2 3 5 8 is added. Note that "6" is fine, but it will be used for the 5th time, so it cannot be used in this example.



Input

The input consists of multiple datasets. For each dataset, 13 numbers are given on one line. The number of datasets does not exceed 50.

Output

For each dataset, the numbers that can complete the puzzle are output on one line in ascending order, separated by blanks.

Example

Input

3649596966777
6358665788577
9118992346175
9643871425498
7755542764533
1133557799246


Output

2 3 5 8
3 4
1 2 3 4 5 6 7 8 9
7 8 9
1 2 3 4 6 7 8
0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys

def f(c):
	if sum(c) in c:
		return 1
	if 5 in c:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			c[i] -= 1
			c[i + 1] -= 1
			c[i + 2] -= 1
			if f(c):
				return 1
			c[i] += 1
			c[i + 1] += 1
			c[i + 2] += 1
n = '123456789'
for e in sys.stdin:
	e = list(e)
	a = [i for i in n if f([(e + [i]).count(j) for j in n])]
	if a:
		print(*a)
	else:
		print(0)


def Solve(c, s):
	if s:
		if max(c) > 4:
			return False
		for i in range(9):
			if c[i] >= 2:
				cc = c[:]
				cc[i] -= 2
				if Solve(cc, False):
					return True
	else:
		check = 0
		for i in range(4):
			check += c.count(3 * i)
		if check == 9:
			return True
		else:
			for i in range(7):
				if c[i] >= 1:
					cc = c[:]
					isneg = False
					for j in range(3):
						cc[i + j] -= 1
						if cc[i + j] < 0:
							isneg = True
							break
					if isneg == False and Solve(cc, False):
						return True
_in = ''
while True:
	ans = []
	try:
		_in = input()
	except EOFError:
		break
	for i in range(9):
		l = (_in + str(i + 1))[::1]
		count = [l.count(str(j + 1)) for j in range(9)]
		if Solve(count, True):
			ans.append(str(i + 1))
	print(0 if len(ans) == 0 else ' '.join(ans))


import sys

def f(c, h=0):
	if 2 in c and sum(c) == 2:
		return 1
	if 5 in c:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c, h + 1):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c, h + 1):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			c[i] -= 1
			c[i + 1] -= 1
			c[i + 2] -= 1
			if f(c, h + 1):
				return 1
			c[i] += 1
			c[i + 1] += 1
			c[i + 2] += 1
n = '123456789'
for e in sys.stdin:
	e = list(e)
	a = [i for i in n if f([(e + [i]).count(j) for j in n])]
	if a:
		print(*a)
	else:
		print(0)


def check(nums):
	for i in range(9):
		if nums[i] > 4:
			return False
	for head in range(9):
		anums = nums[:]
		if anums[head] < 2:
			continue
		anums[head] -= 2
		for i in range(9):
			if anums[i] >= 3:
				anums[i] -= 3
			while anums[i] > 0:
				if i >= 7:
					break
				ok = True
				for j in range(i, i + 3):
					if anums[j] <= 0:
						ok = False
				if not ok:
					break
				for j in range(i, i + 3):
					anums[j] -= 1
		if not any(anums):
			return True
	return False
while True:
	st = ''
	try:
		st = input()
	except:
		break
	nums = [0 for i in range(9)]
	for c in st:
		nums[int(c) - 1] += 1
	anss = []
	for n in range(0, 9):
		nums[n] += 1
		if check(nums[:]):
			anss.append(n + 1)
		nums[n] -= 1
	if len(anss) == 0:
		anss.append(0)
	print(' '.join(map(str, anss)))


def is_hora(lst):
	for i in range(1, 10):
		if lst[i] >= 2:
			if is_4chunk(lst, i):
				return True
	return False

def is_4chunk(lst, atama):
	searchlist = [0] * 10
	for i in range(10):
		searchlist[i] = lst[i]
	searchlist[atama] -= 2
	for i in range(1, 8):
		if searchlist[i] < 0:
			return False
		if searchlist[i] >= 3:
			searchlist[i] -= 3
		if searchlist[i] == 1:
			searchlist[i] -= 1
			searchlist[i + 1] -= 1
			searchlist[i + 2] -= 1
		elif searchlist[i] == 2:
			searchlist[i] -= 2
			searchlist[i + 1] -= 2
			searchlist[i + 2] -= 2
	return (searchlist[8] == 0 or searchlist[8] == 3) and (searchlist[9] == 0 or searchlist[9] == 3)
while True:
	try:
		instr = input()
		pai = [0] * 10
		ans = []
		for i in range(13):
			pai[int(instr[i])] += 1
		for i in range(1, 10):
			if pai[i] == 4:
				continue
			pai[i] += 1
			if is_hora(pai):
				ans.append(i)
			pai[i] -= 1
		if len(ans) != 0:
			print(' '.join(list(map(str, ans))))
		else:
			print(0)
	except EOFError:
		break


def check(nums):
	for i in range(9):
		if nums[i] > 4:
			return False
	for head in range(9):
		anums = nums[:]
		if anums[head] < 2:
			continue
		anums[head] -= 2
		for i in range(9):
			if anums[i] >= 3:
				anums[i] -= 3
			while anums[i] > 0:
				if i >= 7:
					break
				ok = True
				for j in range(i, i + 3):
					if anums[j] <= 0:
						ok = False
				if not ok:
					break
				for j in range(i, i + 3):
					anums[j] -= 1
		if not any(anums):
			return True
	return False
while True:
	st = ''
	try:
		st = input()
	except:
		break
	nums = [0 for i in range(9)]
	for c in st:
		nums[int(c) - 1] += 1
	anss = []
	for n in range(0, 9):
		nums[n] += 1
		if check(nums[:]):
			anss.append(n + 1)
		nums[n] -= 1
	if len(anss) == 0:
		anss.append(0)
	print(' '.join(map(str, anss)))


from collections import deque
try:
	while True:
		a = list(sorted(map(int, input())))
		result = []
		for i in range(1, 10):
			if a.count(i) == 4:
				continue
			_a = sorted(a + [i])
			dq = deque([(_a, 0)])
			while dq:
				(hand, mentu) = dq.popleft()
				if mentu == 5:
					if not hand:
						result.append(i)
						break
					continue
				elif mentu > 5:
					continue
				current = hand[0]
				if hand.count(current) >= 2:
					dq.append((hand[2:], mentu + 1))
				if hand.count(current) >= 3:
					dq.append((hand[3:], mentu + 1))
				if current + 1 in hand and current + 2 in hand:
					_hand = hand[:]
					del _hand[0]
					del _hand[_hand.index(current + 1)]
					del _hand[_hand.index(current + 2)]
					dq.append((_hand, mentu + 1))
		print(' '.join(map(str, result)) if result else 0)
except EOFError:
	exit()


import sys

def g(c, i):
	a = [0] * 9
	for j in e + [i]:
		a[j - 1] += 1
	return a

def f(c):
	if sum(c) in c:
		return 1
	if 5 in c:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			c[i] -= 1
			c[i + 1] -= 1
			c[i + 2] -= 1
			if f(c):
				return 1
			c[i] += 1
			c[i + 1] += 1
			c[i + 2] += 1
for e in sys.stdin:
	e = list(map(int, e.strip()))
	a = [i for i in range(1, 10) if f(g(e, i))]
	if a:
		print(*a)
	else:
		print(0)


def check_set(hand):
	set_list = []
	for i in range(9):
		if hand.count(i + 1) >= 3:
			set_list.append([i + 1, i + 1, i + 1])
		if i + 1 in hand and i + 2 in hand and (i + 3 in hand):
			set_list.append([i + 1, i + 2, i + 3])
	return set_list

def check_winning(hand):
	if len(hand) == 2:
		if hand[0] == hand[1]:
			return True
		else:
			return False
	set_tmp_list = check_set(hand)
	if len(set_tmp_list) == 0:
		return False
	for set_tmp in set_tmp_list:
		hand_tmp = hand[:]
		for i in range(3):
			hand_tmp.remove(set_tmp[i])
		res = check_winning(hand_tmp)
		if res:
			break
		else:
			continue
	return res
while True:
	try:
		inp = list(map(int, list(input())))
		ans = []
		for i in range(9):
			if inp.count(i + 1) >= 4:
				continue
			inp_tmp = inp[:]
			inp_tmp.append(i + 1)
			if check_winning(inp_tmp):
				ans.append(i + 1)
		if len(ans) == 0:
			print(0)
		else:
			print(*ans)
	except:
		break


def check(nums):
	for i in range(9):
		if nums[i] > 4:
			return False
	for head in range(9):
		anums = nums[:]
		if anums[head] < 2:
			continue
		anums[head] -= 2
		for i in range(9):
			if anums[i] >= 3:
				anums[i] -= 3
			while anums[i] > 0:
				if i >= 7:
					break
				ok = True
				for j in range(i, i + 3):
					if anums[j] <= 0:
						ok = True
				if not ok:
					break
				for j in range(i, i + 3):
					anums[j] -= 1
		if not any(anums):
			return True
	return False
while True:
	st = ''
	try:
		st = input()
		if st == '':
			break
	except:
		break
	nums = [0 for i in range(9)]
	for c in st:
		nums[int(c) - 1] += 1
	anss = []
	for n in range(0, 9):
		nums[n] += 1
		if check(nums[:]):
			anss.append(n + 1)
		nums[n] -= 1
	if len(anss) == 0:
		anss.append(0)
	print(' '.join(map(str, anss)))


from collections import Counter
from copy import copy

def _check(pi):
	pi = sorted(pi)
	if len(pi) == 0:
		return True
	retval = False
	try:
		_pi = copy(pi)
		tmp = _pi[0]
		for i in range(3):
			_pi.remove(tmp)
		retval = retval or _check(_pi)
	except:
		pass
	try:
		_pi = copy(pi)
		tmp = _pi[0]
		for i in range(3):
			_pi.remove(tmp + i)
		retval = retval or _check(_pi)
	except:
		pass
	return retval

def check(pi, tsumo):
	pi = pi + [tsumo]
	c = Counter(pi)
	for i in range(1, 10):
		if c[i] > 4:
			return False
	for i in range(1, 10):
		if c[i] >= 2:
			_pi = copy(pi)
			_pi.remove(i)
			_pi.remove(i)
			_pi = sorted(_pi)
			if _check(_pi):
				return True
	return False
while True:
	try:
		s = input()
		s = [int(i) for i in s]
		retval = []
		for i in range(1, 10):
			if check(s, i):
				retval.append(str(i))
		if len(retval) == 0:
			print('0')
		else:
			print(' '.join(retval))
	except EOFError:
		break


import sys

def f(c):
	if sum(c) in c:
		return 1
	if 5 in c or sum(c) == 2:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			c[i] -= 1
			c[i + 1] -= 1
			c[i + 2] -= 1
			if f(c):
				return 1
			c[i] += 1
			c[i + 1] += 1
			c[i + 2] += 1
n = '123456789'
for e in sys.stdin:
	e = list(e)
	a = [i for i in n if f([(e + [i]).count(j) for j in n])]
	if a:
		print(*a)
	else:
		print(0)


from itertools import combinations_with_replacement, combinations

def gen_dict(nums):
	r = {}
	for i in nums:
		if i in r.keys():
			r[i] += 1
		else:
			r[i] = 1
	return r

def has_more_4(num_dict):
	for i in num_dict.values():
		if i > 4:
			return True
	return False

def gen_conseq3(nums):
	r = []
	for i in range(1, 8):
		for j in range(i, i + 3):
			if j not in nums:
				break
		else:
			r.append((i, i + 1, i + 2))
	return r

def gen_same(n, num_dict):
	r = []
	for (i, v) in num_dict.items():
		if v >= n:
			r.append(i)
	return r

def gen_prec(c1s, c2s, c3):
	r = []
	for i in c1s:
		for j in i:
			r.append(j)
	for i in c2s:
		for j in range(3):
			r.append(i)
	for j in range(2):
		r.append(c3)
	return sorted(r)
while True:
	try:
		line = input()
	except EOFError:
		break
	founds = []
	for i in range(1, 10):
		ln = line + str(i)
		nums = sorted(list(map(int, ln[:])))
		num_dict = gen_dict(nums)
		if has_more_4(num_dict):
			continue
		conseq_3s = gen_conseq3(nums)
		same_3s = gen_same(3, num_dict)
		same_2s = gen_same(2, num_dict)
		was_found = False
		for r in range(1, 5):
			if was_found:
				break
			for c1s in combinations_with_replacement(conseq_3s, r):
				if was_found:
					break
				for c2s in combinations(same_3s, 4 - r):
					if was_found:
						break
					for c3 in same_2s:
						pred = gen_prec(c1s, c2s, c3)
						if pred == nums:
							founds.append(str(i))
							was_found = True
	if founds:
		print(' '.join(founds))
	else:
		print(0)


import sys
readlines = sys.stdin.readlines
write = sys.stdout.write
memo = {}

def solve(s):
	d = [0] * 10
	for c in s:
		d[int(c)] += 1

	def dfs(i, d):
		if i == 10:
			return True
		key = tuple(d)
		if s in key:
			return memo[key]
		if d[i] == 0:
			return dfs(i + 1, d)
		if d[i] >= 3:
			d[i] -= 3
			r = dfs(i, d)
			d[i] += 3
			if r:
				memo[key] = True
				return True
		if i + 2 <= 9 and d[i + 1] >= 1 and (d[i + 2] >= 1):
			d[i] -= 1
			d[i + 1] -= 1
			d[i + 2] -= 1
			r = dfs(i, d)
			d[i] += 1
			d[i + 1] += 1
			d[i + 2] += 1
			if r:
				memo[key] = True
				return True
		memo[key] = False
		return False
	ans = []
	for k in range(1, 10):
		if d[k] == 4:
			continue
		d[k] += 1
		for i in range(10):
			if d[i] >= 2:
				d[i] -= 2
				r = dfs(0, d)
				d[i] += 2
				if r:
					ans.append(k)
					break
		d[k] -= 1
	if not ans:
		ans.append(0)
	return ans
for line in readlines():
	res = solve(line.strip())
	write(' '.join(map(str, res)))
	write('\n')


import sys

def p(c, l, b):
	for i in l:
		c[i] += [-1, 1][b]

def f(c):
	if sum(c) in c:
		return 1
	if 5 in c:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			p(c, [i, i + 1, i + 2], 0)
			if f(c):
				return 1
			p(c, [i, i + 1, i + 2], 1)
n = '123456789'
for e in sys.stdin:
	e = list(e)
	a = [i for i in n if f([(e + [i]).count(j) for j in n])]
	if a:
		print(*a)
	else:
		print(0)


def is_solved(nums):
	keys = set(nums)
	for key in keys:
		if nums.count(key) >= 2:
			tmp = nums[:]
			tmp.remove(key)
			tmp.remove(key)
			for key in keys:
				key_count = tmp.count(key)
				if key_count == 4:
					if key + 1 in tmp and key + 2 in tmp:
						for _ in range(4):
							tmp.remove(key)
						tmp.remove(key + 1)
						tmp.remove(key + 2)
				elif key_count == 3:
					for _ in range(3):
						tmp.remove(key)
				elif tmp.count(key + 1) >= key_count and tmp.count(key + 2) >= key_count:
					for _ in range(key_count):
						tmp.remove(key)
						tmp.remove(key + 1)
						tmp.remove(key + 2)
			if tmp == []:
				return True
	return False
while True:
	try:
		puzzle = list(map(int, list(input())))
		ans = []
		for i in range(1, 10):
			if puzzle.count(i) <= 3 and is_solved(puzzle + [i]):
				ans.append(i)
		if ans:
			print(*ans)
		else:
			print(0)
	except EOFError:
		break


import sys

def f(c):
	if sum(c) in c:
		return 1
	if 5 in c:
		return 0
	if 4 in c:
		k = c.index(4)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	if 3 in c:
		k = c.index(3)
		c[k] -= 3
		if f(c):
			return 1
		c[k] += 3
	for i in range(7):
		if c[i] and c[i + 1] and c[i + 2]:
			c[i] -= 1
			c[i + 1] -= 1
			c[i + 2] -= 1
			if f(c):
				return 1
			c[i] += 1
			c[i + 1] += 1
			c[i + 2] += 1
n = '123456789'
for e in sys.stdin:
	c = [list(e).count(j) for j in n]
	a = []
	for i in range(9):
		t = c[:]
		t[i] += 1
		if f(t):
			a += [i + 1]
	if a:
		print(*a)
	else:
		print(0)


def ch(data):
	data.sort()
	if max((data.count(i) for i in range(1, 10))) > 4:
		return False
	if len(data) == 2 and data[0] == data[1]:
		return True
	for i in range(1, 10):
		if data.count(i) >= 3:
			tmp = data[:]
			for _ in range(3):
				tmp.remove(i)
			if ch(tmp):
				return True
	for i in range(7):
		if i + 1 in data and i + 2 in data and (i + 3 in data):
			tmp = data[:]
			for j in range(3):
				tmp.remove(i + j + 1)
			if ch(tmp):
				return True
	return False
while True:
	try:
		data = list(map(int, input()))
		if not len(data):
			break
	except:
		break
	res = []
	for i in range(1, 10):
		if ch(data + [i]):
			res.append(i)
	print(*(res if len(res) else [0]))


import sys
from sys import stdin
input = stdin.readline

def dfs(hand, count):
	if count < 1:
		return True
	for (i, n) in enumerate(hand[1:], start=1):
		if n == 0:
			continue
		if n >= 3:
			c_hand = hand[:]
			c_hand[i] -= 3
			res = dfs(c_hand[:], count - 1)
			if res:
				return True
		if i > 7:
			return False
		if hand[i + 1] >= 1 and hand[i + 2] >= 1:
			c_hand = hand[:]
			c_hand[i] -= 1
			c_hand[i + 1] -= 1
			c_hand[i + 2] -= 1
			res = dfs(c_hand[:], count - 1)
			if res:
				return True
		else:
			return False

def solve(data):
	ans = []
	for tsumo in range(1, 10):
		my_hand = data[:]
		my_hand.append(tsumo)
		remaining = [0] * 10
		for n in my_hand:
			remaining[n] += 1
		if max(remaining) > 4:
			continue
		for (i, atama) in enumerate(remaining[1:], start=1):
			if atama >= 2:
				c_remaining = remaining[:]
				c_remaining[i] -= 2
				res = dfs(c_remaining[:], 4)
				if res:
					ans.append(tsumo)
					break
	return ans

def main(args):
	for line in sys.stdin:
		data = list(map(int, list(line.strip())))
		result = solve(data)
		if len(result) > 0:
			print(*result)
		else:
			print(0)
main(sys.argv[1:])