34407번 - x와 배수와 XOR (Hard)

문제

이 문제는 굵은 글씨로 적힌 출력 조건을 제외하면 x와 배수와 XOR (Easy)와 동일한 문제이다.

전남대학교 게임개발동아리 PIMM에 놀러 온 지훈은 동아리 사람들이 수상하게 XOR을 좋아한다는 사실을 깨닫고, $x$의 배수들을 적절히 XOR해서 다시 $x$를 만드는 게임을 고안하였다.

지훈이 만든 게임을 플레이하기 위해서는 음이 아닌 정수 $x$가 주어졌을 때, 다음 조건들을 모두 만족하는 정수 배열 $[k_1,\cdots,k_n]$을 찾아서 출력해야 한다.

• $n$은 1ドル$ 이상의 정수이다.
• 각 $k_i$는 정수이며, 1ドル \lt k_i \lt 2^{31}$이다.
• $(k_1\times x) \oplus \cdots \oplus (k_n \times x)=x$가 성립한다.

게임을 다 만든 지훈은 컴퓨터가 채점을 할 때 매우 비싼 연산인 곱셈 연산을 $n$번이나 수행해야 한다는 사실을 깨닫고, 채점을 해야 하는 컴퓨터의 입장을 고려하여 다음과 같은 조건을 추가하였다.

• 조건을 만족하는 배열 중에서 원소의 개수 $n$이 최소인 배열을 찾고, 그 배열을 출력하라. 조건을 만족하는 배열이 여러 개라면, 그중 사전순으로 가장 앞선 배열을 출력해야 한다.

지훈이 만든 게임을 플레이해 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

두 번째 줄부터 $T$개의 줄에 걸쳐 각 테스트 케이스마다 한 줄에 정수 $x$가 주어진다.

출력

각 테스트 케이스마다 아래와 같이 두 줄로 구성된 답안을 출력한다.

첫 번째 줄에 조건을 만족하는 배열의 원소 개수 $n$을 출력한다.

두 번째 줄에 해당 배열의 원소 $k_1,\cdots,k_n$을 공백으로 구분하여 출력한다. 조건을 만족하는 배열이 여러 개라면, 그중 사전순으로 가장 앞선 배열을 출력해야 한다. 조건을 만족하는 배열이 반드시 존재하는 입력만 주어진다.

제한

• 1ドル \le T \le 100$
• 0ドル \le x \le 10^9$

노트

$\oplus$는 Bitwise XOR을 나타내는 기호이다.

1ドル \lt k_i$인 이유는, 만약 1ドル \le k_i$로 조건을 설정할 경우 $n=1, k_1=1$이 항상 답이 되어 게임이 재미 없어지기 때문이다.

$k_i \lt 2^{31}$인 이유는, 이 조건이 없으면 채점기를 만들기 힘들기 때문이다.

수열 $A$가 $B$보다 사전순으로 앞선다는 것은 $A[i] \ne B[i]$가 성립하는 최소의 $i$에 대해 $A[i] \lt B[i]$가 성립한다는 것을 의미한다.