private static String solve(int M, int N, char[][] a) {
        int[] S = find(a, M, N, 'S');
        int[] G = find(a, M, N, 'G');
        a[S[0]][S[1]] = a[G[0]][G[1]] = '.';
        
        char[][][] maze = new char[4][M][N];
        
        createMaze(maze, a, M, N, 0); // maze of phase 0
        createMaze(maze, a, M, N, 1); // maze of phase 1
        createMaze(maze, a, M, N, 2); // maze of phase 2
        createMaze(maze, a, M, N, 3); // maze of phase 3
        
        boolean[][][] closedset = new boolean[4][M][N]; // closed set in 4 phases
        int[][][] g_score = new int[4][M][N]; // g_score in 4 phases
        f_score = new int[4][M][N]; // f_score in 4 phases
        
        g_score[0][S[0]][S[1]] = 0;
        f_score[0][S[0]][S[1]] = g_score[0][S[0]][S[1]] + heuristics_score(S[0], S[1], G[0], G[1]);
        
        PrioritySet openset = new PrioritySet(M, N);
        openset.push(new Node(S[0], S[1], 0));
        
        while (!openset.isEmpty()) {
            Node current = openset.poll();
            if (current.i == G[0] && current.j == G[1]) return String.valueOf(current.gscore);
            
            int phase = current.gscore % 4;
            closedset[phase][current.i][current.j] = true; // add current to closedset
            
            phase = (phase + 1) % 4;
            for (Node nb : neighbors(current.i, current.j, maze[phase], M, N)) {
                if (closedset[phase][nb.i][nb.j]) continue; // if neighbor in closedset
                
                nb.gscore = current.gscore + 1;
                if (!openset.contains(nb) || nb.gscore < g_score[nb.gscore % 4][nb.i][nb.j]) {
                    g_score[nb.gscore % 4][nb.i][nb.j] = nb.gscore;
                    f_score[nb.gscore % 4][nb.i][nb.j] = g_score[nb.gscore % 4][nb.i][nb.j] + heuristics_score(nb.i, nb.j, G[0], G[1]);
                    if (!openset.contains(nb))
                        openset.push(nb);
                }
            }
        }
        
        return "impossible";
    }