시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 5 4 66.667%

문제

성관이는 다음과 같은 조건을 만족하는 집합을 만들려고 한다.

  • 집합의 모든 원소는 서로 다른 자연수이다.
  • 집합의 모든 원소는 [l, r] 범위 내에 있다.
  • 집합의 원소 개수는 1보다 크거나 같고, k보다 작거나 같다.
  • 집합의 모든 원소를 XOR한 값이 최대한 작아야 한다.

위와 같은 조건을 만족하는 집합을 출력하시오.

입력

첫 번째 줄에 세 개의 자연수 l, r, k가 주어진다. (1 ≤ l ≤ r ≤ 1012, 1 ≤ k ≤ min(106, r-l+1))

출력

첫 번째 줄에, 만든 집합의 모든 원소를 XOR한 값을 출력한다.

두 번째 줄에 집합의 크기 |S|를 출력한다.

세 번째 줄에 집합의 각 원소를 나타내는 자연수 |S|개를 출력한다.

만약 조건을 만족하는 집합이 여러 개라면, 아무 것이나 출력해도 관계없다.

예제 입력 1

8 15 3

예제 출력 1

1
2
10 11

예제 입력 2

8 30 7

예제 출력 2

0
5
14 9 28 11 16