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

문제

귀여운 아기 주환이에게는 $1$부터 $N$까지의 양의 정수가 적힌 숫자 카드가 있다.

주환이는 오늘이 자신과 가장 친한 아기 블롭의 생일이라는 사실을 알고, 선물로 $K$장의 카드를 주었다.

주환이는 카드를 다음 조건에 맞게 뽑았다.

  • 뽑은 카드들에 적힌 수를 모두 ⊕한 값이 최대가 되어야 한다. ⊕는 배타적 논리합(xor)을 의미한다.
  • 첫 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 카드를 최대한 적게 뽑아야 한다.
  • 두 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 사전 순으로 가장 앞서도록 뽑아야 한다.

$K$와 고른 카드에 적힌 각 수를 구하자.

입력

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

출력

첫째 줄에 $K$를 출력한다. $K$는 $N$ 이하인 양의 정수이다.

둘째 줄부터 조건을 만족하는 $K$개의 카드에 적힌 양의 정수를 한 줄에 하나씩 오름차순으로 출력한다.

가능한 답이 여러 경우라면, 사전 순으로 가장 앞서는 것을 출력한다.

제한

  • $1 \leq N \leq 10^{18}$

예제 입력 1

7

예제 출력 1

1
7

노트

길이 K의 수열 A가 같은 길이의 수열 B보다 사전순으로 앞선다는 것은, A의 1~(i-1)번째 원소와 B의 1~(i-1)번째 원소가 같으면서, A의 i번째 원소가 B의 i번째 원소보다 작은 i가 있다는 것이다.

출처

Contest > BOJ User Contest > 블롭컵 > 제1회 블롭컵 C번