PALOVE - Pandas are the best Lovers

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 (x1, x2, ..., xn), (y1, y2, ..., yn).

- x12 + y12 ≡ x2(mod p),

- x22 + y22 ≡ x3(mod p),

....

- xn2 + yn2 ≡ x1(mod p),

- 1 ≤ xi, yi ≤ 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 x1, x2, ..., xn, separated by single space. Next and the last line should contain y1, y2, ..., yn in the format of the previous line.

Example

Input:
7

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

Added by:Barish
Date:2018-11-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Deep places of my brain

hide comments
2018-12-06 08:51:05
Keledi ozu. Maraqlidi.

<3

Last edit: 2018-12-07 18:29:00
2018-12-02 09:21:39
You just can't set bad problems, can you =)

Re: Thanks, very happy to see nice feedbacks :) Also, congrats for solving first!

Last edit: 2018-12-03 07:39:53
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.