結果

問題 No.5006 Hidden Maze
ユーザー Yu_212Yu_212
提出日時 2022-06-12 17:18:34
言語 Java19
(openjdk 21)
結果
AC  
実行時間 767 ms / 2,000 ms
コード長 31,193 bytes
コンパイル時間 2,700 ms
実行使用メモリ 64,548 KB
スコア 74,331
平均クエリ数 247.58
最終ジャッジ日時 2022-06-12 17:19:10
合計ジャッジ時間 35,729 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
54,828 KB
testcase_01 AC 233 ms
58,744 KB
testcase_02 AC 178 ms
56,168 KB
testcase_03 AC 128 ms
52,252 KB
testcase_04 AC 167 ms
55,644 KB
testcase_05 AC 696 ms
63,188 KB
testcase_06 AC 232 ms
59,628 KB
testcase_07 AC 723 ms
63,292 KB
testcase_08 AC 177 ms
56,252 KB
testcase_09 AC 180 ms
56,076 KB
testcase_10 AC 160 ms
55,960 KB
testcase_11 AC 139 ms
53,012 KB
testcase_12 AC 150 ms
54,160 KB
testcase_13 AC 188 ms
56,784 KB
testcase_14 AC 159 ms
56,112 KB
testcase_15 AC 163 ms
55,744 KB
testcase_16 AC 154 ms
55,000 KB
testcase_17 AC 172 ms
56,480 KB
testcase_18 AC 258 ms
60,428 KB
testcase_19 AC 95 ms
51,192 KB
testcase_20 AC 139 ms
54,096 KB
testcase_21 AC 106 ms
51,512 KB
testcase_22 AC 163 ms
55,224 KB
testcase_23 AC 192 ms
57,680 KB
testcase_24 AC 256 ms
60,140 KB
testcase_25 AC 140 ms
53,580 KB
testcase_26 AC 676 ms
61,996 KB
testcase_27 AC 744 ms
64,548 KB
testcase_28 AC 102 ms
51,024 KB
testcase_29 AC 704 ms
63,800 KB
testcase_30 AC 138 ms
52,876 KB
testcase_31 AC 139 ms
53,256 KB
testcase_32 AC 186 ms
55,644 KB
testcase_33 AC 157 ms
54,984 KB
testcase_34 AC 185 ms
56,376 KB
testcase_35 AC 163 ms
56,068 KB
testcase_36 AC 178 ms
55,696 KB
testcase_37 AC 669 ms
63,252 KB
testcase_38 AC 767 ms
63,184 KB
testcase_39 AC 144 ms
54,088 KB
testcase_40 AC 157 ms
55,420 KB
testcase_41 AC 166 ms
56,084 KB
testcase_42 AC 177 ms
56,432 KB
testcase_43 AC 161 ms
55,676 KB
testcase_44 AC 117 ms
52,220 KB
testcase_45 AC 683 ms
63,220 KB
testcase_46 AC 669 ms
63,120 KB
testcase_47 AC 169 ms
55,960 KB
testcase_48 AC 141 ms
53,688 KB
testcase_49 AC 700 ms
64,200 KB
testcase_50 AC 148 ms
54,672 KB
testcase_51 AC 150 ms
54,404 KB
testcase_52 AC 172 ms
55,968 KB
testcase_53 AC 284 ms
60,424 KB
testcase_54 AC 154 ms
55,916 KB
testcase_55 AC 174 ms
56,332 KB
testcase_56 AC 168 ms
55,924 KB
testcase_57 AC 620 ms
63,256 KB
testcase_58 AC 169 ms
55,752 KB
testcase_59 AC 157 ms
55,192 KB
testcase_60 AC 136 ms
53,524 KB
testcase_61 AC 167 ms
55,968 KB
testcase_62 AC 199 ms
57,908 KB
testcase_63 AC 167 ms
56,328 KB
testcase_64 AC 395 ms
62,308 KB
testcase_65 AC 156 ms
56,260 KB
testcase_66 AC 137 ms
53,296 KB
testcase_67 AC 189 ms
56,568 KB
testcase_68 AC 716 ms
62,316 KB
testcase_69 AC 165 ms
55,656 KB
testcase_70 AC 103 ms
51,376 KB
testcase_71 AC 127 ms
51,844 KB
testcase_72 AC 154 ms
55,000 KB
testcase_73 AC 403 ms
61,164 KB
testcase_74 AC 624 ms
63,000 KB
testcase_75 AC 174 ms
56,544 KB
testcase_76 AC 204 ms
57,564 KB
testcase_77 AC 676 ms
63,392 KB
testcase_78 AC 151 ms
54,280 KB
testcase_79 AC 697 ms
63,892 KB
testcase_80 AC 138 ms
53,064 KB
testcase_81 AC 176 ms
55,468 KB
testcase_82 AC 148 ms
54,000 KB
testcase_83 AC 141 ms
53,248 KB
testcase_84 AC 169 ms
56,284 KB
testcase_85 AC 215 ms
58,408 KB
testcase_86 AC 131 ms
52,432 KB
testcase_87 AC 233 ms
58,800 KB
testcase_88 AC 755 ms
62,792 KB
testcase_89 AC 625 ms
62,184 KB
testcase_90 AC 169 ms
55,820 KB
testcase_91 AC 156 ms
54,816 KB
testcase_92 AC 246 ms
59,480 KB
testcase_93 AC 151 ms
54,448 KB
testcase_94 AC 665 ms
62,924 KB
testcase_95 AC 176 ms
55,576 KB
testcase_96 AC 162 ms
55,508 KB
testcase_97 AC 177 ms
56,464 KB
testcase_98 AC 736 ms
63,872 KB
testcase_99 AC 686 ms
62,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;

