시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3451109949.010%

문제

cs71107은 신기한 기계를 발견했다. 기계에는 $1$번부터 $N$번까지 번호가 붙어있는 $N$ 개의 버튼과 수를 표시하는 장치가 하나 있다. 처음에는 $0$이 표시되어 있다.

cs71107은 버튼을 누를 때마다 표시되는 수가 특정한 규칙에 따라 변한다는 사실을 알아냈다. 기존에 표시되는 수를 $X$라고 할 때, $i$번 버튼을 누르면 표시되는 수가 $X \oplus A_{i}$, 즉 $X$와 $A_{i}$의 bitwise XOR로 변한다는 사실을 알아냈다.

버튼을 몇 개씩 눌러보던 중 cs71107은 표시되는 수로 서로 다른 수를 최대한 많이 만들고 싶다고 생각했다. 단, 아무 방법으로만 만들면 재미없다고 생각해서 버튼을 최대한 적게, 또 그런 방법이 여러 개라면 누른 버튼의 번호로 이루어진 수열이 사전 순으로 가장 앞선 방법으로 누르고 싶었다.

안타깝게도 cs71107은 이 문제를 해결할 수 있을 정도로 똑똑하지 않다. 여러분이 cs71107을 도와서 문제를 해결해 주자!

입력

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $N$개의 정수 $A_1,A_2, \cdots , A_N$이 공백으로 구분되어 주어진다.

출력

첫째 줄에 서로 다른 수를 최대한 많이 만들기 위해 버튼을 눌러야 하는 최소 횟수인 $K$를 출력한다.

두 번째 줄부터 $K$ 개의 줄을 출력한다. 이 중 $i$ 번째 줄에는 $i$ 번째로 눌러야 하는 버튼의 번호를 출력한다. 가능한 답이 여럿 있으면 사전 순으로 가장 앞서는 답을 출력한다.

제한

  • $1 \leq N \leq 100$
  • $0 < A_{i} < 2^{20}$
  • 입력으로 주어지는 모든 수는 정수이다.

예제 입력 1

2
1 2

예제 출력 1

3
1
2
1

$1$번, $2$번, $1$번 버튼을 순서대로 누르면 표시되는 수는 차례로 $0$, $1$, $3$, $2$가 된다.

노트

  • $a$와 $b$의 bitwise XOR인 $a \oplus b$는, 2진법으로 표현했을 때 $a$와 $b$의 $i$ 번째 자리가 같으면 $a \oplus b$의 $i$ 번째 자리가 $0$이고, 서로 다르면 $1$이 되도록 계산한다.
  • 수열 $A_1, A_2, \cdots, A_K$가 $B_1, B_2, \cdots, B_K$보다 사전 순으로 앞선다는 의미는, $1$ 이상 $K$ 이하의 정수 $i$가 존재해서, $A_1 = B_1, A_2 = B_2, \cdots, A_{i-1} = B_{i-1}$이고, $A_i < B_i$임을 의미한다.

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2021! E번