Fanney was very bored in class, so she started playing around with folding paper. As she is not very good at origami, she simply folds her paper in half over and over lengthwise and then unfolds it. When she unravels it, she makes each fold a ninety degree angle, in the direction of the fold. When she then looks at the paper edge-on, she starts to notice some interesting patterns.
Paper before folding.
Paper after folding several times.
Paper after unfolding a few times.
The first five folds, viewed from the paper edge-on.
When seen this way, the paper traces a pleasing path through the plane. She tries to make longer and longer paths, but eventually she starts to struggle to fold the paper enough times.
Could you help her investigate the properties of this folded paper path?
Here the first few folds are shown. The folded paper is shown in purple. Then after unfolding once, the newly added portion is shown in blue. The portion added in the next unfolding step is in green, and so on. The portion up to orange corresponds to the earlier image, while red is what would be added with one more fold.
We choose the coordinate system such that one end of the paper is at $$$(0, 0)$$$, with the paper starting to go along the $$$x$$$-axis.
The first line contains an integer $$$n$$$ ($$$0 \leq n \leq 10^{100}$$$).
Print the location one reaches after following the paper path for $$$n$$$ steps. This is indexed such that we are at $$$(0, 0)$$$ after $$$0$$$ steps and at $$$(1, 0)$$$ after $$$1$$$ step.
1
1 0
8
-2 2
22
-3 -1
