#include using namespace std; using ll = long long; using Clock = chrono::steady_clock; constexpr int MAX_W = 300000; constexpr double TIME_LIMIT = 1.9; constexpr int TRIALS_PER_VERTEX = 300; int vertical_id(int n, int r, int c) { return r * n + c; } int horizontal_id(int n, int r, int c) { return n * (n - 1) + r * (n - 1) + c; } bool construct(int n, mt19937& rng, Clock::time_point deadline, vector& answer) { int v = n * n; const ll INF = (1LL << 60); vector dist((size_t)v * v, INF), to_new(v); dist[0] = 0; answer.assign(2 * n * (n - 1), 1); uniform_int_distribution weight(1, MAX_W); for (int x = 1; x < v; ++x) { int r = x / n, c = x % n; vector> edge; if (r > 0) edge.push_back({x - n, vertical_id(n, r - 1, c)}); if (c > 0) edge.push_back({x - 1, horizontal_id(n, r, c - 1)}); bool fixed = false; for (int trial = 0; trial < TRIALS_PER_VERTEX; ++trial) { if (Clock::now() >= deadline) return false; vector w(edge.size()); for (int& z : w) z = weight(rng); for (int i = 0; i < x; ++i) { to_new[i] = INF; for (int j = 0; j < (int)edge.size(); ++j) to_new[i] = min(to_new[i], dist[(size_t)i * v + edge[j].first] + w[j]); } unordered_set seen; seen.reserve((size_t)(x + 1) * x); bool ok = true; for (int j = 1; j < x && ok; ++j) { for (int i = 0; i < j; ++i) { ll d = min(dist[(size_t)i * v + j], to_new[i] + to_new[j]); if (!seen.insert(d).second) { ok = false; break; } } } for (int i = 0; i < x && ok; ++i) if (!seen.insert(to_new[i]).second) ok = false; if (!ok) continue; // Floyd-Warshallで中継頂点 x を1つ追加する場合と同じ更新。 for (int j = 1; j < x; ++j) for (int i = 0; i < j; ++i) { ll d = min(dist[(size_t)i * v + j], to_new[i] + to_new[j]); dist[(size_t)i * v + j] = dist[(size_t)j * v + i] = d; } for (int i = 0; i < x; ++i) dist[(size_t)i * v + x] = dist[(size_t)x * v + i] = to_new[i]; dist[(size_t)x * v + x] = 0; for (int j = 0; j < (int)edge.size(); ++j) answer[edge[j].second] = w[j]; fixed = true; break; } if (!fixed) return false; } return true; } void output(int n, const vector& answer) { int k = 0; for (int r = 0; r + 1 < n; ++r) { for (int c = 0; c < n; ++c) cout << (c ? " " : "") << answer[k++]; cout << '\n'; } for (int r = 0; r < n; ++r) { for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << answer[k++]; cout << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); auto deadline = Clock::now() + chrono::duration_cast(chrono::duration(TIME_LIMIT)); vector answer; while (Clock::now() < deadline) { if (construct(n, rng, deadline, answer)) { output(n, answer); return 0; } } cout << -1 << '\n'; }