Binary Power Bishop

Time limit2sMemory limit128 MB

Summary

Find the minimum number of diagonal jumps, each by a distinct power of two, needed to move a bishop from (0,0) to a given point and output the visited cells.

Level: Hard8 of 10
Topics: Bit manipulation, Math, Number theory, Greedy
Solved: No attempts yet

Problem

A binary power bishop is on an infinite chessboard. If it is currently at (x, y), it may choose a nonnegative integer k that has not been used before and move diagonally by 2^k cells to one of (x + 2^k, y + 2^k), (x + 2^k, y - 2^k), (x - 2^k, y + 2^k), or (x - 2^k, y - 2^k).

The bishop starts at (0, 0) and wants to reach (x, y). Find a route that minimizes the number of visited cells.

The chessboard is infinite, and the route may visit cells with negative coordinates.

Input

The first line contains the target coordinates x and y, separated by a space.

Both numbers are positive integers not greater than 100,000,000.

Output

If the bishop can reach (x, y), print the minimum number of visited cells on the first line. Starting from the second line, print the visited cells in order from (0, 0) to (x, y).

Each coordinate must be printed in the form x,y. If there are multiple optimal routes, any one of them may be printed.

If the target cannot be reached, print -1 on the first line.

Examples4

Example 1
Input
```
8 24
```
Expected output
```
3
0,0
-8,8
8,24
```
Example 2
Input
```
16 16
```
Expected output
```
2
0,0
16,16
```
Example 3
Input
```
11 22
```
Expected output
```
-1
```

Example 4

Input

123 321

Expected output

9
0,0
-128,128
-112,112
-104,104
-100,100
102,98
-101,97
-133,65
123,321