문제

해적 명이 금화 개가 들어있는 보물상자를 발견했다. 욕심이 많고 서로를 무척이나 싫어하는 해적들은 금화를 둘러싸고 오랜 시간 신경전을 벌였다. 긴장 상태가 해소되지 않자 해적 중 한 명이 다음과 같은 제안을 한다.

먼저 제비뽑기를 하여 해적들 사이의 순서를 정한다. 이후 앞 순서인 해적부터 개의 금화를 어떻게 배분할지 제안한다. 제안자를 포함하여 현재 남은 해적들 중 과반이 분배안에 동의한다면 그 제안대로 금화를 배분하고 상황을 종료한다. 만약 과반의 찬성을 얻지 못하면 제안자는 즉시 죽임을 당하고, 다음 순서의 해적이 새로운 제안자가 되어 과정을 반복한다.

모든 해적은 다음과 같은 원칙에 따라 행동하며, 서로가 이 원칙을 지킨다는 사실을 알고 있다.

• 탐욕: 각 해적은 자신의 목숨을 부지하는 것을 최우선으로 하며, 살아남는다는 전제하에 자신이 얻을 수 있는 금화의 양이 최대가 되도록 행동한다. 만약 상황에 따라 자신이 받을 수 있는 금화의 양이 변할 수 있다면, 그중 가장 많이 받을 수 있는 경우를 기준으로 행동한다. 금화를 단 한 개라도 더 얻을 수 있다면 망설임 없이 제안자를 죽인다.
• 잔혹: 자신이 얻을 수 있는 금화의 최댓값이 같다면, 제안자가 죽는 것을 보기 위해 반대 표를 던진다. 다만 아무리 죽음을 즐기더라도 금화를 한 개라도 더 얻는 것을 항상 선호한다.
• 합리성: 모든 해적은 계산 착오를 하지 않으며 항상 자신에게 가장 이득이 되는 방향으로 완벽하게 판단한다.

이때 과반이란 절반 초과를 의미한다. 예를 들어 총원이 명일 때는 명 이상의 동의가 필요하다. 찬성과 반대 이외의 기권은 없다고 할 때, 해적 명이 금화를 어떻게 나누게 될지 구해보자.

입력

첫째 줄에 이 주어진다.

출력

개의 정수를 공백으로 구분하여 출력한다. 번째 () 수는 번째로 제안하는 해적이 모든 상황을 고려했을 때 얻을 수 있는 금화의 최댓값이다.

제약 조건

• 입력으로 주어지는 모든 수는 정수이다.