판드랄추

시간 제한1초메모리 제한1024 MB

요약

서로 다른 a와 b가 주어질 때 한쪽에는 xor, 다른 쪽에는 덧셈을 하는 명령으로 두 값을 같게 만드는 최소 명령 수를 구한다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 동적 계획법, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

어느 날 게시판을 둘러보던 피돌이는 추천이 $a$ 개, 비추천이 $b$ 개인 글을 발견했다. 피돌이는 추천과 비추천의 수가 같아야 편안해지기 때문에 조작프로그램을 이용해 이를 조작하기로 했다.

조작 프로그램은 $c\ x$ 와 같은 형식의 명령어를 입력해 사용할 수 있다. $c$ 는 A 또는 B이고 $x$ 는 $1$ 이상 $2^{30}$ 미만의 정수이다. 현재의 추천 수와 비추천 수를 각각 $p$ , $q$ 라고 하자. 명령어를 입력했을 때 일어나는 일은 다음과 같다.

$c$ 가 A인 경우, 추천 수가 $p \oplus x$ 가 되고 비추천 수가 $q+x$ 가 된다.
$c$ 가 B인 경우, 추천 수가 $p + x$ 가 되고 비추천 수가 $q \oplus x$ 가 된다.

단, 조작된 추천 수와 비추천 수에는 상한이 없다.

조작 프로그램을 이용해 추천 수와 비추천 수를 같게 만들 수 있는지 판별하고, 가능하다면 그 중 명령어를 최소로 입력하는 방법을 찾아보자.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. $(1\leq T \leq 10\ 000)$

각 테스트 케이스의 첫째 줄에 추천 수와 비추천 수 $a$ , $b$ 가 공백을 두고 주어진다. $(0 \leq a,b < 2^{30}; a \neq b)$

출력

각 테스트 케이스의 첫째 줄에 입력해야 하는 명령어의 최소 개수 $K$ 를 출력한다. 불가능하다면 -1을 출력한다.

각 테스트 케이스에서 실행이 가능한 경우, 다음 $K$ 줄에 입력해야 하는 명령어를 $c\ x$ 꼴로 출력한다.

힌트

$\oplus$ 는 xor연산을 나타낸다.

예제1

예제 1
입력
```
2
3 4
3 5
```
예상 출력
```
-1
1
B 1
```