바이너리 파워 비숍

시간 제한2초메모리 제한128 MB

요약

대각선으로 서로 다른 2의 거듭제곱 크기만큼 한 번씩 이동해 (0,0)에서 목표 지점까지 가는 최소 이동 경로를 구하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

바이너리 파워 비숍은 무한한 체스판 위에 있다. 현재 위치가 (x, y)일 때, 아직 사용하지 않은 음이 아닌 정수 k를 하나 골라 2^k칸만큼 대각선으로 이동할 수 있다. 따라서 한 번의 이동으로 (x + 2^k, y + 2^k), (x + 2^k, y - 2^k), (x - 2^k, y + 2^k), (x - 2^k, y - 2^k) 중 하나로 갈 수 있다.

비숍은 (0, 0)에서 출발해 (x, y)로 이동하려고 한다. 방문하는 칸의 수가 최소가 되는 경로를 구하시오.

체스판은 무한히 넓으며, 음수 좌표의 칸도 방문할 수 있다.

입력

첫째 줄에 목표 좌표 x와 y가 공백으로 구분되어 주어진다.

두 수는 모두 100,000,000 이하의 자연수이다.

출력

비숍이 (x, y)까지 이동할 수 있다면, 첫째 줄에 방문하는 칸 수의 최솟값을 출력한다. 둘째 줄부터는 (0, 0)에서 (x, y)까지 비숍이 방문하는 칸을 차례대로 출력한다.

각 좌표는 x,y 형식으로 출력해야 한다. 가능한 최적 경로가 여러 개라면 아무 경로나 출력해도 된다.

이동할 수 없다면 첫째 줄에 -1을 출력한다.

예제4

예제 1
입력
```
8 24
```
예상 출력
```
3
0,0
-8,8
8,24
```
예제 2
입력
```
16 16
```
예상 출력
```
2
0,0
16,16
```
예제 3
입력
```
11 22
```
예상 출력
```
-1
```

예제 4

입력

123 321

예상 출력

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