#include <iostream>
                #include <queue>
                #include <vector>
                #include <map>
                #include <time.h>
                
                int cnt = 0;
                int puz_state[1000000][12];
                int p_state[1000000];
                
                
                struct state { int puzzle[12]; int depth; int f_n; int id;
                    bool operator>(const state &s) const {
                        return f_n > s.f_n;
                    }
                };
                
                state start = { {6, 4, 7, 8, 5, 0, 3, 2, 1, 11, 10, 9}, 0, 0, 0};
                state goal = { {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0}, 0, 0, 0};    // evaluation
                std::priority_queue <state, std::vector<state>, std::greater<state> > open;
                std::vector<state> closed;
                
                bool IsFinished(state s){
                    for (int i = 0; i < 11; i++) {
                       if (s.puzzle[i] != goal.puzzle[i]) return false;
                    }
                    return true;
                }
                
                bool IsSamePuzzle(state s1, state s2){
                    for (int i = 0; i < 12; i++) {
                        if (s1.puzzle[i] != s2.puzzle[i]) return false;
                    }
                    return true;
                }
                
                bool InClosed(state s){
                    for (int i = 0; i < closed.size(); i++) {
                        if (IsSamePuzzle(s, closed[i])) return true;
                    }
                    return false;
                }
                
                void print_ans(int n){
                    if(n != 0) print_ans(p_state[n]);
                    for(int i = 0; i < 3; i++){
                        for(int j = 0; j < 4; j++){
                            printf("%d ", puz_state[n][i*3 + j] );
                        }
                        printf("\n");
                    }
                    printf("\n");
                }
                
                void bfs(){
                    state now = open.top();
                    open.pop();
                    closed.push_back(now);
                    if (IsFinished(now)){
                        print_ans(now.id);
                        return;
                    }
                    state s = now;    
                    int zero;
                    for (int i = 0; i < 12; i++) {
                        if (now.puzzle[i] == 0) zero = i;
                    }
                    if (zero - 4 >= 0) {
                        std::swap(s.puzzle[zero - 4], s.puzzle[zero]);
                        if (!InClosed(s)) {
                            cnt++; s.id = cnt;
                            p_state[cnt] = now.id;
                            for(int i = 0; i < 12; i++) puz_state[cnt][i] = s.puzzle[i];
                            s.depth++;
                            s.f_n = s.depth;
                            open.push(s);
                        }
                        s = now;
                    }
                    if (zero % 4 != 0) {
                        std::swap(s.puzzle[zero - 1], s.puzzle[zero]);
                        if (!InClosed(s)) {
                            cnt++; s.id = cnt;
                            p_state[cnt] = now.id;
                            for(int i = 0; i < 12; i++) puz_state[cnt][i] = s.puzzle[i];
                            s.depth++;
                            s.f_n = s.depth;
                            open.push(s);
                        }
                        s = now;
                    }
                    if (zero % 4 != 3) {
                        std::swap(s.puzzle[zero + 1], s.puzzle[zero]);
                        if (!InClosed(s)) {
                            cnt++; s.id = cnt;
                            p_state[cnt] = now.id;
                            for(int i = 0; i < 9; i++) puz_state[cnt][i] = s.puzzle[i];
                            s.depth++;
                            s.f_n = s.depth;
                            open.push(s);
                        }
                        s = now;
                    }
                    if (zero + 4 < 12) {
                        std::swap(s.puzzle[zero + 4], s.puzzle[zero]);
                        if (!InClosed(s)) {
                            cnt++; s.id = cnt;
                            p_state[cnt] = now.id;
                            for(int i = 0; i < 12; i++) puz_state[cnt][i] = s.puzzle[i];
                            s.depth++;
                            s.f_n = s.depth;
                            open.push(s);
                        }
                    }
                    bfs();
                    return;
                }
                
                
                int main(){
                    clock_t s = clock();
                    start.f_n = 0;
                    open.push(start);
                    for(int i = 0; i < 12; i++) puz_state[0][i] = start.puzzle[i];
                    bfs();
                    clock_t e = clock();
                    std::cout << (double)(e-s)/CLOCKS_PER_SEC << std::endl;
                
                    return 0;
                }