Description

Rumia: The Great Fairy wants to construct a finite field of order $n$, where the elements are represented by the integers $0 \sim n - 1$.

A finite field must satisfy the following conditions:

1. There exists an additive identity $o$, such that for any element $a$, $o + a = a + o = a$.
2. For any element $a$, there exists an additive inverse $a^{-1}$, such that $a + a^{-1} = a^{-1} + a = o$.
3. There exists a multiplicative identity $i$ different from the additive identity $o$, such that for any element $a$, $i \times a = a \times i = a$.
4. For any element $a$ that is not the additive identity, there exists a multiplicative inverse $a^{-1}$, such that $a \times a^{-1} = a^{-1} \times a = i$.
5. For any elements $x$, $y$, addition is commutative, i.e., $x + y = y + x$.
6. For any elements $x$, $y$, multiplication is commutative, i.e., $x \times y = y \times x$.
7. For any elements $x$, $y$, $z$, addition is associative, i.e., $( x + y ) + z = x + ( y + z )$.
8. For any elements $x$, $y$, $z$, multiplication is associative, i.e., $( x \times y ) \times z = x \times ( y \times z )$.
9. For any elements $x$, $y$, $z$, multiplication distributes over addition, i.e., $( x + y ) \times z = x \times z + y \times z$.

The Great Fairy certainly knows how to do it, but she wants to test you.

In the output, the additive identity $o$ is $0$, and the multiplicative identity $i$ is $1$.

Description

Input Format

A positive integer $n$ ($2 \leq n \leq 350$).

Output Format

On the first line, output an integer $k$. If a finite field of order $n$ exists, then $k = 0$; otherwise $k = -1$.

If $k = 0$, then:

1. Output an $n$-by-$n$ addition table of the finite field in the next $n$ lines. The number in row $i + 1$, column $j + 1$ represents the result of $i + j$ in the field.
2. Output an $n$-by-$n$ multiplication table of the finite field in the following $n$ lines. The number in row $i + 1$, column $j + 1$ represents the result of $i \times j$ in the field.

In total, output $n \times 2 + 1$ lines.

upd1: The SPJ is very strict. Do not output extra spaces at the ends of lines (the trailing newline at the end of the file will still be ignored).

upd2: The official correct-answer file is large, so Luogu may keep judging... If this happens, please submit the source code directly.

2

0
0 1
1 0
0 0
0 1

Hint

Translated by ChatGPT 5