Who doesn't love pandas? But more importantly, which panda doesn't love? They are the best lovers, believe me. Furthermore, the relationship is the strongest when they have love with bears. These are not just facts, also have proven practically. Pandas are somewhat good at mathematics, so they like presenting mathematical gifts to their lovers, bears. Pandagorean the panda proved following theorem and it is called the Pandagorean theorem:

For given prime number p, there exist two sequences with the following properties:

- Both sequences have the same length and let it be n. Also, let the sequences be (x₁, x₂, ..., x_n), (y₁, y₂, ..., y_n).

- x₁² + y₁² ≡ x₂²  (mod p),

- x₂² + y₂² ≡ x₃²  (mod p),

....

- x_n² + y_n² ≡ x₁²  (mod p),

- 1 ≤ x_i, y_i ≤ p-1 for each valid i.

- 1 ≤ n ≤ 10*p

However, she couldn't find such two sequences. In the calendar of panda world, all numbers are prime numbers and her lover Bearsh the bear was born in the p'th day of the only month. So, she needs to find any two sequences satisfying above conditions with that p. Why don't you help her?

Input

The only line consisting of the number p (7 ≤ p ≤ 100000).

Output

In the first line of the output the number n.  The second line should contain the numbers x₁, x₂, ..., x_n, separated by single space. Next and the last line should contain y₁, y₂, ..., y_n in the format of the previous line.

Example

Input:
7

Output:
6
1 4 2 1 4 2
6 3 5 6 3 5