배낭 문제 준비하기 Batch Compilation commands

문제를 출제하는 과정 중에서 중요한 축 중 하나가 바로 데이터를 만드는 일입니다. 데이터를 만드는 일반적인 방법 같은 것은 없고, 문제에 따라 발생할 수 있는 모든 오답들을 최대한 생각해보고 이들에 대비한 데이터를 만들어야 합니다.

예를 들어 아래와 같은 유명한 문제를 생각해 봅시다.

저는 이 문제에서 발생할 수 있는 다양한 오답들을 떠올리다가, 답이 정확히 $t$인 데이터에서 $t - 1$을 출력하는 답안을 생각해냈습니다. 이러한 답안을 걸러주는 데이터를 마련하기 위해, 저는 어떤 자연수 $t$가 주어졌을 때, 위 문제의 답이 $t$가 되도록 하는 집합 $S$와 자연수 $k$를 구해주는 프로그램이 필요합니다.

하지만 저는 그 능력이 부족한 관계로, 여러분이 대신 프로그램을 작성해주셔야 합니다.

입력 형식

첫 번째 줄에 자연수 $t$가 주어집니다.

출력 형식

첫 번째 줄에 $n$과 $k$를 공백을 사이로 두고 출력합니다. 두 번째 줄에 $a_{1}, a_{2}, ..., a_{n}$을 공백을 사이로 두고 출력합니다.

모든 변수의 이름과 제약 조건은 위 그림에 나타낸 문제와 같습니다. 출력한 데이터는 반드시 이 조건을 충족해야 합니다.

제약 조건

• $1 \le t \le 10^{18}$

부분문제

부분문제	점수	t
1	5	≤ 300
2	13	≤ 104
3	17	≤ 105
4	29	≤ 109
5	36	≤ 1018

예제

예제 1

입력

1

출력

4 13
1 2 4 8

예제 2

입력

3

출력

4 3
1 1 2 3

예제 3

입력

17

출력

10 12
1 2 3 4 5 6 7 8 9 5