JC15C - Walking Jumper

no tags 

Gunawan really bored today, he sit in his home reading newspaper, but suddenly he found very interesting news. Using modern radar, Satria detect a new chemical stone on top of the nearby mountain, the stone is so rare so it will be very valuable. After Gunawan know that news, he decided to climb that mountain to collect some of that valuable stone. To climb the mountain he need energy, to use energy he need oxygen, he know that when climbing the mountain there are some part of the mountain containing sulphuric gas and it's toxic so decreasing his oxygen, fortunately some other mountain part containing clear breathable air that increasing his oxygen.

Because it's dangerous to climb the mountain without a map containing information about which part of the mountain has breathable air and which part of the mountain containing toxic sulphuric gas, Gunawan went to Tjandra house because Tjandra has that mountain map. Tjandra strongly advise Gunawan to take a deep breath before climbing this mountain to store some oxygen in his body and recommend him to train his jumping power to avoid the toxic gas part (by jumping of course).

After a few days of training, Gunawan observed that his optimal jumping power is proportional to the amount of oxygen inside his body, that means if he has K unit of oxygen inside his body he can jump at most K unit skipping K-1 area that may be containing toxic gas. Not only that, he also observed that after he jump his leg is shaking for a while so he must walk at some distance, this distance also the same as the distance he jumped, for example after he jump with distance K unit, he must walk K unit before he can make another jump. His last observation is that jumping has no effect with his oxygen inside his body, that means no matter how far he jump the amount of oxygen in his body remain the same.

Tjandra tell Gunawan that he must keep his oxygen level positive, if he run out of oxygen (oxygen level in his body < 1) he will die. So Tjandra want to give Gunawan some oxygen supply, Tjandra know that pure oxygen is expensive this day so he must give the minimum possible oxygen that is enough to bring Gunawan to top of that mountain, also he also want the instruction (jump or walk plan) for Gunawan to use that oxygen wisely so he can reach the top of the mountain without running out of oxygen.

The objective is to keep the Gunawan from running out of oxygen, not necessarily to maximize Gunawan's oxygen level at the top of the mountain. Tjandra know that you're very good at this kind of task so he call you using his old phone for your help. Can you help them?

Input

The first line there is an integer N denoting number of area in the map.

On the second line there is a string S of length N which is the content of that map.

Length of string S is equal to N, in other word: |S|=N

The first character of string S describing the area that is nearest to Gunawan's house, and the last character of string S describing the area that is nearest to the top of the mountain.

String S containing two possible characters:

  • '+' means that area is a breathable area that increase Gunawan's oxygen level inside his body by one unit.
  • '-' means that area is a toxic sulphuric gas that decrease Gunawan's oxygen level inside his body by one unit.

Output

On the first line you should output an integer that is the minimum number of oxygen that Gunawan needed at the beginning.

On the second line and after you should output one instruction for each line, there are two types on instruction:

  • If Gunawan need to walk to the next area, print a single character 'W' on that line
  • If Gunawan need to jump K unit (skipping K-1 area), print a single character 'J' and an integer K respectively on that line.

Constraints

1 ≤ N ≤ 1000

Examples

Input 1:
1
+

Output 1:
1
W
W
Input 2:
1
-

Output 2:
2
J 2
Input 3:
5
-----

Output 3:
4
J 4
W
W
Input 4:
5
++---

Output 4:
1
W
W
J 2
W
W
Input 5:
8
-+----+-

Output 5:
3
J 2
W
W
J 2
W
W
W

Sample 5 Explanation

If Gunawan has less than 3 unit of oxygen inside his body at the beginning, he can't make it to the top of mountain, so the minimum number of oxygen needed is 3.

Here is the explanation of move command:

[{3} G-+----+-_]

: Initially Gunawan has 3 unit of oxygen inside his body.

[{3} G-+----+-_] ="J 2"=> [{4} _-G----+-_]

: Gunawan jump 2 step forward to avoid the first toxic area, now he land on the breathable oxygen area increasing his oxygen level to 4.

[{4} _-G----+-_] =="W"==> [{3} _-.G---+-_]

: Because Gunawan's leg is shaking after jump, he is unable to jump so his only choice is to walk to next area decreasing his oxygen level to 3 because that next area is toxic.

[{3} _-.G---+-_] =="W"==> [{2} _-..G--+-_]

: Similar to his previous move, his only choice is to walk to the next area.

[{2} _-..G--+-_] ="J 2"=> [{1} _-...-G+-_]

: After walking two steps his leg become normal again so he can jump to avoid the next toxic area, but unfortunately his remaining oxygen is only 2 so the best jump he can do is to jump 2 step forward landing on toxic area decreasing his oxygen level to 1.

[{1} _-...-G+-_] =="W"==> [{2} _-...-.G-_]

: Fortunately the next area is breathable area, so he walk to this area increasing his oxygen level to 2.

[{1} _-...-.G-_] =="W"==> [{2} _-...-..G_]

: Because the effect of previous jump is not gone, his leg is still shaking and his only choice is to move to the next area decreasing his oxygen value to 1 again.

[{1} .-...-..G_] =="W"==> [{1} .-...-...G]

: Finally to reach the top of the mountain he need to walk once again and completed his mission

Don't worry about how Gunawan go home, because he is at the top of the tall mountain, to going home he simply jump of a cliff with his parachute :)



Added by:Tjandra Satria Gunawan
Date:2016-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem, used in Jolly Challenge #15