Inspect the following rows: \[ \begin{aligned} R_1 &= 1, 2, 4, 8, 16, 32, \ldots \\ R_2 &= 1, -1, 1, -1, 1, -1, \ldots \\ R_3 &= 1, -4, 9, -16, 25, -36, \ldots \end{aligned} \]

Input

A natural number n, $$1\leq n\leq 20$$.

Output

The first n terms of these three rows, each on a separate line. The various values of each row are always separated by a single space.

Example

Input:

6

Output:

1 2 4 8 16 32
1 -1 1 -1 1 -1
1 -4 9 -16 25 -36