Hide and Seek 2

Time limit2sMemory limit512 MB

Summary

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.

Level: Medium7 of 10
Topics: BFS, Graph, Dynamic programming
Solved: No attempts yet

Problem

Subin plays hide and seek with a younger sibling. Subin is at point $N$ and the sibling is at point $K$ . Subin either walks or teleports. When Subin is at position $X$ and walks, one second later Subin is at $X-1$ or $X+1$ . When Subin teleports, one second later Subin is at $2X$ .

Subin never moves to a position below $0$ or above $100{,}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 $1$ , for example, walking forward and teleporting both lead to position $2$ , and because the actions differ they count as two separate ways.

Input

The first line contains the position $N$ of Subin and the position $K$ of the sibling, separated by a space. Both values are integers with $0 \le N \le 100{,}000$ and $0 \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.

Examples3

Example 1
Input
```
5 17
```
Expected output
```
4
2
```
Example 2
Input
```
1 2
```
Expected output
```
1
2
```
Example 3
Input
```
0 0
```
Expected output
```
0
1
```