import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    private static final double timeLimitSecond = 1.8;
    private static final int[] dr = { -1, 0, 0, 1, };
    private static final int[] dc = { 0, -1, 1, 0, };
    private static int N;
    private static int T;
    private static int[][] A;
    private static PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());
    private static Watch2 watch;
    private static Path solution;
    private static Path bestSolution;
    private static Params params;
    private static Point[][] P;

    public static void main(String[] args) {
        try {
            read();
            init();
            solve();
            write();
            Utils.debug("score", bestScore, "time", watch.toString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void read() {
        try (Scanner in = new Scanner(System.in)) {
            N = in.nextInt();
            watch = new Watch2();
            T = in.nextInt();
            System.err.println("[DATA] N = " + N);
            System.err.println("[DATA] T = " + T);
            System.err.flush();
            A = new int[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    A[r][c] = in.nextInt();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void init() {
        params = Params.fromProps();
        P = new Point[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                P[r][c] = new Point(r, c);
            }
        }
        solution = new Path(new ArrayList<>(), new boolean[N][N], 0);
        bestScore = 0;
        bestSolution = new Path(new ArrayList<>(), new boolean[N][N], 0);
    }

    private static void write() {
        StringBuilder sb = new StringBuilder();
        sb.append(bestSolution.size()).append("\n");
        for (int i = 0; i < bestSolution.size(); i++) {
            Point p = bestSolution.get(i);
            sb.append(p.r).append(" ").append(p.c).append("\n");
        }
        System.out.println(sb.toString().trim());
        System.out.flush();
    }

    private static void solve() {
        greedy();
        multiSA();
    }

    private static void greedy() {
        ArrayList<Point> current = new ArrayList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                solution.clear();
                Point p = P[r][c];
                current.clear();
                current.add(p);
                ArrayList<Point> newPath = solution.dfs(Math.min(T, params.depth), p, null, current);
                if (newPath.isEmpty()) {
                    continue;
                }
                for (int i = 0; i < newPath.size(); i++) {
                    solution.add(newPath.get(i));
                }
                newPath.clear();
                score = solution.score();
                saveBest();
            }
        }
        loadBest();
        Utils.debug("greedy", "score", score, "time", watch.elapsedSecond());
    }

    private static double temperature;
    private static double score;
    private static double bestScore;
    private static int[] countAC = new int[30];
    private static long iterations = 0;
    private static long validIterations = 0;
    private static long acIterations = 0;

    private static void multiSA() {
        int numRestart = params.numRestart;
        double startTime = watch.elapsedSecond();
        double endTime = timeLimitSecond;
        double remainTime = endTime - startTime;
        double startStartTemperature = params.startTemp;
        double endStartTemperature = params.endTemp;
        for (double restart = 0; restart < numRestart; restart++) {
            double startTime2 = startTime + remainTime * restart / numRestart;
            double endTime2 = startTime + remainTime * (restart + 1) / numRestart;
            double startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);
            double endTemperature = params.endTemp;
            SA(startTime2, endTime2, startTemperature, endTemperature);
            loadBest();
        }
        Utils.debug("multiSA", "score", score, "time", watch.elapsedSecond());
    }

    private static void SA(double startTime, double endTime, double startTemperature, double endTemperature) {
        temperature = startTemperature;
        while (true) {
            iterations++;
            if ((iterations & ((1 << 5) - 1)) == 0) {
                final double timeRatio01 = (watch.elapsedSecond() - startTime) / (endTime - startTime);
                temperature = startTemperature + (endTemperature - startTemperature) * timeRatio01;
                if (timeRatio01 >= 1.0) {
                    Utils.debug("iters", iterations, "valid", String.format("%.2f%%", validIterations * 100.0 / iterations), "ac", String.format("%.2f%%", acIterations * 100.0 / iterations), "score", score, "best", bestScore, "T", String.format("%.3f", temperature), "time", String.format("%.2f", watch.elapsedSecond()), "st", startTime, "et", endTime, "sTemp", startTemperature, "eTemp", endTemperature, "countAC", countAC);
                    break;
                }
            }
            if (solution.size() == 0) {
                loadBest();
            }
            mutate();
        }
    }

    private static void mutate() {
        double random = (params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3 + params.mutate4 + params.mutate5 + params.mutate6) * rng.nextDouble();
        if (random < params.mutate0) {
            removeAndAdd();
        } else if (random < params.mutate0 + params.mutate1) {
            trim();
        } else if (random < params.mutate0 + params.mutate1 + params.mutate2) {
            removeAndAddFirst();
        } else if (random < params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3) {
            move1();
        } else if (random < params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3 + params.mutate4) {
            corner();
        } else if (random < params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3 + params.mutate4 + params.mutate5) {
            center2end();
        } else if (random < params.mutate0 + params.mutate1 + params.mutate2 + params.mutate3 + params.mutate4 + params.mutate5 + params.mutate6) {
            end2center();
        }
    }

    private static ArrayList<Point> removes = new ArrayList<>();
    private static final int[] indexes = new int[] { 0, 1, 2, 3, };

    private static void move1() {
        final boolean reverse = rng.nextInt(2) == 0;
        if (reverse) {
            final Point tail = solution.get(0);
            int d = -1;
            for (int d2 = 0; d2 < dr.length; d2++) {
                int d3 = d2 + rng.nextInt(dr.length - d2);
                swap(indexes, d2, d3);
                int nr = tail.r + dr[indexes[d2]];
                int nc = tail.c + dc[indexes[d2]];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                    continue;
                }
                if (solution.used[nr][nc]) {
                    int index = solution.points.indexOf(P[nr][nc]);
                    if (index - 1 == 0) {
                        continue;
                    }
                    for (int l = 0, r = index - 1; l < r; l++, r--) {
                        Collections.swap(solution.points, l, r);
                    }
                    return;
                }
                d = d2;
                break;
            }
            int nr = tail.r + dr[indexes[d]];
            int nc = tail.c + dc[indexes[d]];
            double deltaScore = A[nr][nc];
            if (solution.size() == T) {
                final Point head = solution.get(solution.size() - 1);
                deltaScore -= A[head.r][head.c];
            }
            if (accept(deltaScore)) {
                score += deltaScore;
                if (solution.size() == T) {
                    solution.remove(solution.size() - 1);
                }
                solution.reverse();
                solution.add(P[nr][nc]);
                saveBest();
                countAC[3]++;
            }
        } else {
            final Point tail = solution.get(solution.size() - 1);
            int d = -1;
            for (int d2 = 0; d2 < dr.length; d2++) {
                int d3 = d2 + rng.nextInt(dr.length - d2);
                swap(indexes, d2, d3);
                int nr = tail.r + dr[indexes[d2]];
                int nc = tail.c + dc[indexes[d2]];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                    continue;
                }
                if (solution.used[nr][nc]) {
                    int index = solution.points.lastIndexOf(P[nr][nc]);
                    if (index + 1 == solution.size() - 1) {
                        continue;
                    }
                    for (int l = index + 1, r = solution.size() - 1; l < r; l++, r--) {
                        Collections.swap(solution.points, l, r);
                    }
                    return;
                }
                d = d2;
                break;
            }
            int nr = tail.r + dr[indexes[d]];
            int nc = tail.c + dc[indexes[d]];
            double deltaScore = A[nr][nc];
            if (solution.size() == T) {
                Point head = solution.get(0);
                deltaScore -= A[head.r][head.c];
            }
            if (accept(deltaScore)) {
                score += deltaScore;
                if (solution.size() == T) {
                    solution.remove(0);
                }
                solution.add(P[nr][nc]);
                saveBest();
                countAC[3]++;
            }
        }
    }

    private static void corner() {
        if (solution.size() <= 2) {
            return;
        }
        final int index = rng.nextInt(solution.size() - 2);
        final Point p0 = solution.get(index);
        final Point p1 = solution.get(index + 1);
        final Point p2 = solution.get(index + 2);
        if (p0.r == p2.r || p0.c == p2.c) {
            return;
        }
        final int dr = p2.r - p1.r;
        final int dc = p2.c - p1.c;
        final int nr = p0.r + dr;
        final int nc = p0.c + dc;
        if (solution.used[nr][nc]) {
            return;
        }
        double deltaScore = A[nr][nc] - A[p1.r][p1.c];
        if (accept(deltaScore)) {
            score += deltaScore;
            solution.set(index + 1, P[nr][nc]);
            saveBest();
            countAC[4]++;
        }
    }

    private static void center2end() {
        if (solution.size() <= 3) {
            return;
        }
        final int index = rng.nextInt(solution.size() - 3);
        final Point p0 = solution.get(index);
        final Point p1 = solution.get(index + 1);
        final Point p2 = solution.get(index + 2);
        final Point p3 = solution.get(index + 3);
        if (!isAdjacent(p0, p3)) {
            return;
        }
        final double random = 3 * rng.nextDouble();
        if (random < 1) {
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            for (int d = 0; d < dr.length; d++) {
                int nr = solution.get(0).r + dr[d];
                int nc = solution.get(0).c + dc[d];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N) || solution.used[nr][nc]) {
                    continue;
                }
                for (int d2 = 0; d2 < dr.length; d2++) {
                    int nr2 = nr + dr[d2];
                    int nc2 = nc + dc[d2];
                    if (!Utils.isValid(nr2, 0, N) || !Utils.isValid(nc2, 0, N) || solution.used[nr2][nc2]) {
                        continue;
                    }
                    int sumA = A[nr][nc] + A[nr2][nc2];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = nc;
                        bestNr2 = nr2;
                        bestNc2 = nc2;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[p1.r][p1.c] + A[p2.r][p2.c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.remove(index + 2);
                solution.remove(index + 1);
                solution.add(0, P[bestNr][bestNc]);
                solution.add(0, P[bestNr2][bestNc2]);
                saveBest();
                countAC[5]++;
            }
        } else if (random < 2) {
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            for (int d = 0; d < dr.length; d++) {
                int nr = solution.get(solution.size() - 1).r + dr[d];
                int nc = solution.get(solution.size() - 1).c + dc[d];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N) || solution.used[nr][nc]) {
                    continue;
                }
                for (int d2 = 0; d2 < dr.length; d2++) {
                    int nr2 = nr + dr[d2];
                    int nc2 = nc + dc[d2];
                    if (!Utils.isValid(nr2, 0, N) || !Utils.isValid(nc2, 0, N) || solution.used[nr2][nc2]) {
                        continue;
                    }
                    int sumA = A[nr][nc] + A[nr2][nc2];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = nc;
                        bestNr2 = nr2;
                        bestNc2 = nc2;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[p1.r][p1.c] + A[p2.r][p2.c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.remove(index + 2);
                solution.remove(index + 1);
                solution.add(P[bestNr][bestNc]);
                solution.add(P[bestNr2][bestNc2]);
                saveBest();
                countAC[5]++;
            }
        } else if (random < 3) {
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            for (int d = 0; d < dr.length; d++) {
                int nr = solution.get(0).r + dr[d];
                int nc = solution.get(0).c + dc[d];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N) || solution.used[nr][nc]) {
                    continue;
                }
                for (int d2 = 0; d2 < dr.length; d2++) {
                    int nr2 = solution.get(solution.size() - 1).r + dr[d2];
                    int nc2 = solution.get(solution.size() - 1).c + dc[d2];
                    if ((nr2 == nr && nc2 == nc) || !Utils.isValid(nr2, 0, N) || !Utils.isValid(nc2, 0, N) || solution.used[nr2][nc2]) {
                        continue;
                    }
                    int sumA = A[nr][nc] + A[nr2][nc2];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = nc;
                        bestNr2 = nr2;
                        bestNc2 = nc2;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[p1.r][p1.c] + A[p2.r][p2.c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.remove(index + 2);
                solution.remove(index + 1);
                solution.add(0, P[bestNr][bestNc]);
                solution.add(P[bestNr2][bestNc2]);
                saveBest();
                countAC[5]++;
            }
        }
    }

    private static int[] ds = { -1, 1, };

    private static void end2center() {
        if (solution.size() <= 3) {
            return;
        }
        final double random = 3 * rng.nextDouble();
        if (random < 1) {
            final int index = 2 + rng.nextInt(solution.size() - 3);
            final Point p0 = solution.get(index);
            final Point p3 = solution.get(index + 1);
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            if (p0.r == p3.r) {
                for (int d : ds) {
                    int nr = p0.r + d;
                    if (!Utils.isValid(nr, 0, N) || solution.used[nr][p0.c] || solution.used[nr][p3.c]) {
                        continue;
                    }
                    int sumA = A[nr][p0.c] + A[nr][p3.c];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = p0.c;
                        bestNr2 = nr;
                        bestNc2 = p3.c;
                    }
                }
            } else {
                for (int d : ds) {
                    int nc = p0.c + d;
                    if (!Utils.isValid(nc, 0, N) || solution.used[p0.r][nc] || solution.used[p3.r][nc]) {
                        continue;
                    }
                    int sumA = A[p0.r][nc] + A[p3.r][nc];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = p0.r;
                        bestNc = nc;
                        bestNr2 = p3.r;
                        bestNc2 = nc;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[solution.get(0).r][solution.get(0).c] + A[solution.get(1).r][solution.get(1).c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.add(index + 1, P[bestNr][bestNc]);
                solution.add(index + 2, P[bestNr2][bestNc2]);
                solution.remove(0);
                solution.remove(0);
                saveBest();
                countAC[6]++;
            }
        } else if (random < 2) {
            final int index = rng.nextInt(solution.size() - 3);
            final Point p0 = solution.get(index);
            final Point p3 = solution.get(index + 1);
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            if (p0.r == p3.r) {
                for (int d : ds) {
                    int nr = p0.r + d;
                    if (!Utils.isValid(nr, 0, N) || solution.used[nr][p0.c] || solution.used[nr][p3.c]) {
                        continue;
                    }
                    int sumA = A[nr][p0.c] + A[nr][p3.c];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = p0.c;
                        bestNr2 = nr;
                        bestNc2 = p3.c;
                    }
                }
            } else {
                for (int d : ds) {
                    int nc = p0.c + d;
                    if (!Utils.isValid(nc, 0, N) || solution.used[p0.r][nc] || solution.used[p3.r][nc]) {
                        continue;
                    }
                    int sumA = A[p0.r][nc] + A[p3.r][nc];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = p0.r;
                        bestNc = nc;
                        bestNr2 = p3.r;
                        bestNc2 = nc;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[solution.get(solution.size() - 2).r][solution.get(solution.size() - 2).c] + A[solution.get(solution.size() - 1).r][solution.get(solution.size() - 1).c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.add(index + 1, P[bestNr][bestNc]);
                solution.add(index + 2, P[bestNr2][bestNc2]);
                solution.remove(solution.size() - 1);
                solution.remove(solution.size() - 1);
                saveBest();
                countAC[6]++;
            }
        } else if (random < 3) {
            final int index = 1 + rng.nextInt(solution.size() - 3);
            final Point p0 = solution.get(index);
            final Point p3 = solution.get(index + 1);
            int best = (int) -1e9;
            int bestNr = -1;
            int bestNc = -1;
            int bestNr2 = -1;
            int bestNc2 = -1;
            if (p0.r == p3.r) {
                for (int d : ds) {
                    int nr = p0.r + d;
                    if (!Utils.isValid(nr, 0, N) || solution.used[nr][p0.c] || solution.used[nr][p3.c]) {
                        continue;
                    }
                    int sumA = A[nr][p0.c] + A[nr][p3.c];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = nr;
                        bestNc = p0.c;
                        bestNr2 = nr;
                        bestNc2 = p3.c;
                    }
                }
            } else {
                for (int d : ds) {
                    int nc = p0.c + d;
                    if (!Utils.isValid(nc, 0, N) || solution.used[p0.r][nc] || solution.used[p3.r][nc]) {
                        continue;
                    }
                    int sumA = A[p0.r][nc] + A[p3.r][nc];
                    if (sumA > best) {
                        best = sumA;
                        bestNr = p0.r;
                        bestNc = nc;
                        bestNr2 = p3.r;
                        bestNc2 = nc;
                    }
                }
            }
            if (best < 0) {
                return;
            }
            double deltaScore = best - (A[solution.get(0).r][solution.get(0).c] + A[solution.get(solution.size() - 1).r][solution.get(solution.size() - 1).c]);
            if (accept(deltaScore)) {
                score += deltaScore;
                solution.add(index + 1, P[bestNr][bestNc]);
                solution.add(index + 2, P[bestNr2][bestNc2]);
                solution.remove(0);
                solution.remove(solution.size() - 1);
                saveBest();
                countAC[6]++;
            }
        }
    }

    private static void trim() {
        final int threshold = params.initA + rng.nextInt(params.randomA);
        for (int i = solution.size() - 1; i >= 0; i--) {
            Point p = solution.get(i);
            if (A[p.r][p.c] >= threshold) {
                break;
            }
            solution.remove(i);
            removes.add(p);
        }
        int size = removes.size();
        solution.reverse();
        for (int i = solution.size() - 1; i >= 0; i--) {
            Point p = solution.get(i);
            if (A[p.r][p.c] >= threshold) {
                break;
            }
            solution.remove(i);
            removes.add(p);
        }
        double deltaScore = solution.score() - score;
        if (accept(deltaScore)) {
            score += deltaScore;
            saveBest();
            removes.clear();
            countAC[1]++;
        } else {
            while (removes.size() > size) {
                Point p = removes.remove(removes.size() - 1);
                solution.add(p);
            }
            solution.reverse();
            while (removes.size() > 0) {
                Point p = removes.remove(removes.size() - 1);
                solution.add(p);
            }
        }
    }

    private static void removeAndAdd() {
        if (solution.size() == 0) {
            return;
        }
        final int index = rng.nextInt(Math.max(1, solution.size() - params.initSize - rng.nextInt(params.randomSize)));
        final int length = params.initLength + rng.nextInt(params.randomLength);
        if (index + length >= solution.size()) {
            solution.reverse();
        }
        Point last = null;
        for (int i = 0; i < length; i++) {
            if (index >= solution.size()) {
                last = null;
                break;
            }
            Point p = solution.remove(index);
            removes.add(p);
            last = p;
        }
        final int length2 = Math.min(T - solution.size(), length + rng.nextInt(params.randomLength2));
        ArrayList<Point> newPath = solution.dfs(length2, removes.get(0), last, removes);
        if (newPath.isEmpty()) {
            assert newPath.size() == 0;
            for (int i = removes.size() - 1; i >= 0; i--) {
                Point p = removes.remove(i);
                solution.add(index, p);
            }
            return;
        }
        for (int i = 0; i < newPath.size(); i++) {
            Point p = newPath.get(i);
            solution.add(index + i, p);
        }
        double deltaScore = solution.score() - score;
        if (accept(deltaScore)) {
            score += deltaScore;
            saveBest();
            removes.clear();
            newPath.clear();
            countAC[0]++;
        } else {
            for (int i = newPath.size() - 1; i >= 0; i--) {
                newPath.remove(i);
                solution.remove(index);
            }
            for (int i = removes.size() - 1; i >= 0; i--) {
                Point p = removes.remove(i);
                solution.add(index, p);
            }
        }
    }

    private static void removeAndAddFirst() {
        if (solution.size() == 0) {
            return;
        }
        final int index = rng.nextInt(Math.max(1, solution.size() - params.initSize - rng.nextInt(params.randomSize)));
        final int length = params.initLength + rng.nextInt(params.randomLength);
        if (index + length >= solution.size()) {
            solution.reverse();
        }
        Point last = null;
        for (int i = 0; i < length; i++) {
            if (index >= solution.size()) {
                last = null;
                break;
            }
            Point p = solution.remove(index);
            removes.add(p);
            last = p;
        }
        final int length2 = Math.min(T - solution.size(), length + rng.nextInt(params.randomLength2));
        ArrayList<Point> newPath = solution.dfsFirst(length2, removes.get(0), last, removes);
        if (newPath.isEmpty()) {
            assert newPath.size() == 0;
            for (int i = removes.size() - 1; i >= 0; i--) {
                Point p = removes.remove(i);
                solution.add(index, p);
            }
            return;
        }
        for (int i = 0; i < newPath.size(); i++) {
            Point p = newPath.get(i);
            solution.add(index + i, p);
        }
        double deltaScore = solution.score() - score;
        if (accept(deltaScore)) {
            score += deltaScore;
            saveBest();
            removes.clear();
            newPath.clear();
            countAC[2]++;
        } else {
            for (int i = newPath.size() - 1; i >= 0; i--) {
                newPath.remove(i);
                solution.remove(index);
            }
            for (int i = removes.size() - 1; i >= 0; i--) {
                Point p = removes.remove(i);
                solution.add(index, p);
            }
        }
    }

    private static void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            bestSolution.clear();
            bestSolution.addAll(solution);
        }
    }

    private static void loadBest() {
        score = bestScore;
        solution.clear();
        solution.addAll(bestSolution);
    }

    private static boolean accept(double delta) {
        validIterations++;
        if (delta >= 0) {
            acIterations++;
            return true;
        }
        double deltaPerTemperature = delta / temperature;
        if (deltaPerTemperature < -10.0) {
            return false;
        }
        boolean ac = rng.nextDouble() < Math.exp(deltaPerTemperature);
        if (ac) {
            acIterations++;
        }
        return ac;
    }

    static class Params {
        double mutate0 = 1.0;
        double mutate1 = 19.93662895407674;
        double mutate2 = 0.005790438016769785;
        double mutate3 = 605.2598604202931;
        double mutate4 = 0.21403038171472305;
        double mutate5 = 209.86405100025604;
        double mutate6 = 122.31710998486543;
        double startTemp = 243.65609756196233;
        double endTemp = 0.010676786349606823;
        int depth = 7;
        int numRestart = 11;
        int initA = 2;
        int randomA = 491;
        int initSize = 3;
        int randomSize = 1;
        int initLength = 5;
        int randomLength = 5;
        int randomLength2 = 2;

        static Params fromProps() {
            Params p = new Params();
            p.mutate0 = getD("mutate0", p.mutate0);
            p.mutate1 = getD("mutate1", p.mutate1);
            p.mutate2 = getD("mutate2", p.mutate2);
            p.mutate3 = getD("mutate3", p.mutate3);
            p.mutate4 = getD("mutate4", p.mutate4);
            p.mutate5 = getD("mutate5", p.mutate5);
            p.mutate6 = getD("mutate6", p.mutate6);
            p.startTemp = getD("startTemp", p.startTemp);
            p.endTemp = getD("endTemp", p.endTemp);
            p.depth = getI("depth", p.depth);
            p.numRestart = getI("numRestart", p.numRestart);
            p.initA = getI("initA", p.initA);
            p.randomA = getI("randomA", p.randomA);
            p.initSize = getI("initSize", p.initSize);
            p.randomSize = getI("randomSize", p.randomSize);
            p.initLength = getI("initLength", p.initLength);
            p.randomLength = getI("randomLength", p.randomLength);
            p.randomLength2 = getI("randomLength2", p.randomLength2);
            return p;
        }

        static double getD(String k, double def) {
            String s = System.getProperty(k);
            if (s == null)
                return def;
            try {
                return Double.parseDouble(s);
            } catch (Exception e) {
                return def;
            }
        }

        static int getI(String k, int def) {
            String s = System.getProperty(k);
            if (s == null)
                return def;
            try {
                return Integer.parseInt(s);
            } catch (Exception e) {
                return def;
            }
        }
    }

    static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public boolean equals(Point other) {
            if (other == null)
                return false;
            return c == other.c && r == other.r;
        }

        @Override
        public String toString() {
            return "(" + r + "," + c + ")";
        }
    }

    static class Path {
        ArrayList<Point> points;
        boolean[][] used;
        int score;

        public Path(ArrayList<Point> points, boolean[][] used, int score) {
            this.points = points;
            this.used = used;
            this.score = score;
        }

        public void set(int index, Point newP) {
            Point p = points.get(index);
            assert used[p.r][p.c];
            used[p.r][p.c] = false;
            score -= A[p.r][p.c];
            points.set(index, newP);
            assert !used[newP.r][newP.c];
            used[newP.r][newP.c] = true;
            score += A[newP.r][newP.c];
        }

        public void reverse() {
            Collections.reverse(points);
        }

        public double score() {
            return score;
        }

        public Point get(int i) {
            return points.get(i);
        }

        public int size() {
            return points.size();
        }

        public void add(int index, Point p) {
            points.add(index, p);
            assert !used[p.r][p.c];
            used[p.r][p.c] = true;
            score += A[p.r][p.c];
        }

        public void add(Point p) {
            add(points.size(), p);
        }

        public Point remove(int index) {
            Point p = points.remove(index);
            assert used[p.r][p.c];
            used[p.r][p.c] = false;
            score -= A[p.r][p.c];
            return p;
        }

        public void clear() {
            for (int i = size() - 1; i >= 0; i--) {
                remove(i);
            }
        }

        public void addAll(Path other) {
            for (int i = 0; i < other.size(); i++) {
                add(other.get(i));
            }
        }

        private int bestScoreDfs;
        private ArrayList<Point> bestScoreDfsSolution = new ArrayList<>();
        private ArrayList<Point> temp = new ArrayList<>();

        private ArrayList<Point> dfs(int length, Point start, Point end, ArrayList<Point> current) {
            bestScoreDfs = 0;
            assert bestScoreDfsSolution.isEmpty() : Utils.toString("bestScoreDfsSolution", bestScoreDfsSolution);
            assert temp.isEmpty() : Utils.toString("temp", temp);
            temp.add(start);
            assert !used[start.r][start.c];
            used[start.r][start.c] = true;
            dfs(temp, 0, length, end, 0, current);
            temp.remove(temp.size() - 1);
            assert temp.isEmpty() : Utils.toString("temp", temp);
            assert used[start.r][start.c];
            used[start.r][start.c] = false;
            return bestScoreDfsSolution;
        }

        private void dfs(ArrayList<Point> temp, int i, int length, Point end, int scoreDfs, ArrayList<Point> current) {
            if (i >= length) {
                return;
            }
            Point last = temp.get(temp.size() - 1);
            if (end != null) {
                if (i + Math.abs(last.r - end.r) + Math.abs(last.c - end.c) >= length) {
                    return;
                }
            }
            if (end == null || last.equals(end)) {
                if (!equals(temp, current)) {
                    if (scoreDfs > bestScoreDfs) {
                        bestScoreDfs = scoreDfs;
                        bestScoreDfsSolution.clear();
                        for (int j = 0; j < temp.size(); j++) {
                            bestScoreDfsSolution.add(temp.get(j));
                        }
                    }
                }
                if (last.equals(end)) {
                    return;
                }
            }
            for (int d = 0; d < dr.length; d++) {
                int nr = temp.get(i).r + dr[d];
                int nc = temp.get(i).c + dc[d];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                    continue;
                }
                if (used[nr][nc]) {
                    continue;
                }
                used[nr][nc] = true;
                temp.add(P[nr][nc]);
                dfs(temp, i + 1, length, end, scoreDfs + A[nr][nc], current);
                used[nr][nc] = false;
                temp.remove(temp.size() - 1);
            }
        }

        private ArrayList<Point> dfsFirst(int length, Point start, Point end, ArrayList<Point> current) {
            bestScoreDfs = 0;
            assert bestScoreDfsSolution.isEmpty() : Utils.toString("bestScoreDfsSolution", bestScoreDfsSolution);
            assert temp.isEmpty() : Utils.toString("temp", temp);
            temp.add(start);
            assert !used[start.r][start.c];
            used[start.r][start.c] = true;
            dfsFirst(temp, 0, length, end, 0, current);
            temp.remove(temp.size() - 1);
            assert temp.isEmpty() : Utils.toString("temp", temp);
            assert used[start.r][start.c];
            used[start.r][start.c] = false;
            return bestScoreDfsSolution;
        }

        private void dfsFirst(ArrayList<Point> temp, int i, int length, Point end, int scoreDfs, ArrayList<Point> current) {
            if (bestScoreDfs != 0) {
                return;
            }
            if (i >= length) {
                return;
            }
            Point last = temp.get(temp.size() - 1);
            if (end != null) {
                if (i + Math.abs(last.r - end.r) + Math.abs(last.c - end.c) >= length) {
                    return;
                }
            }
            if (end == null || last.equals(end)) {
                if (!equals(temp, current)) {
                    if (scoreDfs > bestScoreDfs) {
                        bestScoreDfs = scoreDfs;
                        bestScoreDfsSolution.clear();
                        for (int j = 0; j < temp.size(); j++) {
                            bestScoreDfsSolution.add(temp.get(j));
                        }
                    }
                }
                if (last.equals(end)) {
                    return;
                }
            }
            int[] index = new int[] { 0, 1, 2, 3, };
            shuffle(index);
            for (int d = 0; d < dr.length; d++) {
                int nr = temp.get(i).r + dr[index[d]];
                int nc = temp.get(i).c + dc[index[d]];
                if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                    continue;
                }
                if (used[nr][nc]) {
                    continue;
                }
                used[nr][nc] = true;
                temp.add(P[nr][nc]);
                dfsFirst(temp, i + 1, length, end, scoreDfs + A[nr][nc], current);
                used[nr][nc] = false;
                temp.remove(temp.size() - 1);
            }
        }

        private static boolean equals(ArrayList<Point> l, ArrayList<Point> l2) {
            if (l.size() != l2.size()) {
                return false;
            }
            for (int i = 0; i < l.size(); i++) {
                if (!l.get(i).equals(l2.get(i))) {
                    return false;
                }
            }
            return true;
        }
    }

    private static final void shuffle(int[] a) {
        for (int i = a.length - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            swap(a, i, j);
        }
    }

    private static final void swap(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static boolean isAdjacent(Point p, Point p2) {
        return Math.abs(p.r - p2.r) + Math.abs(p.c - p2.c) == 1;
    }
}

