31836번 - 피보나치 기념품 스페셜 저지

문제

피보나치 수열은 다음과 같이 정의되는 수열이다.

• $F_1=1$
• $F_2=1$
• $F_n=F_{n-1}+F_{n-2}$ (단, $n\ge 3$)

정휘는 이집트 룩소르의 한 시장에서 피보나치 수가 적혀 있는 $N$개의 기념품을 구매했다. $x(1\le x\le N)$번 기념품에는 $F_x$가 적혀 있다.

정휘는 피보나치 수열을 좋아하는 세림이와 성주에게 기념품을 선물하려고 한다. 하지만 한 명에게 너무 많은 기념품을 주면 기념품을 적게 받은 사람이 슬퍼할 수 있기 때문에, 두 명이 받게 될 기념품에 적힌 피보나치 수의 합이 같아지도록 선물을 분배하려고 한다. 구매한 기념품의 개수 $N$에 따라 $N$개의 기념품을 전부 나눠주지 못할 수 있는데, 이때는 최대한 많은 개수의 기념품을 나눠주려고 한다.

나눠주는 기념품의 개수를 최대화하면서, 두 명이 받는 기념품에 적힌 수의 합이 같도록 기념품을 나눠주는 방법을 구해보자. 두 사람에게 1개 이상의 기념품을 나눠주는 방법은 항상 존재한다.

입력

첫째 줄에 정휘가 구매한 기념품의 개수 $N$이 주어진다.

출력

첫째 줄에 세림이가 받을 기념품의 개수 $X$를 출력한다.

둘째 줄에 세림이가 받을 기념품들의 번호 $A_1,A_2,\cdots ,A_X$를 공백으로 구분해서 출력한다.

셋째 줄에 성주가 받을 기념품의 개수 $Y$를 출력한다.

넷째 줄에 성주가 받을 기념품들의 번호 $B_1,B_2,\cdots ,B_Y$를 공백으로 구분해서 출력한다.

가능한 분배 방법이 여러 가지면 그중 아무거나 하나만 출력하라.

제한

• 2ドル\leq N\leq 2,円 000$
• $X,Y\ge 1$
• 1ドル\le A_i\le N(1\le i\le X)$
• 1ドル\le B_j\le N(1\le j\le Y)$
• $A_1,A_2,\cdots ,A_X,B_1,B_2,\cdots ,B_Y$는 서로 다른 수이다.
• 입력으로 주어지는 수는 모두 정수이다.

힌트