public class Main {
    static In in = new In();
    static Out out = new Out(false);
    static final long inf = 0x1fffffffffffffffL;
    static final int iinf = 0x3fffffff;
    static final double eps = 1e-9;
    static long mod = 998244353;

    boolean isLocal = false;
    double p;
    int n = 20;
    Pos[] instances = new Pos[n * n];
    Pos[][] moved = new Pos[4][n * n];
    String[] roads = new String[n * n];
    double[][] walls = new double[4][n * n];
    void solve() {
        for (int i = 0; i < n * n; i++) {
            instances[i] = new Pos(i % n, i / n, i);
        }
        for (int d = 0; d < 4; d++) {
            for (int i = 0; i < n * n; i++) {
                int nx = i % n + (d - 1) % 2;
                int ny = i / n + (d - 2) % 2;
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    moved[d][i] = instances[ny * n + nx];
                }
            }
        }
        in.nextInt();
        in.nextInt();
        p = in.nextInt() / 100.0;
        w = isLocal ? gen() : null;
        roads[0] = "";
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < n * n; j++) {
                if (pos(j).moved(i) == null) {
                    walls[i][j] = 1;
                } else {
                    walls[i][j] = 0.5;
                }
            }
        }
        if (isLocal) {
            debug(w);
        }
        for (int t = 0; t < 1000; t++) {
//            BitBoard visited = BitBoard.zeros(n);
//            visited.set(0, 0);
            String ask = bfs(t);
//            StringBuilder ask = dfs(pos(0, 0), 0, visited).reverse();
            int ret = ask(ask.toString());
            if (ret == -1) {
                return;
            }
        }
        if (isLocal) {
            debug(w);
        }
    }

    boolean[][] gen() {
        boolean[][] w = new boolean[4][n * n];
        int c = 0;
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        int m = rand.nextInt(100, 200);
        for (int i = 0; i < m; i++) {
            if (rand.nextInt(2) == 0) {
                int ii = rand.nextInt(0, 20);
                int jj = rand.nextInt(0, 19);
                w[2][ii * n + jj] = true;
                w[0][ii * n + jj + 1] = true;
                if (reachable(w) < n * n) {
                    w[2][ii * n + jj] = false;
                    w[0][ii * n + jj + 1] = false;
                }
                c++;
            } else {
                int ii = rand.nextInt(0, 19);
                int jj = rand.nextInt(0, 20);
                w[3][ii * n + jj] = true;
                w[1][(ii + 1) * n + jj] = true;
                if (reachable(w) < n * n) {
                    w[3][ii * n + jj] = false;
                    w[1][(ii + 1) * n + jj] = false;
                }
                c++;
            }
        }
        return w;
    }

    int reachable(boolean[][] w) {
        BitBoard bb = BitBoard.zeros(n);
        Deque<Pos> deque = new ArrayDeque<>();
        deque.addLast(pos(0));
        bb.set(0, 0);
        while (!deque.isEmpty()) {
            Pos v = deque.remove();
            for (int dir = 0; dir < 4; dir++) {
                Pos nei = v.moved(dir);
                if (nei == null || w[dir][v.z] || bb.get(nei.x, nei.y)) {
                    continue;
                }
                bb.set(nei.x, nei.y);
                deque.addLast(nei);
            }
        }
        return bb.countOne();
    }

    int virtual(boolean[][] w, String moves) {
        Pos cur = pos(0, 0);
        for (int i = 0; i < moves.length(); i++) {
            int dir = "LURD".indexOf(moves.charAt(i));
            if (ThreadLocalRandom.current().nextInt(100) <= p) {
                return i;
            }
            if (cur.moved(dir) == null) {
                throw new RuntimeException();
            }
            if (w[dir][cur.z]) {
                return i;
            }
            cur = cur.moved(dir);
        }
        if (cur == pos(n - 1, n - 1)) {
            return -1;
        }
        return moves.length();
    }

    String bfs(int turn) {
        class State implements Comparable<State> {
            final Pos pos;
            final int dist;
            final double prob;

            State(Pos pos, int dist, double prob) {
                this.pos = pos;
                this.dist = dist;
                this.prob = prob;
            }

            @Override
            public int compareTo(State o) {
                if (dist != o.dist) {
                    return Integer.compare(dist, o.dist);
                } else if (prob != o.prob) {
                    return -Double.compare(prob, o.prob);
                } else {
                    return Integer.compare(hashCode(), o.hashCode());
                }
            }

            @Override
            public String toString() {
                return "State{" + "pos=" + pos + ", dist=" + dist + ", prob=" + prob + '}';
            }
        }
        PriorityQueue<State> queue = new PriorityQueue<>();
        int[] prev = new int[n * n];
        State[] s = new State[n * n];
        for (int i = 0; i < n * n; i++) {
            s[i] = new State(pos(i), iinf, 0);
        }
        Arrays.fill(prev, -1);
        s[0] = new State(pos(0), 0, 1);
        queue.add(s[0]);
        Pos best = null;
        while (!queue.isEmpty()) {
            State state = queue.remove();
            Pos cur = state.pos;
            if (s[cur.z].compareTo(state) > 0) {
                continue;
            }
            if (best == null || s[best.z].dist < state.dist || s[best.z].dist == state.dist && s[best.z].prob < state.prob) {
                best = cur;
            }
            for (int dir = 0; dir < 4; dir++) {
                Pos nei = cur.moved(dir);
                if (nei == null) {
                    continue;
                }
                if (walls[dir][cur.z] >= 0.9) {
                    continue;
                }
                double pp = state.prob * (1 - walls[dir][cur.z]);
                State ss = new State(nei, state.dist + 1, pp);
                if (s[nei.z].compareTo(ss) > 0) {
                    s[nei.z] = ss;
                    prev[nei.z] = dir;
                    queue.add(ss);
                }
            }
        }
        if (isLocal) {
            out.debug(s[n * n - 1]);
            StringBuilder bb = new StringBuilder();
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    bb.append(String.format("%1.1f", walls[2][i * n + j])).append("|").append(String.format("%1.1f", walls[3][i * n + j])).append(", ");
//                }
//                bb.append('\n');
//            }
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    bb.append(s[i * n + j].dist).append(", ");
//                }
//                bb.append('\n');
//            }
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    bb.append(String.format("%2.3f", s[i * n + j].prob)).append(", ");
//                }
//                bb.append('\n');
//            }
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    bb.append(prev[i * n + j]).append(", ");
//                }
//                bb.append('\n');
//            }
//            out.debug(bb);
        }
        if (turn >= 10) {
            best = pos(n * n - 1);
        }
        StringBuilder ret = new StringBuilder();
        while (best.z != 0) {
            ret.append("LURD".charAt(prev[best.z]));
            best = best.moved((prev[best.z] + 2) % 4);
        }
        return ret.reverse().toString();
    }

