#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <map>
#include <time.h>
using namespace std;
const int inf = 1000000000 + 7;
vector<vector<char>> CreateTruePytnaska(string s, const int& n) {
    vector<vector<char>> answer(n, vector<char>(n));
    int count = 0;
    s += "_";
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            answer[i][j] = s[count++];
    return answer;
}
void PrintPytnaska(const vector<vector<char>>& v, const int& n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
        {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
void PrintMinWay(map<vector<vector<char>>, int>& d, const vector<vector<char>>& final, int steps, const int& n){
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    vector<vector<char>> temp = final;
    int Steps = steps;
    vector<vector<vector<char>>> VectorToPrint = {final};
    while(steps > 0) {
        steps--;
        int x = 0, y = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (temp[i][j] == '_') {
                    x = i;
                    y = j;
                }
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= n)
                continue;
            vector<vector<char>> f = temp;
            swap(f[x][y], f[a][b]);
            if(d.count(f) && d[f] == steps)
            {
                temp = f;
                VectorToPrint.push_back(f);
                break;
            }
        }
    }
    reverse(VectorToPrint.begin(),VectorToPrint.end());
    for(const auto& x : VectorToPrint)
        PrintPytnaska(x,n);
    cout << endl << "Done in " << Steps <<" steps" << endl;
}
void bfs(const int& n, const vector<vector<char>>& m, const string& s) {
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    vector<vector<char>> final = CreateTruePytnaska(s, n);
    if (m == final) {
        cout << "Pytnaska already done" << endl;
        return;
    }
    queue <vector<vector<char>>> q;
    map <vector<vector<char>>, int> was;
    map<vector<vector<char>>, int> d;
    d[m] = 0;
    q.push(m);
    was[m] = 1;
    while (!q.empty()) {
        vector<vector<char>> temp = q.front();
        q.pop();
        int x = 0, y = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (temp[i][j] == '_') {
                    x = i;
                    y = j;
                }
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= n)
                continue;
            vector<vector<char>> f = temp;
            swap(f[x][y], f[a][b]);
            if (f == final) {
                //PrintPytnaska(f, n);

                PrintMinWay(d,final,d[temp] + 1,n);
                return;

            }
            if (!was[f])
            {
                q.push(f);
                was[f] = 1;
                d[f] = d[temp] + 1;
                //PrintPytnaska(f, n);
            }

        }

    }
    cout << "Can't be solved" << endl;
}
signed main() {
    int n = 3;
    string s;
    cin >> s;
    vector<vector<char>> m(n, vector<char>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    clock_t start = clock();
    bfs(n, m, s);
    clock_t end = clock();
    double seconds = (double)(end - start) / CLOCKS_PER_SEC;
    cout << "time: " << seconds << endl << endl;
}