// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2") #include using namespace std; #include using namespace atcoder; // #include // using namespace boost::multiprecision; #define ll long long #define ld long double #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define vi vector #define vl vector #define vd vector #define vb vector #define vs vector #define vc vector #define ull unsigned long long #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() template inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } // #define ll int // #define ll int128_t // #define ll int256_t // #define ll cpp_int constexpr ll inf = (1ll << 62); // constexpr ll inf = (1 << 30); // const double PI=3.1415926535897932384626433832795028841971; uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123; inline uint32_t xor_next() { uint32_t t = xor_x ^ (xor_x << 11); xor_x = xor_y; xor_y = xor_z; xor_z = xor_w; return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8)); } inline int rnd(int max_val) { return xor_next() % max_val; } struct Timer { std::chrono::steady_clock::time_point start_time; Timer() { reset(); } // 測定の起点リセット用 void reset() { start_time = std::chrono::steady_clock::now(); } // スタートからの経過時間をミリ秒(msec)で返す long long get_ms() const { auto now = std::chrono::steady_clock::now(); return std::chrono::duration_cast(now - start_time).count(); } }; // ll rui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a*rui(a*a,b/2); // return rui(a*a,b/2); // } // vl fact; // ll kai(ll n){ // fact.resize(n,1); // rep(i,n-1)fact[i+1]=fact[i]*(i+1); // } // using mint = ld; using mint = modint998244353;//static_modint<998244353> // using mint = modint1000000007;//static_modint<1000000007> // using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly // using mint = static_modint<469762049>; // ntt-friendly // using mint = static_modint<167772161>; // ntt-friendly // using mint = modint;//mint::set_mod(mod); // ll const mod=1000000007ll; // ll const mod=998244353ll; // ll modrui(ll a,ll b,ll mod){ // a%=mod; // if(b==0)return 1; // if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod; // return modrui(a*a%mod,b/2,mod)%mod; // } // void incr(vl &v,ll n){//　n進法 // ll k=v.size(); // v[k-1]++; // ll now=k-1; // while (v[now]>=n) // { // v[now]=0; // if(now==0)break; // v[now-1]++; // now--; // } // return; // } vector fact,invf; void init_modfact(ll sz){ fact.resize(sz); invf.resize(sz); fact[0]=1; rep(i,sz-1){ fact[i+1]=fact[i]*(i+1); } invf[sz-1]=1/fact[sz-1]; for(ll i=sz-2; i>=0; i--){ invf[i]=invf[i+1]*(i+1); } } mint choose(ll n,ll r){ if(n modpow,invpow; // void init_modpow(ll x,ll sz){ // mint inv=1/mint(x); // modpow.assign(sz,1); // invpow.assign(sz,1); // rep(i,sz-1){ // modpow[i+1]=modpow[i]*x; // invpow[i+1]=invpow[i]*inv; // } // } // long long phi(long long n) {// O(sqrt(n)) // long long res = n; // for (long long i = 2; i * i <= n; i++) { // if (n % i == 0) { // res -= res / i; // while (n % i == 0) n /= i; // } // } // if (n > 1) res -= res / n; // return res; // } void solve(){ ll n; cin >> n; vector r(n,vl(n-1,0)); vector c(n-1,vl(n,0)); const ll M=300000; ll iter=0; if(n==1){ // return; } if(n==2){ cout << "199111 119409\n" << "287787\n" << "72619\n"; return; } if(n==3){ cout << "199111 69575 239114\n" << "119409 229869 10822\n" << "287787 72619\n" << "91519 149380\n" << "166585 195573\n"; return; } if(n==4){ cout << "199111 229869 174474 207047\n" << "119409 239114 253238 169645\n" << "69575 10822 288983 132713\n" << "287787 72619 91519\n" << "149380 166585 195573\n" << "170321 153269 15221\n" << "281933 253449 60397\n"; return; } if(n==5){ cout << "199111 239114 288983 34234 175419\n" << "119409 10822 207047 253313 278732\n" << "69575 174474 169645 157460 94861\n" << "229869 253238 132713 149641 127416\n" << "287787 72619 91519 149380\n" << "166585 195573 170321 153269\n" << "15221 281933 253449 60397\n" << "280800 106654 206779 102566\n" << "90347 90040 16209 50044\n"; return; } if(n==6){ cout << "206760 192027 137473 188017 220403 16100\n" << "279971 202643 145037 177750 164401 246975\n" << "41161 188211 294588 270828 169742 146022\n" << "288207 238363 11818 28538 276216 249463\n" << "17323 146452 148053 96138 220870 123633\n" << "96297 228847 134210 32665 179652\n" << "28895 90604 173947 62213 230369\n" << "268434 101748 229439 232413 7556\n" << "134816 125817 156967 237757 240805\n" << "17180 224545 108154 253427 92084\n" << "150340 85876 181960 152616 65534\n"; return; } if(n==7){ cout << "199111 174474 34234 94861 272370 206760 202643\n" << "119409 253238 253313 127416 111098 279971 188211\n" << "69575 288983 157460 76301 22359 41161 238363\n" << "229869 207047 149641 10454 95701 288207 146452\n" << "239114 169645 175419 81391 202387 17323 137473\n" << "10822 132713 278732 67953 270697 192027 145037\n" << "287787 72619 91519 149380 166585 195573\n" << "170321 153269 15221 281933 253449 60397\n" << "280800 106654 206779 102566 90347 90040\n" << "16209 50044 13143 258643 266708 293108\n" << "167797 67699 82362 195301 220330 168599\n" << "96297 228847 134210 32665 179652 28895\n" << "90604 173947 62213 230369 268434 101748\n"; return; } if(n==8){ cout << "81193 155056 294105 56038 226192 100494 295344 275801\n" << "87530 22686 126266 208520 284492 85362 59156 18302\n" << "37965 210243 296997 163629 23260 120151 126318 41596\n" << "270027 269665 208323 243199 141925 4555 134480 243925\n" << "55360 44208 27596 94425 237479 131323 147206 127524\n" << "4003 188369 185864 127852 289452 178920 114346 141741\n" << "139530 103648 171694 128247 221626 125531 50415 264421\n" << "171721 223255 251473 101818 15957 145725 93669\n" << "209923 129500 291204 243394 63692 152064 70000\n" << "716 130719 41059 203924 186852 157793 194111\n" << "178682 82294 7526 292031 233363 103835 283375\n" << "77216 297778 204705 104255 288681 258694 150091\n" << "201970 21221 185040 132796 198315 20925 130056\n" << "45551 56160 156792 129187 149519 164754 221330\n" << "132457 210356 223274 294877 121376 45865 152067\n"; return; } if(n==9){ cout << "76806 244105 296744 124333 155191 21073 183046 80606 63635\n" << "70258 264777 213679 195315 206746 190242 267325 122024 294118\n" << "17093 76069 294254 268706 143708 12580 9093 159716 23757\n" << "137781 281966 3753 25556 32805 24498 293435 225423 44680\n" << "284352 291948 259871 275463 282316 85287 57357 121830 44342\n" << "173692 175742 188091 140629 217109 33257 72355 105139 86343\n" << "173560 54594 247022 273442 39761 281439 15901 227973 106377\n" << "284424 86836 37328 48732 242154 257408 58846 196194 196437\n" << "88993 297305 156685 166744 23407 100953 65495 191408\n" << "101443 172984 170118 50277 72326 289919 271969 62073\n" << "218269 52916 43749 1493 107274 121392 216743 178867\n" << "200990 259547 74963 242093 63012 267784 210490 97519\n" << "250648 8435 20905 299065 177902 93394 219384 52156\n" << "132841 196978 297575 237066 140108 78885 24983 138848\n" << "234929 51489 280932 224138 164615 141043 93785 136676\n" << "39717 222265 218739 73318 31313 202219 231766 175783\n" << "175801 156735 133097 12663 116331 18840 22718 272714\n"; return; } if(n==10){ cout << "22798 21752 211490 21666 96789 164853 166994 79004 248566 191463\n" << "143033 182159 293683 58634 139100 217014 50471 261380 76394 199419\n" << "21300 1472 283226 242575 225212 184604 140027 175261 219794 165308\n" << "178498 147409 292620 55946 172459 180638 299357 85070 115491 204792\n" << "63544 5525 152860 162865 294324 108156 120938 257734 89529 214583\n" << "113298 190919 148359 182883 213884 281839 111574 191216 43596 223514\n" << "293356 43255 293281 281646 8198 183573 246373 248901 19664 125970\n" << "243460 279406 83107 88972 68696 227927 154527 48622 288553 110708\n" << "194286 127788 206661 151200 164891 285546 283679 135629 252947 235188\n" << "237014 275098 164396 53616 160301 71696 175476 268726 157466\n" << "8458 203004 265164 37823 167740 118175 167301 186501 34092\n" << "80814 194194 277906 296746 76323 296129 255360 131143 138737\n" << "75629 169234 283505 127315 270967 164528 164930 37028 49056\n" << "98140 34535 252979 86243 205630 162509 294659 66109 56882\n" << "91382 16796 128624 118228 53242 256157 154357 235159 234848\n" << "51204 30429 55549 164424 116740 159528 163409 33416 225368\n" << "54126 156055 139141 3498 209850 174288 195754 243366 209555\n" << "113949 245538 27219 132544 206583 6710 167921 161748 117657\n" << "189806 173302 189707 183192 264193 251033 202618 244487 33864\n"; return; } while(1){ rep(i,n)rep(j,n-1){ r[i][j]=rnd(300000)+1; c[j][i]=rnd(300000)+1; } bool ok=1; set st; st.clear(); rep(si,n)rep(sj,n){ if(!ok)break; priority_queue,vector>,greater>> pq; pq.push({0,si,sj}); vector dist(n,vl(n,inf)); dist[si][sj]=0; while(!pq.empty()){ auto [d,x,y]=pq.top(); pq.pop(); if(dist[x][y]!=d)continue; if(x!=n-1 && chmin(dist[x+1][y],d+c[x][y]))pq.push({dist[x+1][y],x+1,y}); if(x!=0 && chmin(dist[x-1][y],d+c[x-1][y]))pq.push({dist[x-1][y],x-1,y}); if(y!=n-1 && chmin(dist[x][y+1],d+r[x][y]))pq.push({dist[x][y+1],x,y+1}); if(y!=0 && chmin(dist[x][y-1],d+r[x][y-1]))pq.push({dist[x][y-1],x,y-1}); } rep(i,n)rep(j,n){ if(i!=si || j!=sj){ st.insert(dist[i][j]); } } } if(st.size()==(n*n*(n*n-1))/2)break; iter++; if(iter%100==0)cout << iter << endl; } rep(i,n-1){ cout << "\""; rep(j,n)cout <> t; while (t--){ solve(); } }