//    StringBuilder dfs(Pos cur, int depth, BitBoard visited) {
//        List<Integer> cand = new ArrayList<>();
//        for (int dir = 0; dir < 4; dir++) {
//            Pos nei = cur.moved(dir);
//            if (nei == null || visited.get(nei.x, nei.y) || walls[dir][cur.z] > 0.9) {
//                continue;
//            }
//            cand.add(dir);
//        }
//        if (cand.isEmpty()) {
//            return new StringBuilder();
//        }
//        cand.sort(Comparator.comparingDouble(i -> walls[i][cur.z]));
//        int dir = cand.get(0);
//        Pos nei = cur.moved(dir);
//        visited.set(nei.x, nei.y);
//        String ret = bfs();
//        visited.clear(nei.x, nei.y);
//        ret.append("LURD".charAt(dir));
//        double prob = (1 - walls[dir][cur.z]) * ret.length();
//        return ret;
//    }

    void debug(boolean[][] w) {
        char[][] c = new char[n][n * 2 - 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(c[i], ' ');
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (w[2][i * n + j]) {
                    c[i][j * 2 + 1] = '|';
                }
                if (w[3][i * n + j]) {
                    c[i][j * 2] = '_';
                }
            }
        }
        for (int i = 0; i < n; i++) {
            out.debug(String.valueOf(c[i]));
        }
    }

    boolean[][] w;
    int ask(String moves) {
        Pos cur = pos(0, 0);
        out.println(moves);
        out.flush();
        int k = isLocal ? virtual(w, moves) : in.nextInt();
        out.debug(k);
        if (k == -1) {
            return -1;
        }
        int len = moves.length();
        for (int i = 0; i <= k && i < len; i++) {
            int dir = "LURD".indexOf(moves.charAt(i));
            if (i == k) {
                out.debug(cur, dir, walls[dir][cur.z], walls[dir][cur.z] / (walls[dir][cur.z] + p));
                walls[dir][cur.z] = walls[dir][cur.z] / (walls[dir][cur.z] + p);
            } else {
                String sub = moves.substring(0, i);
                if (roads[cur.z] == null || roads[cur.z].length() > sub.length()) {
                    roads[cur.z] = sub;
                }
                walls[dir][cur.z] = 0;
            }
            cur = cur.moved(dir);
        }
        return k;
    }

    Pos pos(int x, int y) {
        return instances[y * n + x];
    }

    Pos pos(int z) {
        return instances[z];
    }

    class Pos implements Comparable<Pos> {
        final int x, y, z;

        private Pos(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        Pos moved(int d) {
            return moved[d][z];
        }

        int dist(Pos o) {
            return Math.abs(x - o.x) + Math.abs(y - o.y);
        }

        int euclid(Pos o) {
            return Math.abs(x - o.x) + Math.abs(y - o.y);
        }

        Pos[] neighbors() {
            Pos[] p = new Pos[4];
            int i = 0;
            if ((p[i++] = moved(0)) == null) i--;
            if ((p[i++] = moved(1)) == null) i--;
            if ((p[i++] = moved(2)) == null) i--;
            if ((p[i++] = moved(3)) == null) i--;
            return Arrays.copyOf(p, i);
        }

        @Override
        public int compareTo(Pos o) {
            return Integer.compare(z, o.z);
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pos && z == ((Pos)o).z;
        }

        @Override
        public int hashCode() {
            return z;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    static abstract class BitBoard {
        private static final long[] MASKS = {0, 0x1L, 0x3L, 0x7L, 0xFL, 0x1FL, 0x3FL, 0x7FL, 0xFFL, 0x1FFL, 0x3FFL, 0x7FFL, 0xFFFL, 0x1FFFL, 0x3FFFL, 0x7FFFL, 0xFFFFL, 0x1FFFFL, 0x3FFFFL, 0x7FFFFL, 0xFFFFFL, 0x1FFFFFL, 0x3FFFFFL, 0x7FFFFFL, 0xFFFFFFL, 0x1FFFFFFL, 0x3FFFFFFL, 0x7FFFFFFL, 0xFFFFFFFL, 0x1FFFFFFFL, 0x3FFFFFFFL, 0x7FFFFFFFL, 0xFFFFFFFFL, 0x1FFFFFFFFL, 0x3FFFFFFFFL, 0x7FFFFFFFFL, 0xFFFFFFFFFL, 0x1FFFFFFFFFL, 0x3FFFFFFFFFL, 0x7FFFFFFFFFL, 0xFFFFFFFFFFL, 0x1FFFFFFFFFFL, 0x3FFFFFFFFFFL, 0x7FFFFFFFFFFL, 0xFFFFFFFFFFFL, 0x1FFFFFFFFFFFL, 0x3FFFFFFFFFFFL, 0x7FFFFFFFFFFFL, 0xFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFL, 0x3FFFFFFFFFFFFL, 0x7FFFFFFFFFFFFL, 0xFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFFL};

        private static class BitBoard8 extends BitBoard { // [][][][][][][][] x1
            private final static long[] ONES = {0, 0x1L, 0x101L, 0x10101L, 0x1010101L, 0x101010101L, 0x10101010101L, 0x1010101010101L, 0x101010101010101L};

            private BitBoard8(int size) {
                super(size, new long[1]);
            }

            private BitBoard8(int size, long[] board) {
                super(size, board);
            }

            public BitBoard copy() {
                return new BitBoard8(size, board);
            }

            protected int x(int x, int y) {
                return y << 3 | x;
            }

            protected int y(int x, int y) {
                return 0;
            }

            public long line(int y) {
                return board[0] >>> (y << 3) & 0xFF;
            }

            public int countOne() {
                return Long.bitCount(board[0]);
            }

            public void fillOnes() {
                board[0] = ONES[size] * MASKS[size];
            }

            public void spread() {
                board[0] |= spread(board[0], 8, ONES[size]) & MASKS[size * 8];
            }

            private static BitBoard compress(long[] lines) {
                long board = 0;
                for (long line : lines) {
                    board = board << 8 | line;
                }
                return new BitBoard8(lines.length, new long[] {board});
            }
        }

        private static class BitBoard16 extends BitBoard { // [  ][  ][  ][  ] x4
            private final static long[] ONES = {0x1000100010001L, 0x1L, 0x10001L, 0x100010001L};

            private BitBoard16(int size) {
                super(size, new long[(size + 3) >> 2]);
            }

            private BitBoard16(int size, long[] board) {
                super(size, board);
            }

            public BitBoard copy() {
                return new BitBoard16(size, board);
            }

            protected int x(int x, int y) {
                return (y & 3) << 4 | x;
            }

            protected int y(int x, int y) {
                return y >> 2;
            }

            public long line(int y) {
                return board[y >> 2] >>> ((y & 3) << 4) & 0xFFFF;
            }

            public int countOne() {
                if (board.length == 3) {
                    return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]);
                } else {
                    return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]) + Long.bitCount(board[3]);
                }
            }

            public void fillOnes() {
                board[0] = ONES[0] * MASKS[size];
                board[1] = ONES[0] * MASKS[size];
                if (board.length == 3) {
                    board[2] = ONES[size & 3] * MASKS[size];
                } else {
                    board[2] = ONES[0] * MASKS[size];
                    board[3] = ONES[size & 3] * MASKS[size];
                }
            }

            public void spread() {
                long old0 = board[0];
                long old1 = board[1];
                long old2 = board[2];
                board[0] |= spread(old0, 16, ONES[0]) | old1 << 48;
                board[1] |= spread(old1, 16, ONES[0]) | old2 << 48 | old0 >>> 48;
                if (board.length == 3) {
                    board[2] |= spread(old2, 16, ONES[0]) & MASKS[(size - 8) * 16] | old1 >>> 48;
                } else {
                    long old3 = board[3];
                    board[2] |= spread(old2, 16, ONES[0]) | old3 << 48 | old1 >>> 48;
                    board[3] |= spread(old3, 16, ONES[0]) & MASKS[(size - 12) * 16] | old2 >>> 48;
                }
            }

            private static BitBoard compress(long[] lines) {
                long[] board = new long[lines.length >> 2];
                for (int i = 0; i < lines.length; i++) {
                    board[i >> 2] = board[i >> 2] << 16 | lines[i];
                }
                return new BitBoard16(lines.length, board);
            }
        }

        private static class BitBoard32 extends BitBoard { // [      ][      ] x16
            private BitBoard32(int size) {
                super(size, new long[(size + 1) >> 1]);
            }

            private BitBoard32(int size, long[] board) {
                super(size, board);
            }

            public BitBoard copy() {
                return new BitBoard32(size, board);
            }

            protected int x(int x, int y) {
                return (y & 1) << 5 | x;
            }

            protected int y(int x, int y) {
                return y >> 1;
            }

            public long line(int y) {
                return board[y >> 1] >>> ((y & 1) << 5) & 0xFFFFFFFFL;
            }

            public void fillOnes() {
                Arrays.fill(board, MASKS[size] << 16 | MASKS[size]);
                if ((size & 1) == 1) {
                    board[board.length - 1] = MASKS[size];
                }
            }

            public void spread() {
                long old = 0;
                for (int i = 0; i < board.length; i++) {
                    if (i > 0) {
                        board[i - 1] |= board[i] << 32;
                    }
                    long old2 = board[i];
                    board[i] |= spread(board[i], 32, 0x100000001L) | old >>> 32;
                    old = old2;
                }
                if ((size & 1) == 1) {
                    board[board.length - 1] &= 0xFFFFFFFFL;
                }
            }

            private static BitBoard compress(long[] lines) {
                long[] board = new long[lines.length >> 2];
                for (int i = 0; i < lines.length; i++) {
                    board[i >> 2] = board[i >> 2] << 16 | lines[i];
                }
                return new BitBoard32(lines.length, board);
            }
        }

        private static class BitBoard64 extends BitBoard { // [              ] x64
            private BitBoard64(int size) {
                super(size, new long[size]);
            }

            private BitBoard64(int size, long[] board) {
                super(size, board);
            }

            public BitBoard copy() {
                return new BitBoard64(size, board);
            }

            protected int x(int x, int y) {
                return x;
            }

            protected int y(int x, int y) {
                return y;
            }

            public long line(int y) {
                return board[y];
            }

            public void fillOnes() {
                Arrays.fill(board, MASKS[size]);
            }

            public void spread() {
                long old = 0;
                for (int i = 0; i < board.length; i++) {
                    if (i > 0) {
                        board[i - 1] |= board[i];
                    }
                    long old2 = board[i];
                    board[i] |= old | board[i] >>> 1 | board[i] << 1 & MASKS[size];
                    old = old2;
                }
            }

            private static BitBoard compress(long[] lines) {
                return new BitBoard64(lines.length, lines);
            }
        }

        protected final long[] board;
        protected final byte size;

        private BitBoard(int size, long[] board) {
            this.size = (byte)size;
            this.board = board;
        }

        public static BitBoard of(long[] lines) {
            int size = lines.length;
            if (size <= 8) {
                return BitBoard8.compress(lines);
            } else if (size <= 16) {
                return BitBoard16.compress(lines);
            } else if (size <= 32) {
                return BitBoard32.compress(lines);
            } else if (size <= 64) {
                return BitBoard64.compress(lines);
            }
            throw new IllegalArgumentException();
        }

        public static BitBoard zeros(int size) {
            if (0 <= size) {
                if (size <= 8) {
                    return new BitBoard8(size);
                } else if (size <= 16) {
                    return new BitBoard16(size);
                } else if (size <= 32) {
                    return new BitBoard32(size);
                } else if (size <= 64) {
                    return new BitBoard64(size);
                }
            }
            throw new IllegalArgumentException();
        }

        public static BitBoard ones(int size) {
            BitBoard board = zeros(size);
            board.fillOnes();
            return board;
        }

        protected long spread(long a, int b, long ones) {
            long shiftLeft = (a & ~ones) >>> 1;
            long shiftRight = (a & ~(ones << size - 1)) << 1;
            return shiftLeft | shiftRight | a << b | a >>> b;
        }

        protected abstract int x(int x, int y);

        protected abstract int y(int x, int y);

        public abstract BitBoard copy();

        public abstract long line(int y);

        public abstract void fillOnes();

        public abstract void spread();

        public BitBoard subboard(int sx, int sy, int size) {
            long[] lines = new long[size];
            for (int i = 0; i < size; i++) {
                lines[i] = line(sy + i) >> sx & MASKS[size];
            }
            return BitBoard.of(lines);
        }

        public void set(int x, int y) {
            Objects.checkIndex(x, size);
            Objects.checkIndex(y, size);
            board[y(x, y)] |= 1L << x(x, y);
        }

        public void set(int x, int y, boolean value) {
            if (value) {
                set(x, y);
            } else {
                clear(x, y);
            }
        }

        public void flip(int x, int y) {
            Objects.checkIndex(x, size);
            Objects.checkIndex(y, size);
            board[y(x, y)] ^= 1L << x(x, y);
        }

        public void clear(int x, int y) {
            Objects.checkIndex(x, size);
            Objects.checkIndex(y, size);
            board[y(x, y)] &= ~(1L << x(x, y));
        }

        public boolean get(int x, int y) {
            Objects.checkIndex(x, size);
            Objects.checkIndex(y, size);
            return (line(y) >>> x & 1) == 1;
        }

        public void and(BitBoard o) {
            for (int i = 0; i < board.length; i++) {
                board[i] &= o.board[i];
            }
        }

        public void or(BitBoard o) {
            for (int i = 0; i < board.length; i++) {
                board[i] |= o.board[i];
            }
        }

        public void xor(BitBoard o) {
            for (int i = 0; i < board.length; i++) {
                board[i] ^= o.board[i];
            }
        }

        public void andNot(BitBoard o) {
            for (int i = 0; i < board.length; i++) {
                board[i] &= ~o.board[i];
            }
        }

        public int size() {
            return size;
        }

        public int countOne() {
            int count = 0;
            for (long bits : board) {
                count += Long.bitCount(bits);
            }
            return count;
        }

        public int countZero() {
            return size * size - countOne();
        }

        @Override
        public int hashCode() {
            long h = 1234;
            for (int i = 0; i < board.length; i++) {
                h ^= board[i] * (i + 1);
            }
            return (int)(h >> 32 ^ h);
        }

        @Override
        public boolean equals(Object o) {
            return this == o || o instanceof BitBoard && Arrays.equals(board, ((BitBoard)o).board);
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    builder.append(get(j, i) ? 'o' : '.');
                }
                if (i + 1 < size) {
                    builder.append('\n');
                }
            }
            return builder.toString();
        }
    }

    public static void main(String... args) {
        try {
            new Main().solve();
            out.flush();
        } catch (Exception e) {

        }
    }
}

