402224: GYM100703 G Game of numbers

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Game of numberstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

— It' s a good game, — Princess said pensively. It was clear that she was thinking about something else.

— They like to play various games here in Castles Valley. And they invent ones themselves. Say, my friend Knight played with a princess a game some time ago, — Dragon thought it was a good idea o tell Princess about another game, if, perhaps, previous game was seemed no interesting for her.

Princess A. offered Knight to play a game of numbers. She puts down the number zero on a sheet of paper. Let us call this number a current result.

Further steps of princess A. and Knight are described below. She calls any positive integer and Knight says what she must do with this number: to add it to the current result or subtract it from the current result.

Princess A. performs the action and calculates a new value. This value becomes the new current result.

Princess A. wants that current result to be not less than zero and not greater than k at any time. The game finishes when an action makes the result out of the range or when a sequence of n numbers, which princess A. conceived, exhausts.

Knight managed to learn the sequence of n numbers that princess A. guessed, and now he wants the game to last as long as possible.

Your task is to compute maximum possible number of actions which Knight is able to perform during the game.

Input

The first line contains integers n and k (1 ≤ n ≤ 1000,  1 ≤ k ≤ 1000) — the size of sequence which princess A. conceived and an upper bound for a current result which must not be exceeded.

The second line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ k) — the sequence which princess A. conceived.

Output

In the first line print integer d — maximum possible number of actions, which Knight is able to perform during the game.

Print d symbols "+" and "-" in the second line. Symbol at jth position specifies an action which is applied to jth number in the princess' sequence. If multiple answers exist, choose any of them.

ExamplesInput
2 5
3 2
Output
2
++
Input
5 5
1 2 3 4 5
Output
4
++-+

加入题单

上一题 下一题 算法标签: