F :: 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 space₀ ,hole₀ , space₁,hole₁,..., space_(n−1)/2 length of spaces and holes separated by white spaces.

N is odd, 0 < N <12, 0 ≤ S ≤ 100, space_i, hole_i > 0, Σ(space_i) + Σ(hole_j) ≤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

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