class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
        System.err.flush();
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

    public static boolean isValid(int v, int min, int minUpper) {
        return v >= min && v < minUpper;
    }
}

class PCG_XSH_RR {
    private long state = 5342;

    public PCG_XSH_RR(final long state) {
        this.state = state;
    }

    public int nextInt() {
        final long oldstate = state;
        state = oldstate * 6364136223846793005L + 521L;
        final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);
        final int rotation = (int) (oldstate >>> 59);
        return (xorshift >>> rotation) | (xorshift << (-rotation & 31));
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

    public int nextInt2(int n) {
        final int k = 16;
        final int x = (nextInt() & ((1 << k) - 1));
        return (x * n) >>> k;
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }
}

class Watch2 {
    private final long start;

    public Watch2() {
        start = System.nanoTime();
    }

    public double elapsedSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    @Override
    public String toString() {
        final long elapsedSecond = (long) (1e3 * elapsedSecond());
        return formatElapsedTimeWithUnits(elapsedSecond);
    }

    public static String formatElapsedTimeWithUnits(final long elapsedMillis) {
        final Duration duration = Duration.ofMillis(elapsedMillis);
        final long hours = duration.toHours();
        final long minutes = duration.toMinutesPart();
        final long seconds = duration.toSecondsPart();
        final long millis = duration.toMillisPart();
        final StringBuilder sb = new StringBuilder();
        if (hours > 0) {
            sb.append(hours).append("h");
        }
        if (minutes > 0 || hours > 0) {
            sb.append(minutes).append("m");
        }
        sb.append(seconds);
        if (minutes > 0 || hours > 0) {
        } else {
            sb.append(".").append(String.format("%03d", millis));
        }
        sb.append("s");
        return sb.toString().trim();
    }
}