Muffinspelet

Alf and Beata were two young people who lived a long, long time ago, in an age before anyone could spend their afternoons on programming contests. Their lives were therefore much duller than the lives of young people today. How could anyone survive without computers, you might ask. The answer is simple: you bake!

Our two young people loved baking muffins, and often had large piles of them when they were done baking. To keep their kitchens from filling up with muffins, Beata challenged her friend to a game every evening: Muffinspelet.

Muffinspelet is played by two players (in our case, Alf and Beata) and one large pile of $N$ muffins. The players now take turns making moves. A move consists of player $A$ splitting the muffin pile into two piles (where one of the piles may be empty). The opponent then chooses one of the piles and eats all the muffins in it. On the next move the players switch roles, so player $B$ splits the pile and player $A$ eats one of the piles. They alternate in this way until all the muffins are gone.

Alf starts by making a move (that is, splitting the large pile), and Beata starts by eating one of the piles. Can you compute how many muffins Alf and Beata will eat over the course of the game if both play as well as possible (that is, each wants to eat as many muffins as possible)?

Hint: when splitting a pile of muffins, you always want to split it into two piles whose sizes are as equal as possible (see the example explanations).

The first and only line of the input contains the integer $N$, the number of muffins in the pile at the start.

Print two integers: the number of muffins Alf will eat and the number of muffins Beata will eat if both play as well as possible.

• $N \le 10\,000$