Under construction

Still being built. Things may change

Hide and Seek 4

Time limit2sMemory limit512 MB

Summary
Find the shortest time from N to K using moves -1, +1, and 2X, then output the lexicographically smallest shortest path.
Level

Medium6 of 10

Topics
BFS, Graph, Shortest path
Solved
No attempts yet

Problem

Subin plays hide and seek with his younger sibling. Subin is at point NN and the sibling is at point KK. Subin can walk or teleport. If Subin is at XX and walks, one second later he is at X−1X-1 or X+1X+1. If he teleports, one second later he is at 2X2X. Subin's position is never negative. The sibling never moves.

Given both positions, find the shortest time in which Subin reaches his sibling, together with the positions he passes through.

Several routes can take that shortest time. In that case pick the one whose sequence of visited positions is smallest in lexicographic order. All shortest routes have the same length, so compare two sequences from the front: the one with the smaller number at the first position where they differ comes first.

Input

The first line contains Subin's position NN and the sibling's position KK, separated by a space. (0≤N≤1000000 \le N \le 100000, 0≤K≤1000000 \le K \le 100000)

Output

On the first line, print the shortest time in seconds.

On the second line, print the positions Subin passes through in order, from NN to KK, separated by single spaces. If several routes take the shortest time, print only the sequence that is smallest in lexicographic order.

Examples2

  1. Example 1

    Input
    5 17
    
    Expected output
    4
    5 4 8 16 17
    
  2. Example 2

    Input
    17 5
    
    Expected output
    12
    17 16 15 14 13 12 11 10 9 8 7 6 5