Giải bài trực tuyến

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.