Golf
Beschrijving
Een normaal partijtje golf bestaat uit het spelen van een bal over 18
holes. Da's een beetje weinig. Daarom is in Ool'In-Wan een golfcourt
aangelegd met enkele duizenden holes. Da's een beetje veel. Daarom
zijn de regels enigszins aangepast. De bal wordt verondersteld over
een gedeelte van de holes gespeeld te worden in plaats van over alle
holes.
Het Probleem
De golfcourt heeft geen 18, maar N holes, genummerd van 1 ...
N, waarbij N <= 10000 (tienduizend). Het gaat erom de bal te
spelen van hole X naar hole Y, maar via een bepaalde route. Als
de bal in hole i is, mag de bal gespeeld worden naar holes j, met
j is element van { i+1, i-1, 2 i, i/2 }, waarbij uiteraard
1 <= j <= N moet gelden.
Hoe korter zo'n route, hoe sneller je klaar bent. Daarom
vragen we jullie om de kortste route uit te rekenen.
De Invoer
De invoer begint met een regel met daarop het aantal runs.
Daarna per run:
- een regel met de hoeveelheid holes van de court.
- een regel met de start- en eindholes X, resp. Y,
1 <= X,Y <= N.
Bij gegeven X en Y is er precies één kortste route.
De Uitvoer
Per run één regel met de kortste route (inclusief X en
Y). Holes in zo'n route worden gescheiden door een spatie.
Voorbeeld
Bij de invoer
2
100
11 30
100
11 32
hoort de uitvoer
11 12 13 14 15 30
11 10 9 8 16 32