아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

역기

시간 제한2초메모리 제한512 MB

요약
무게 1부터 n까지인 바벨을 세 사람이 같은 총 무게로 나누어 갖도록 분배하고, 불가능하면 Impossible을 출력한다.
난이도

보통10점 중 5점

유형
수학, 그리디, 구현, 조합론
정답자
아직 제출이 없습니다

문제

Vanya, Seryozha, Dima는 운동을 좋아한다. 그중에서도 무거운 것을 드는 걸 가장 좋아한다. 세 사람은 오래전부터 역기 운동을 해 왔고, 연습용 역기 세트도 이미 모아 두었다. 이 세트는 1부터 nn까지 서로 다른 정수 무게를 가진 nn개의 역기로 이루어져 있다.

얼마 전 세 사람은 새 체육관을 발견하고 역기를 모두 그곳으로 옮기기로 했다. 역기를 드는 것을 좋아하는 만큼, 각자 최대한 무거운 무게를 들고 가고 싶어 한다. 하지만 세 사람은 매우 정직해서 전체 무게를 똑같이 나누기로 했다.

무게가 1,2,…,n1, 2, \ldots, n인 nn개의 역기 세트를 무게가 같은 세 부분으로 나누는 것을 도와주자.

입력

입력 파일에는 정수 nn 하나가 주어진다 (1≤n≤100 0001 \leq n \leq 100\,000). nn은 역기의 개수다.

출력

각 선수가 새 체육관으로 옮겨야 할 역기 세트를 출력한다. 세트는 다음과 같이 출력한다. 첫째 줄에는 세트에 있는 역기의 개수를 출력한다. 그다음 줄에는 역기의 무게를 공백으로 구분해 출력한다.

모든 역기를 무게가 같은 세 집합으로 나눌 수 없으면 <<Impossible>>을 출력한다.

해가 여러 개라면 아무거나 하나 출력해도 된다.

예제2

  1. 예제 1

    입력
    6
    
    예상 출력
    2
    3 4
    2
    5 2
    2
    1 6
    
  2. 예제 2

    입력
    3
    
    예상 출력
    Impossible