Zlatograd
Grad Zlatograd dobio je novog gradonačelnika koji voli brojeve. Gradonačelnik je odlučio da kućni brojevi u ulicama moraju biti Fibonaccijevi brojevi. Svaki kućni broj mora biti iz skupa kod kojeg su prva dva člana 1 i 2, a svaki slijedeći se dobije kao zbroj prethodna dva (početak skupa je: {1, 2, 3, 5, 8, 13, 21, ...}). Kao i u drugim gradovima, na jednoj strani ulice se nalaze kuće s parnim brojevima, a na drugoj one čiji su kućni brojevi neparni. Ako znate da je za numeriranje kuća neke ulice bilo potrebno \(n\) brojeva, izračunajte koliko kuća se nalazi na svakoj strani ulice.
Ulaz
U jedinom retku dan je broj \(n\), \((1 \leq n \leq 10^{18})\), broj kuća u ulici.
Izlaz
U jedini redak ispišite dva broja, prvo broj kuća s parne strane ulice, a zatim broj kuća s neparne strane ulice.
U 20% primjera će vrijediti \(n \leq 15\),
U 50% primjera će vrijediti \(n \leq 10^5\).
Primjer ulaza
3
Primjer izlaza
1 2
Primjer ulaza
5
Primjer izlaza
2 3
Pojašnjenje
S lijeve strane ulice se nalaze brojevi 1, 3 i 5, a s desne 2 i 8.
Comments