class In {
    private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    char[] nextCharArray() {
        return next().toCharArray();
    }

    String[] nextStringArray(int n) {
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = next();
        }
        return s;
    }

    char[][] nextCharGrid(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    int[][] nextIntMatrix(int h, int w) {
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextIntArray(w);
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }

    long[][] nextLongMatrix(int h, int w) {
        long[][] a = new long[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextLongArray(w);
        }
        return a;
    }

    List<List<Integer>> nextEdges(int n, int m, boolean directed) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            res.get(u).add(v);
            if (!directed) {
                res.get(v).add(u);
            }
        }
        return res;
    }
}

class Out {
    private final PrintWriter out = new PrintWriter(System.out);
    private final PrintWriter err = new PrintWriter(System.err);
    boolean autoFlush = false;
    boolean enableDebug;

    Out(boolean enableDebug) {
        this.enableDebug = enableDebug;
    }

    void println(Object... args) {
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        out.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == Double.class ? String.format("%.10f", obj) :
                   clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
        if (autoFlush) {
            out.flush();
        }
    }

    void debug(Object... args) {
        if (!enableDebug) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        err.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == Double.class ? String.format("%.10f", obj) :
                   clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
        err.flush();
    }

    void println(char[] s) {
        out.println(String.valueOf(s));
        if (autoFlush) {
            out.flush();
        }
    }

    void println(int[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i : a) {
            joiner.add(Integer.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void println(long[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (long i : a) {
            joiner.add(Long.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void flush() {
        err.flush();
        out.flush();
    }
}
0