generate a valid equation using specified operators A twist on a recently asked question, you are given a list of operators and a result and you need to find integers which, when operated on by those operators, generate the result.

Example 1

input

+ + * / 13


possible output

4 8 2 2 4


which means that 4 + 8 + 2 * 2 / 4 = 13.

More specifically, you are given a sequence of N operators (between 1 and 5 inclusive) and an integer result, space separated.  You must print N+1 integers, space separated, in the range 1 through 9, inclusive, that when alternated with the operators produce the result.

The operators are +,-,*,/.  They have the natural precedence order (* and / before + and -, left associative).  Divides must be integral divides, a divide with a fractional result is not allowed.  Operators must appear in the order given.

Most problems will have more than one solution.  Printing any of them, or any subset of them, is fine.  If there is no solution, print NO SOLUTION.

Example 2

input

/ + - - 16


output

9 1 9 1 1


Example 3

input

+ 5


output

1 4
2 3
3 2
4 1


(or any nonempty subset of those lines)

Example 4

input

+ + 30


output

NO SOLUTION


Example 5

input

/ + / 3


output

6 3 5 5


note that 3 2 3 2 is not a solution, as 3/2+3/2=3 is true but the individual divides have fractional values.

Standard code golf, shortest answer wins.
Perl, 129 160 151 chars

sub a{my($s,$t,$o)=splice@_,0,3;@_?map{a("$s $_","$t$o$_",@_)}1..9:
$o-eval$t||$o-eval"use integer;$t"||exit say$s}a"","","",split$",&lt;&gt;;say"NO SOLUTION"


Fun with recursion. The program exits upon finding the first valid tuple.

The eval has to be done twice, in and out of integer-only mode, in order to avoid invalid solutions like that given in example 5 in the description.