Today the boy Sasha learned about fractals at a mathematics lesson. The teacher showed the so-called "dragon curve". It is a geometric figure, which is constructed as follows: at the first step, a segment is drawn from the origin of the coordinate plane to the point (0; 1). Further, at each step from the end of the fractal, the already drawn part of the figure is repeated, rotated 90 degrees counterclockwise (see figure).
After the lessons, Sasha tried to draw the "dragon curve" himself, and now he wants to know at what point on the coordinate plane he finished drawing the fractal by following the N steps described above. It is required to write a program that, given the number of N determines the coordinates of the end of the fractal after performing N steps.
Input
A single integer is entered
N (1 <= N <= 30).
Imprint
Output two space-separated numbers - the coordinates of the end of the fractal.
Examples
| # |
Input |
Output |
| 1 |
2 |
1 1 |
| 2 |
4 |
2 -2 |