Festive Sugar Modulus Calculations#11056

Festive Sugar Modulus Calculations

1 second

128 megabytes

Hard

As you already know, Ralph dreams of becoming the best in some game, winning a gold medal in it and becoming a real hero! This time, Ralph decided to show everyone that he is not only strong and brave, but also very smart, that's why he went to the game "Holiday Sugar Modulus Calculations".

The goal of the game is simple: the player is given two numbers. Using a calculator, you need to find $x$ xor $y$ . The expression $x$ xor $y$ denotes the application of bitwise exclusive or (bitwise addition modulo $2$ ) to the numbers $x$ and $y$ . This operation is available in all modern programming languages, for example, in C ++ and Java it is denoted ˆ, in Pascal - xor.

The calculator stores in memory all the numbers that were received by the player during the game, and also knows how to add numbers, subtract them, multiply or integer divide a number by $2$ . The memory of the calculator is, of course, limited: it cannot store more than $1000$ integers. In addition, all numbers stored in the calculator must be between $0$ and $2^{31} - 1$ 2^{31} - 1 inclusive. Initially, the calculator's memory contains the numbers $x$ and $y$ . The player can only use the numbers stored in the calculator's memory.

Ralph is a very smart guy, but Vanellope is in trouble again, he hurries to help her. Therefore, it is up to you to become the best in the game "Holiday Sugar Modulus Calculations"!

Input

One line contains two integers $x$ and $y$ ( $1 \leq x, y \leq 1 0^{9}$ 1 \le x, y \le 10^9) - the numbers that initially lie in calculator memory.

Output

In the first line print the number of actions $n$ ( $1 \leq n \leq 1000$ 1 \le n \le 1000) the player needs to perform to win the game.

In each of the following $n$ lines print first the type of action you want to perform on the current step:

$1$ - add two numbers
$2$ - subtract the second from the first number
$3$ - multiply number by $2$
$4$ - integer divide the number by $2$ .

If the type of operation is $1$ or $2$ , then output two numbers - the numbers of iterations at which each of the used numbers was obtained. If the operation type is $3$ or $4$ , print a single number - the number of the iteration at which the used number was obtained.

For example, to subtract the number obtained at iteration $4$ from the number obtained at iteration $3$ , print "2 3 4".

We will assume that the numbers $x$ and $y$ from the input data were obtained at the 1st and 2nd iterations, respectively.

Note that the number $x$ xor $y$ must come from the last iteration. You are not required to find the answer with the minimum number of actions.

Examples

Example 1

Example 2