Hide and Seek 2

Find the minimum time for Subin to reach position K using steps of minus or plus 1 and doubling, plus the number of distinct shortest action sequences.

Medium7BFSGraphDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

Subin plays hide and seek with a younger sibling. Subin is at point NN and the sibling is at point KK. Subin either walks or teleports. When Subin is at position XX and walks, one second later Subin is at X1X-1 or X+1X+1. When Subin teleports, one second later Subin is at 2X2X.

Subin never moves to a position below 00 or above 100,000100{,}000. The sibling stays in place.

Given both positions, write a program that finds the earliest time at which Subin reaches the sibling and the number of ways to reach the sibling in that time. Two ways are different when the sequence of actions differs. At position 11, for example, walking forward and teleporting both lead to position 22, and because the actions differ they count as two separate ways.

Input

The first line contains the position NN of Subin and the position KK of the sibling, separated by a space. Both values are integers with 0N100,0000 \le N \le 100{,}000 and 0K100,0000 \le K \le 100{,}000.

Output

On the first line print the earliest time at which Subin finds the sibling.

On the second line print the number of ways to find the sibling in that time.