Remote Bike

Time Limit: 10 Seconds    Memory Limit: 32768 KB
Special Judge

Shamir’s dad bought a Remote Bike for him. Shamir can make this Bike do 4 tasks: accelerate, decelerate, jump, and idle. Shamir was playing with his bike the other day and all of a sudden, he saw bunch of  holes. He was wondering how hard can it be to make the bike go over the holes without falling into any of them?

Shamir is a great programmer but he’s busy playing with his bike, can you write a program to help him?

 

The Program:

Write a program which tells bike what to do!

- Bike is moving on X axis and starts it’s movements from x=0.

- Bike’s remote accepts 4 instructions: “Acc”, “Dec”, “Idl” and “Jmp”.

“Acc”: increases speed of bike 1m/s   and bike moves s meters. (s = bike’s speed)

“Dec”: decreases speed of bike 1m/s and bike moves s meters.

“Idl”: does nothing; bike keeps moving s meters.

“Jmp”: makes bike jump; and bike moves s meters.

- Bike already has a speed; we call it  (initial Speed).

- Bike can’t go backwards; speed can’t be negative. (s≥0)

- You have to set all instructions, before bike starts moving; you tell bike what to do before it starts moving, once it starts moving, it will run your instructions one by one.

- If bike reads an instruction, it will run it immediately. What does it mean? It means for example if bike is at position x=5 and s=4 and instruction is “Acc”, speed will increase to 5 then bike will move, it will result in: x=10 and s=5.

- Shamir’s bike is brand new, he doesn’t like to Jump a lot. He wants to go over all holes with minimum number of jumps.

- Do not fall into a hole.

- Each hole has different length.

- There are some spaces before, between and after holes.

- Shamir wants to stop his bike(s=0) after going over the last hole in the field. (bike has to stop in space after the last hole).

 

Sample:

Bike has S0=3:

Instructions are: “Idl”, “Jmp”, “Dec”, “Dec”, “Dec” 

 

 


 

Input

Input starts with an integer T on a single line indicating number of test cases. Each test-case is described as follows:

Test case contains two lines. First line contains two integers N, S indicating number of spaces + holes and initial speed. Other line contains N integers space0 ,hole0 , space1,hole1,..., space(n−1)/2 length of spaces and holes separated by white spaces.

N is odd, 0 < N <12, 0 ≤ S ≤ 100, spacei, holei > 0, Σ(spacei) + Σ(holej) ≤10000

 

Output

For each test-case:

Step one:

Print in a line: “START

Step two:

Print instructions to lead the bike.

If there’s more than one solution, each will do.

Step three:

Print in a line: “END

If there are no solutions, print in a single line “Sorry Shamir!” instead of three steps.

 

Sample Input

3
3 3
4 2 5
3 0
7 2 4
3 0
7 2 3

Sample Output

START
Idl
Jmp
Dec
Dec
Dec
END
START
Acc
Acc
Acc
Jmp
Dec
Dec
Dec
END
Sorry Shamir!
Submit

Source: 12th Iran Nationwide Internet Contest III