BLOPER2 - Operators (new ver)

• Thời gian: 1.5s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Given a sequence a1, a2,..., an and a integer S, your task is find a way to insert an operator ‘+’ , ‘-‘, ‘.‘, ‘~‘  to every neighbor pair of A, that the result of the expression after insert equal to S.

Note that :
- a . b = a + 2 * b
- a ~ b = a - 2 * b

Input

First line :  N and S (2 ≤ N ≤ 22, |S| ≤ 5 * 10 ¹⁶ )
Second line : N integers, a1, a2,..., an  (|ai| ≤ 10 ¹⁵ )

Output

If there are way(s) to insert, output any of them, otherwise output “Impossible” (without quotes).

Example

Input :
9 5

1 2 3 4 5 6 7 8 9

Output :
-~~~++++

Input :
3 -1

-2 5 7
Output :
Impossible

Details :
In first test case : 1 - 2 - 2 * 3 - 2 * 4 - 2 * 5 + 6 + 7 + 8 + 9 = 5

You may want to try another version here .

• Người up: kata69