문제

준혁이는 피보나치 동전을 화폐로 사용하는 피보나치 마을에서 살고 있다. 번째 피보나치 동전은 번째 피보나치 수 만큼의 가치를 가진다.

는 번째 피보나치 수를 의미한다. 이고, 에서 로 정의된다.

준혁이의 일차의 재산은 로 나타낸다. 준혁이는 일차에 재산이 없으므로 이다. 준혁이는 일동안 정당한 노동을 하여 일차 아침에는 번째 피보나치 동전을 받게 된다. 즉 이다.

준혁이는 매일 밤 자신의 재산을 최소 개수의 피보나치 동전들로 만들 때 몇 개가 필요할지 궁금해진다.

일차 부터 일차의 밤까지, 재산 를 피보나치 동전들의 합으로 표현할 때 필요한 최소 동전 개수 를 구하라.

입력

첫째 줄에 이 주어진다.

둘째 줄에 이 주어진다.

출력

첫째 줄에 을 공백으로 구분하여 출력한다.

노트

예제 1 :

이다. 번째 피보나치 동전 하나면 을 만들 수 있다.

이다. 번째 동전 하나면 를 만들 수 있다.

이다. 번째 동전 하나와 번째 동전 하나가 있으면 을 만들 수 있다.