A. (A + B) mod P
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

AGI (artificial general intelligence) is around the corner, but it still cannot add two integers modulo prime. In this task, you can speed up the AGI revolution by training a one-layer perceptron model with $$$n$$$ neurons for a fixed prime $$$p$$$. This model takes two integers $$$a$$$ and $$$b$$$ as inputs and calculates $$$(a + b) \bmod p$$$. The architecture of the model is:

$$$$$$ ReLU(a_{one-hot}W_{input}+b_{one-hot}W_{input})W_{output}^{T} $$$$$$

where

$$$$$$ ReLU(x) = max(x, 0) $$$$$$

and $$$x_{one-hot}$$$ is a matrix of size $$$1 \times p$$$, which consists of all zeros and a single one in column $$$x$$$.

For example, if $$$p=4$$$, $$$0_{one-hot} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix}$$$, $$$2_{one-hot} = \begin{pmatrix}0 & 0 & 1 & 0\end{pmatrix}$$$.

In other words, you must choose the number of neurons $$$n$$$ and generate two real matrices $$$W_{input}$$$ and $$$W_{output}$$$ of size $$$p \times n$$$.

To add integers $$$a$$$ and $$$b$$$ three steps are executed:

  1. The pointwise sum of 0-indexed rows $$$a$$$ and $$$b$$$ of the $$$W_{input}$$$ is calculated.
  2. All negative numbers in this sum are replaced with zeros. Let's call the generated row $$$M$$$.
  3. The score of integer $$$i$$$ is defined as the scalar product of $$$M$$$ and $$$i$$$-th row of the $$$W_{output}$$$. The integer with the highest score should equal $$$(a+b) \bmod p$$$.

See the example explanation for better understanding.

You need to generate two real matrices $$$W_{input}$$$ and $$$W_{output}$$$ that for all pairs $$$(a, b), 0 \le a, b \lt p$$$, the output produced by the model is correct.

Input

The only line of the input consists of the integer $$$p$$$ ($$$3 \le p \le 100$$$). It is guaranteed that $$$p$$$ is prime.

Output

The first line of the output should contain the integer $$$n$$$ ($$$1 \le n \le 25$$$) — the number of neurons in the model.

In the following $$$p$$$ lines, output matrix $$$W_{input}$$$. Each line should consist of $$$n$$$ real numbers not greater than 1000 by the absolute value.

After that, output matrix $$$W_{output}$$$ in the same format.

Example
Input
3
Output
4
2.5 3.0 -0.5 -3.0 
-3.0 0.0 0.5 2.0 
-0.5 0.5 -3.0 1.5 

1.5 1.0 -2.0 2.5 
-3.0 3.0 -1.0 2.0 
-0.5 2.5 0.5 2.0
Note

Let's calculate $$$(1+2) \bmod 3$$$. First, we add rows $$$[-3.0, 0.0, 0.5, 2.0]$$$ and $$$[-0.5, 0.5, -3.0, 1.5]$$$ and get $$$[-3.5, 0.5, -2.5, 3.5]$$$. Then, we remove all negative numbers: $$$[0.0, 0.5, 0.0, 3.5]$$$.

Then, we calculate the score for each possible result:

  • 0: $$$[0.0, 0.5, 0.0, 3.5] \times [1.5, 1.0, -2.0, 2.5] = 0.0 \cdot 1.5 + 0.5 \cdot 1.0 + 0.0 \cdot -2.0 + 3.5 \cdot 2.5 = 9.25$$$.
  • 1: $$$[0.0, 0.5, 0.0, 3.5] \times [-3.0, 3.0, -1.0, 2.0] = 8.5$$$.
  • 2: $$$[0.0, 0.5, 0.0, 3.5] \times [-0.5, 2.5, 0.5, 2.0] = 8.25$$$.

Row 0 has the highest score 9.25, and $$$(1+2) \bmod 3$$$ indeed equal 0.