#include "my_template.hpp"
#include "other/io.hpp"

#include "ds/unionfind/unionfind.hpp"
#include "random/shuffle.hpp"
#include "linalg/matrix_mul.hpp"

/*
置換 P をとって、P^9 = I となるようにとる
A: UP^k の結合
B: P^kV の結合
*/

using ARR = array<int, 9>;
using MAT = array<array<int, 9>, 9>;

void shuffle(ARR& A) {
  FOR(i, 9) {
    int j = RNG(0, i + 1);
    if (i != j) swap(A[i], A[j]);
  }
}

MAT gen_A(ARR U, ARR P, ARR X, ARR W) {
  int N = 9;
  ARR S = U;
  MAT A;
  FOR(k, 9) {
    FOR(i, N) A[i][W[S[i]]] = X[k];
    ARR SS;
    // FOR(i, N) SS[i] = S[P[i]];
    FOR(i, N) SS[i] = P[S[i]];
    swap(S, SS);
  }
  return A;
}

MAT gen_B(ARR V, ARR P, ARR Y, ARR W) {
  int N = 9;
  MAT B;
  ARR T = V;

  FOR(k, 9) {
    FOR(i, N) B[W[i]][T[i]] = Y[k];
    ARR TT;
    FOR(i, N) TT[i] = T[P[i]];
    // FOR(i, N) TT[i] = P[T[i]];
    swap(T, TT);
  }
  return B;
}

MAT gen_C(MAT A, MAT B) {
  int N = 9;
  MAT C = matrix_mul<int, 9>(A, B);
  FOR(i, N) FOR(j, N) C[i][j] %= 9;
  return C;
}

bool check(MAT X) {
  int N = 9;
  int FULL = 511;
  // FOR(i, N) {
  //   int s = 0;
  //   FOR(j, N) s |= 1 << X[i][j];
  //   assert(s == FULL);
  //   if (s != FULL) return 0;
  // }
  // FOR(i, N) {
  //   int s = 0;
  //   FOR(j, N) s |= 1 << X[j][i];
  //   assert(s == FULL);
  //   if (s != FULL) return 0;
  // }
  FOR(i, 3) FOR(j, 3) {
    int s = 0;
    FOR(a, 3) FOR(b, 3) s |= 1 << X[3 * i + a][3 * j + b];
    if (s != FULL) return 0;
  }
  return 1;
}

void solve() {
  int N = 9;
  ARR P;
  FOR(i, N) P[i] = i;
  vc<ARR> perm;
  do {
    UnionFind uf(N);
    FOR(i, N) uf.merge(i, P[i]);
    if (uf.n_comp != 1) continue;
    perm.eb(P);
  } while (next_permutation(all(P)));

  ARR X, Y;
  FOR(i, N) X[i] = i, Y[i] = i;
  ARR U, V;
  FOR(i, N) U[i] = V[i] = i;

  vc<pair<ARR, ARR>> XY;
  while (len(XY) < 10000) {
    shuffle(X);
    shuffle(Y);
    ARR Z{};
    FOR(a, 9) FOR(b, 9) Z[(a + b) % 9] += X[a] * Y[b];
    FOR(i, 9) Z[i] %= 9;
    int s = 0;
    for (auto& z : Z) s |= 1 << z;
    if (s == 511) {
      XY.eb(X, Y);
    }
  }

  int iter = 0;
  ARR W;
  FOR(i, 9) W[i] = i;
  while (1) {
    ++iter;
    auto P = perm[RNG(0, len(perm))];
    auto [X, Y] = XY[RNG(0, len(XY))];
    shuffle(W);
    vc<MAT> as, bs;
    FOR(10000) {
      shuffle(U);
      MAT A = gen_A(U, P, X, W);
      if (check(A)) as.eb(A);
    }
    FOR(10000) {
      shuffle(V);
      MAT B = gen_B(V, P, Y, W);
      if (check(B)) bs.eb(B);
    }
    SHOW(iter, len(as), len(bs));

    for (auto& A : as) {
      for (auto& B : bs) {
        MAT C = gen_C(A, B);
        if (check(C)) {
          FOR(i, N) print(A[i]);
          FOR(i, N) print(B[i]);
          return;
        }
      }
    }
  }
}

signed main() {
  solve();
  return 0;
}