머핀 게임

알프와 베아타는 아주 오래전, 프로그래밍 대회를 하며 오후를 보낼 수 없던 시절에 살던 두 청소년이었다. 그래서 두 사람의 삶은 오늘날 청소년의 삶보다 훨씬 지루했다. 컴퓨터 없이 어떻게 살아남았느냐고 묻는다면, 답은 간단하다. 바로 굽는 것이다!

두 청소년은 머핀 굽기를 좋아했고, 다 구우면 커다란 더미가 쌓이곤 했다. 베아타는 부엌을 머핀로 가득 채우지 않으려고 매일 저녁 친구에게 게임을 제안했다. 바로 머핀 게임이다.

머핀 게임은 두 명의 플레이어(여기서는 알프와 베아타)와 $N$개의 머핀이 담긴 큰 더미 하나로 진행된다. 플레이어는 번갈아 가며 차례를 둔다. 한 차례는 플레이어 $A$가 머핀 더미를 두 더미로 나누는 것부터 시작한다(두 더미 중 하나는 비어 있을 수도 있다). 그러면 상대 플레이어가 두 더미 중 하나를 골라 그 더미의 머핀을 모두 먹는다. 다음 차례에는 역할이 바뀌어 플레이어 $B$가 더미를 나누고 플레이어 $A$가 한 더미를 먹는다. 이렇게 머핀이 모두 없어질 때까지 번갈아 가며 진행한다.

알프가 먼저 차례를 시작하고(즉 큰 더미를 나누고), 베아타가 먼저 한 더미를 먹는다. 두 사람이 최선을 다할 때(즉 각자 머핀을 최대한 많이 먹으려 할 때) 게임이 진행되는 동안 알프와 베아타가 각각 몇 개의 머핀을 먹는지 구할 수 있는가?

힌트: 머핀 더미를 나눌 때는 항상 두 더미의 크기가 최대한 비슷해지도록 나누는 것이 좋다(예제 설명 참고).

입력의 첫째 줄이자 유일한 줄에 처음 더미에 있는 머핀의 수 $N$이 주어진다.

두 사람이 최선을 다할 때 알프가 먹을 머핀 수와 베아타가 먹을 머핀 수를 나타내는 두 정수를 출력한다.

• $N \le 10\,000$