수 이어가기

다음 규칙으로 수열을 만든다.

1. 첫 번째 수는 입력으로 주어지는 양의 정수이다.
2. 두 번째 수는 임의의 양의 정수로 고른다.
3. 세 번째 수부터는 바로 앞의 두 수 중 앞앞의 수에서 앞의 수를 뺀 값으로 만든다. 즉, a_i = a_{i-2} - a_{i-1}이다.
4. 새로 만든 값이 음수이면 그 값은 버리고 수열 생성을 멈춘다.

첫 번째 수가 100일 때 두 번째 수로 60을 고르면 100, 60, 40, 20, 20, 0, 20처럼 7개의 수가 만들어진다. 두 번째 수로 62를 고르면 100, 62, 38, 24, 14, 10, 4, 6처럼 8개의 수가 만들어진다. 이처럼 첫 번째 수가 같아도 두 번째 수에 따라 만들 수 있는 수의 개수가 달라진다.

첫 번째 수가 주어졌을 때, 위 규칙으로 만들 수 있는 가장 긴 수열을 구하라. 가장 긴 수열이 여러 개이면 그중 하나만 출력하면 된다.

첫 번째 수 N이 주어진다. N은 30,000 이하의 양의 정수이다.

첫째 줄에 만들 수 있는 수열의 최대 길이를 출력한다.

둘째 줄에 그 수열의 수들을 순서대로 공백 한 칸으로 구분하여 출력한다.