#include using namespace std; using int64 = long long; bool is_prime(int x) { if (x < 2) return false; if (x % 2 == 0) return x == 2; for (int d = 3; 1LL * d * d <= x; d += 2) { if (x % d == 0) return false; } return true; } vector distinct_prime_factors(int x) { vector factors; for (int d = 2; 1LL * d * d <= x; ++d) { if (x % d != 0) continue; factors.push_back(d); while (x % d == 0) x /= d; } if (x > 1) factors.push_back(x); return factors; } int64 mod_pow(int64 a, int64 e, int64 mod) { int64 result = 1; while (e > 0) { if (e & 1) result = result * a % mod; a = a * a % mod; e >>= 1; } return result; } // p は素数 int primitive_root(int p) { vector factors = distinct_prime_factors(p - 1); for (int g = 2; g < p; ++g) { bool ok = true; for (int q : factors) { if (mod_pow(g, (p - 1) / q, p) == 1) { ok = false; break; } } if (ok) return g; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; const int M = N * N; // p - 1 >= M となる最小の素数 int p = M + 1; while (!is_prime(p)) ++p; const int g = primitive_root(p); const int Q = p - 1; const int64 MOD = 1LL * p * (p - 1); /* * Ruzsa の巡回 Sidon 集合 * * a_i = p*i + (p-1)*g^i mod p(p-1) * 0 <= i <= p-2 */ vector cyclic_marks; cyclic_marks.reserve(Q); int64 power = 1; for (int i = 0; i < Q; ++i) { int64 value = (1LL * p * i + 1LL * (p - 1) * power) % MOD; cyclic_marks.push_back(value); power = power * g % p; } sort(cyclic_marks.begin(), cyclic_marks.end()); // 円周を 2 周分展開する vector extended(2 * Q); for (int i = 0; i < Q; ++i) { extended[i] = cyclic_marks[i]; extended[i + Q] = cyclic_marks[i] + MOD; } // 蛇行順での位置 auto position = [N](int row, int column) -> int { if (row % 2 == 0) { return row * N + column; } else { return row * N + (N - 1 - column); } }; // 蛇行順で表現した全グリッド辺 vector> edges; edges.reserve(2 * N * (N - 1)); // 縦辺 for (int row = 0; row + 1 < N; ++row) { for (int column = 0; column < N; ++column) { edges.emplace_back( position(row, column), position(row + 1, column) ); } } // 横辺 for (int row = 0; row < N; ++row) { for (int column = 0; column + 1 < N; ++column) { edges.emplace_back( position(row, column), position(row, column + 1) ); } } int best_start = -1; int64 best_maximum_weight = (1LL << 60); // 円を切る位置を全探索 for (int start = 0; start < Q; ++start) { int64 maximum_weight = 0; for (auto [u, v] : edges) { int64 weight = llabs(extended[start + u] - extended[start + v]); maximum_weight = max(maximum_weight, weight); } if (maximum_weight < best_maximum_weight) { best_maximum_weight = maximum_weight; best_start = start; } } if (best_start == -1 || best_maximum_weight > 300000) { cout << -1 << '\n'; return 0; } vector mark(M); for (int i = 0; i < M; ++i) { mark[i] = extended[best_start + i] - extended[best_start]; } auto weight = [&](int r1, int c1, int r2, int c2) -> int64 { int x = position(r1, c1); int y = position(r2, c2); return llabs(mark[x] - mark[y]); }; // 縦辺 for (int row = 0; row + 1 < N; ++row) { for (int column = 0; column < N; ++column) { if (column > 0) cout << ' '; cout << weight( row, column, row + 1, column ); } cout << '\n'; } // 横辺 for (int row = 0; row < N; ++row) { for (int column = 0; column + 1 < N; ++column) { if (column > 0) cout << ' '; cout << weight( row, column, row, column + 1 ); } cout << '\n'; } }