34675번 - 가희와 노선 건설 놀이 3 스페셜 저지

문제

쿠마시에는 쿠마역과 모토역, 그리고 건설 예정인 $k$개의 역이 있습니다. 쿠마시의 교통 회사는 KumaSub사와 KumaBus사만 있습니다. KumaBus사의 사장인 가희는 다음과 같은 정보들을 얻었습니다.

• 쿠마시에 건설될 지하철 노선은 2ドル$개이며, 각 노선들은 비환승역이 하나 이상 존재합니다.
• 건설될 노선의 수요 기대 상수 $C$는 모두 같으며, 기점은 쿠마역이고 종점은 모토역입니다.
• 건설되는 모든 노선은 복선으로 운행하며, 쿠마시에만 속해 있습니다.
• 건설될 노선은 정확히 2ドル$개이며, 이들은 모두 KumaSub사가 운영합니다.
• 건설 예정인 $k$개의 역은 건설될 두 노선 중 하나 이상의 노선에 속합니다.

각 역들은 해당 역에 멈추었을 때 다른 교통수단으로 이탈하려는 수치 $r$이 있습니다. 노선 $x$의 수요 기대 상수와 노선 $x$의 기대 수요는 다음 관계가 성립합니다.

$($노선 $x$에 있는 비환승역들의 $r$의 합$)$ $\cdot$ $($노선 $x$의 기대 수요$)$ $=$ $($노선 $x$의 수요 기대 상수$)$

KumaSub가 가져가는 이익은 해당 회사가 운영하는 노선들의 기대 수요의 합으로 정의합니다. 가희는 자신이 운영하는 회사의 이익을 최대로 하기 위해 시에 몰래 잠입해서 지하철 건설 계획을 수정하려고 합니다. 가희를 도와주세요. 쿠마시의 교통 회사가 가져가는 이익의 합은 항상 일정하며, 쿠마시의 시민들은 버스 혹은 지하철만 이용한다고 가정해도 좋습니다.

입력

첫 번째 줄에 건설될 예정의 비환승역의 개수 $n$이 주어집니다.

두 번째 줄에 1ドル$번 역부터 $n$번 역까지 해당 역에 멈추었을 때 다른 교통수단으로 이탈하려는 수치 $r$이 공백으로 구분되어 주어집니다.

출력

가희가 운영하는 회사의 이익이 최대가 되도록 하는 "지하철 건설 계획"을 다음과 같이 출력해 주세요.

• 첫 번째 줄에 1ドル$번째 노선에 속한 비환승역의 역 개수를 출력해 주세요.
• 두 번째 줄에 1ドル$번째 노선에 속한 비환승역의 역 번호를 공백으로 구분하여 출력해 주세요.
• 세 번째 줄에 2ドル$번째 노선에 속한 비환승역의 역 개수를 출력해 주세요.
• 네 번째 줄에 2ドル$번째 노선에 속한 비환승역의 역 번호를 공백으로 구분하여 출력해 주세요.

제한

• 2ドル \leq n \leq 200$
• 1ドル \leq r \leq 300$
• 입력으로 주어지는 모든 수는 정수입니다.

노트

복선이란, 2개의 궤도로 구성되어 있는 선로를 말합니다. 문제에서의 복선은 상행, 하행으로 이루어져 있는 선로를 의미합니다.