Algorithms and Data Structures

Number Transformation

Emil has a number x and he wants to transform it into another number y. To achieve this, he can perform the following operations:
  1. Emil can increase the current number x by 1 (x = x + 1) and pay 1 unit of money for it.
  1. Emil can decrease the current number x by 1 (if x is larger than 0) (x = x - 1) and pay 1 unit of money for it.
  1. Emil can multiply x by any positive integer k (x = k ⋅ x) and pay 2k units of money for it.
  1. Emil can divide x by any positive integer k if x is divisible by k (x = x / k) and pay 2k units of money for it.
Write a program to determine the smallest amount of money Emil needs to transform x into y. You should also print the operations in the respective order they need to be performed. Note that if there are multiple ways to achieve the minimum cost, you can output any of them. Additionally, you do not need to minimize the number of operations.

Input

The input consists of two integers x and y (1 ≤ x, y ≤ 10 000), representing Emil's initial number and the desired number.

Output

The first line of the output should contain two space-separated integers, m and n, representing the number of operations and the minimum amount of money Emil needs to transform x into y.
On the next m lines, output the index of operation, in the respective order they need to be performed. If the operation is Multiply or Divide ( or ), print the index of the operation followed by a space and the number .

Examples

Input
Output
3 7
4 4 1 1 1 1
10 21
2 5 3 2 1
21 10
2 5 2 4 2
10 32
3 8 3 3 1 1

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue