Construct Ternary Expression to Evaluate 1

You are given a binary string consisting only of characters 0 and 1 with length \(2n+1\) (i.e. an odd length). You must insert exactly \(n\) ternary operators into the string. In other words, you have to insert exactly \(n\) occurrences of ? and exactly \(n\) occurrences of : and, if needed, an arbitrary number of parentheses so that the final expression is a valid ternary expression (using the syntax condition ? true_expr : false_expr) and evaluates to \(1\).

The ternary operator works as follows: given an expression of the form \[ \text{Condition} ? \text{Expression}_1 : \text{Expression}_2, \] if the value of Condition is nonzero (i.e. equal to \(1\) in our case) then the result is Expression1, otherwise the result is Expression2.

The order of the digits in the input must remain unchanged. You may only insert operators and parentheses in between the digits. If it is impossible to obtain an expression that evaluates to \(1\) using exactly \(n\) ternary operators, output impossible.

inputFormat

The input consists of a single line containing a binary string \(S\) of odd length (i.e. \(2n+1\) characters) where each character is either 0 or 1.

outputFormat

If there is a way to insert exactly \(n\) ternary operators (each consisting of a ? and a : in the proper places, with optional parentheses) to form a valid ternary expression that evaluates to \(1\), output one such expression. Otherwise, output impossible.

sample

101

impossible