結果

問題 No.5016 Worst Mayor
ユーザー Yu_212Yu_212
提出日時 2023-04-29 16:29:29
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,172 ms / 2,000 ms
コード長 27,879 bytes
コンパイル時間 5,166 ms
コンパイル使用メモリ 86,656 KB
実行使用メモリ 72,964 KB
スコア 20,730,550,080
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 16:30:42
合計ジャッジ時間 62,316 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,044 ms
72,448 KB
testcase_01 AC 900 ms
72,012 KB
testcase_02 AC 952 ms
72,684 KB
testcase_03 AC 1,026 ms
72,524 KB
testcase_04 AC 1,057 ms
71,516 KB
testcase_05 AC 1,119 ms
72,768 KB
testcase_06 AC 929 ms
71,812 KB
testcase_07 AC 1,012 ms
72,220 KB
testcase_08 AC 992 ms
72,468 KB
testcase_09 AC 1,050 ms
72,664 KB
testcase_10 AC 1,028 ms
72,616 KB
testcase_11 AC 988 ms
72,728 KB
testcase_12 AC 1,072 ms
72,140 KB
testcase_13 AC 952 ms
72,740 KB
testcase_14 AC 942 ms
72,348 KB
testcase_15 AC 980 ms
72,460 KB
testcase_16 AC 1,029 ms
72,328 KB
testcase_17 AC 1,017 ms
71,868 KB
testcase_18 AC 1,056 ms
72,312 KB
testcase_19 AC 1,172 ms
72,584 KB
testcase_20 AC 1,084 ms
72,204 KB
testcase_21 AC 1,096 ms
72,708 KB
testcase_22 AC 969 ms
71,784 KB
testcase_23 AC 1,072 ms
72,012 KB
testcase_24 AC 1,165 ms
71,840 KB
testcase_25 AC 959 ms
71,976 KB
testcase_26 AC 940 ms
72,184 KB
testcase_27 AC 1,021 ms
72,396 KB
testcase_28 AC 966 ms
72,288 KB
testcase_29 AC 976 ms
71,540 KB
testcase_30 AC 971 ms
72,964 KB
testcase_31 AC 1,029 ms
72,416 KB
testcase_32 AC 1,061 ms
71,560 KB
testcase_33 AC 1,084 ms
71,444 KB
testcase_34 AC 996 ms
71,728 KB
testcase_35 AC 1,112 ms
72,784 KB
testcase_36 AC 927 ms
72,460 KB
testcase_37 AC 1,079 ms
71,872 KB
testcase_38 AC 1,042 ms
72,672 KB
testcase_39 AC 1,155 ms
72,924 KB
testcase_40 AC 1,061 ms
72,340 KB
testcase_41 AC 1,134 ms
72,664 KB
testcase_42 AC 1,115 ms
71,132 KB
testcase_43 AC 1,042 ms
72,456 KB
testcase_44 AC 1,067 ms
71,616 KB
testcase_45 AC 1,034 ms
72,460 KB
testcase_46 AC 1,052 ms
72,444 KB
testcase_47 AC 1,143 ms
72,096 KB
testcase_48 AC 1,091 ms
72,480 KB
testcase_49 AC 951 ms
71,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.*;
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 boolean isLocal;
    Random rand = new Random();
    In in = new In(System.in);
    PrintStream out = System.out;
    long inf = 0x1fffffffffffffffL;
    int iinf = 0x3fffffff;
    long startTime;

    public static final long[] TABLE = new long[364];
    public static final int[] COST = {0,10000000,7071067,5773502,5000000,4472135,4082482,3779644,3535533,3333333,3162277,3015113,2886751,2773500,2672612,2581988,2500000,2425356,2357022,2294157,2236067,2182178,2132007,2085144,2041241,2000000,1961161,1924500,1889822,1856953,1825741,1796053,1767766,1740776,1714985,1690308,1666666,1643989,1622214,1601281,1581138,1561737,1543033,1524985,1507556,1490711,1474419,1458649,1443375,1428571,1414213,1400280,1386750,1373605,1360827,1348399,1336306,1324532,1313064,1301889,1290994,1280368,1270001,1259881,1250000,1240347,1230914,1221694,1212678,1203858,1195228,1186781,1178511,1170411,1162476,1154700,1147078,1139605,1132277,1125087,1118033,1111111,1104315,1097642,1091089,1084652,1078327,1072112,1066003,1059997,1054092,1048284,1042572,1036951,1031421,1025978,1020620,1015346,1010152,1005037,1000000,995037,990147,985329,980580,975900,971285,966736,962250,957826,953462,949157,944911,940720,936585,932504,928476,924500,920574,916698,912870,909090,905357,901669,898026,894427,890870,887356,883883,880450,877058,873704,870388,867109,863868,860662,857492,854357,851256,848188,845154,842151,839181,836242,833333,830454,827605,824786,821994,819231,816496,813788,811107,808452,805822,803219,800640,798086,795557,793051,790569,788110,785674,783260,780868,778498,776150,773823,771516,769230,766964,764719,762492,760285,758098,755928,753778,751646,749531,747435,745355,743294,741249,739221,737209,735214,733235,731272,729324,727392,725476,723574,721687,719815,717958,716114,714285,712470,710669,708881,707106,705345,703597,701862,700140,698430,696733,695048,693375,691714,690065,688428,686802,685188,683585,681994,680413,678844,677285,675737,674199,672672,671156,669649,668153,666666,665190,663723,662266,660818,659380,657951,656532,655121,653720,652328,650944,649569,648203,646846,645497,644156,642824,641500,640184,638876,637576,636284,635000,633724,632455,631194,629940,628694,627455,626224,625000,623782,622572,621369,620173,618984,617802,616626,615457,614295,613139,611990,610847,609710,608580,607456,606339,605227,604122,603022,601929,600841,599760,598684,597614,596549,595491,594438,593390,592348,591312,590281,589255,588235,587220,586210,585205,584206,583211,582222,581238,580258,579284,578314,577350,576390,575435,574484,573539,572598,571661,570730,569802,568880,567961,567047,566138,565233,564332,563436,562543,561655,560772,559892,559016,558145,557278,556414,555555,554700,553848,553001,552157,551317,550481,549649,548821,547996,547175,546358,545544,544734,543928,543125,542326,541530,540738,539949,539163,538381,537603,536828,536056,535287,534522,533760,533001,532246,531494,530744,529998,529256,528516,527779,527046,526315,525588,524863,524142,523423,522708,521995,521286,520579,519875,519174,518475,517780,517087,516397,515710,515026,514344,513665,512989,512315,511644,510976,510310,509647,508986,508328,507673,507020,506369,505721,505076,504433,503792,503154,502518,501885,501254,500626,500000};
    public static final int S = 14;
    public static final int SS = 196;
    public static final int N = 3000;
    public static final int T = 400;
    int curTurn;
    int corCollabo = 1;
    int corMoney = 1000000;
    long solve(int seed) {
        startTime = System.currentTimeMillis();
        Arrays.setAll(TABLE, i -> rand.next());
        in();

        //  80 10 424367600
        //  80 20 450836500
        //  80 30 439329940
        //  80 50 416846380
        //  50 50 404948590
        //  70 50 416677250
        //  90 50 417352330
        // 100 50 402903920
        // 150 50 344831110


//        int u1 = 80;
//        Trace trace = new Trace();
//        State2 result = greedy(new State2(), trace, u1);
//        List<Action> actions = trace.trace(result.id);
//        int nj = 0;
//        int lastU = 0;
//        while (curTurn < T) {
//            boolean c1 = corMoney >= COST[corCollabo] && nj < actions.size();
//            int cd = COST[corCollabo] - COST[corCollabo + 1];
//            int ud = !c1 ? 0 : actions.get(nj).opened.score - lastU;
//            int e1 = !c1 ? -1 : (T - curTurn) * ud - cd;
//            int e2 = (actions.size() - nj) * cd - ud - 50000;
//            int e3 = 50000 - cd - ud;
//            debug(e1, e2, e3);
//            if (e2 > e1 && e2 > e3) {
//                corCollabo++;
//                corMoney += 60 * lastU;
//                ask2();
//            } else if (c1) {
//                Action action = actions.get(nj);
//                lastU = action.opened.score;
//                corMoney += 60 * lastU - COST[corCollabo];
//                nj++;
//                ask1(action.x, action.v);
//            } else {
//                corMoney += 50000 + 60 * lastU;
//                ask3();
//            }
//        }




        int[] u2 = {50};

        State2 state = new State2();
        //        State2 result = beamSearch(new State2(), trace, 10, 100000);
        //        debug(result.score);
        if (!isLocal) {
            corMoney = in.nextInt();
            in.nextInt();
        }
        //        int money = 1000000;
        int lastU = 0;
        int nj = 0;
        while (true) {
            for (int i = 0; nj < u2.length && i < u2[nj]; i++) {
                corCollabo++;
                ask2();
            }
            while (corMoney < COST[corCollabo]) {
                corMoney += 50000 + 60 * lastU;
                ask3();
            }

            Action best = null;
            for (Action next : state.actions()) {
                next.open();
                if (best == null || best.score < next.score) {
                    best = next;
                }
            }
            state = best.opened;

            //            debug(k++, pos(action.x), action.v, action.opened.score);
            if ((best.opened.score - lastU) * (T - curTurn) < 30000) {
                debug(nj);
                break;
            }
//            debug((best.opened.score - lastU) * (T - curTurn));
            lastU = best.opened.score;
            corMoney += 60 * lastU - COST[corCollabo];
            nj++;
            ask1(best.x, best.v);
            if (curTurn >= T) {
                break;
            }
        }
        while (curTurn < T) {
            corMoney += 60 * lastU;
            ask3();
        }








//
//        int u1 = 80;
//        int[] u2 = {30, 20};
//
//        Trace trace = new Trace();
//        State2 result = greedy(new State2(), trace, u1);
////        State2 result = beamSearch(new State2(), trace, 10, 100000);
////        debug(result.score);
//        if (!isLocal) {
//            corMoney = in.nextInt();
//            in.nextInt();
//        }
////        int money = 1000000;
//        int lastU = 0;
//        int nj = 0;
//        List<Action> actions = trace.trace(result.id);
//        for (Action action : actions) {
//            for (int i = 0; nj < u2.length && i < u2[nj]; i++) {
//                corCollabo++;
//                ask2();
//            }
//            while (corMoney < COST[corCollabo]) {
//                corMoney += 50000 + 60 * lastU;
//                ask3();
//            }
////            debug(k++, pos(action.x), action.v, action.opened.score);
//            if ((action.opened.score - lastU) * (T - curTurn) < 30000) {
//                break;
//            }
//            debug((action.opened.score - lastU) * (T - curTurn));
//            lastU = action.opened.score;
//            corMoney += 60 * lastU - COST[corCollabo];
//            nj++;
//            ask1(action.x, action.v);
//            if (curTurn >= T) {
//                break;
//            }
//        }
//        while (curTurn < T) {
//            corMoney += 60 * lastU;
//            ask3();
//        }
        return isLocal ? corMoney : 0;
    }

    int px(int x, boolean v) {
        return v ? x : x % S * S + x / S;
    }

    int py(int x, boolean v) {
        return v ? x + S : x % S * S + x / S + 1;
    }

    void ask1(int x, boolean v) {
        Pos px = pos(px(x, v));
        Pos py = pos(py(x, v));
        out.println("1 " + (px.x+1) + " " + (px.y+1) + " " + (py.x+1) + " " + (py.y+1));
        out.flush();
        curTurn++;
        if (!isLocal && curTurn < T) {
            corMoney = in.nextInt();
            in.nextInt();
        }
    }

    void ask2() {
        out.println(2);
        out.flush();
        curTurn++;
        if (!isLocal && curTurn < T) {
            corMoney = in.nextInt();
            in.nextInt();
        }
    }

    void ask3() {
        out.println(3);
        out.flush();
        curTurn++;
        if (!isLocal && curTurn < T) {
            corMoney = in.nextInt();
            in.nextInt();
        }
    }

    Pos[] fs, ts;
    void in() {
        Pos.init(S);
        in.nextInt();
        in.nextInt();
        fs = new Pos[N];
        ts = new Pos[N];
        for (int i = 0; i < N; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int c = in.nextInt() - 1;
            int d = in.nextInt() - 1;
            fs[i] = pos(a, b);
            ts[i] = pos(c, d);
        }
    }

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

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

    static class Pos implements Comparable<Pos> {
        static Pos[] instances = new Pos[SS];
        static Pos[] moved = new Pos[4 * SS];
        static void init(int n) {
            for (int i = 0; i < n * n; i++) {
                instances[i] = new Pos(i % n, i / n, i);
            }
            for (int i = 0; i < n * n; i++) {
                for (int d = 0; d < 4; d++) { // LURD
                    int nx = i % n + (d - 1) % 2;
                    int ny = i / n + (d - 2) % 2;
                    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                        moved[i * 4 + d] = instances[ny * n + nx];
                    }
                }
            }
        }

        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[z * 4 + d];
        }

        int dist(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 i == 4 ? p : 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);
        }
    }

//    class State {
//        int collabo;
//        int money;
//        BitSet vert;
//        BitSet hori;
//
//        int constructCost() {
//            return COST[collabo];
//        }
//    }

    State2 initialState() {
        return new State2();
    }

    class State2 implements Comparable<State2> {
        int id;
        State2 prev;
        int score;
        long hash;
        BitSet vert; // |
        BitSet hori; // -
        int[] dist;
        int[] uses;

        State2() {
            this.id = -1;
            this.hash = 0;
            this.vert = new BitSet(SS);
            this.hori = new BitSet(SS);
            this.dist = new int[N];
            this.uses = new int[N];
            for (int i = 0; i < N; i++) {
                dist[i] = Math.abs(fs[i].x - ts[i].x) + Math.abs(fs[i].y - ts[i].y);
            }
        }

        State2(State2 prev) {
            this.id = prev.id;
            this.prev = prev;
            this.score = prev.score;
            this.hash = prev.hash;
            this.vert = (BitSet)prev.vert.clone();
            this.hori = (BitSet)prev.hori.clone();
            this.dist = prev.dist.clone();
            this.uses = prev.uses.clone();
        }

        boolean highway(Pos p, int d) {
            if ((d & 1) == 0) { // LURD
                return hori.get(p.z - (d>>1^1));
            } else {
                return vert.get(p.z - (d>>1^1) * S);
            }
        }

        int dist(int d, int u) {
            return d * 1000 - u * 777;
        }

        void update(int x, boolean v) {
            int px = px(x, v);
            int py = py(x, v);
            (v ? vert : hori).set(px);
            hash ^= TABLE[x + (v ? 182 : 0)];
            Deque<Pos> deque1 = new ArrayDeque<>();
            Deque<Pos> deque2 = new ArrayDeque<>();
            BitSet fromY = new BitSet(SS);
            deque1.add(pos(px));
            deque1.add(pos(py));
            deque2.add(pos(px));
            deque2.add(pos(py));
            fromY.set(py);
            int[] ds = new int[SS];
            int[] us = new int[SS];
            Arrays.fill(ds, 30);
            ds[px] = 0;
            ds[py] = 0;
            while (!deque1.isEmpty() || !deque2.isEmpty()) {
                Pos p1 = deque1.isEmpty() ? null : deque1.peekFirst();
                Pos p2 = deque2.isEmpty() ? null : deque2.peekFirst();
                Pos p;
                boolean h = p2 == null || p1 != null && dist(ds[p1.z], us[p1.z]) < dist(ds[p2.z], us[p2.z]);
                if (h) {
                    p = deque1.removeFirst();
                } else {
                    p = deque2.removeFirst();
                }
                for (int i = 0; i < 4; i++) {
                    Pos q = p.moved(i);
                    if (q == null || highway(p, i) != h) {
                        continue;
                    }
                    int nd = ds[p.z] + 1;
                    int nu = us[p.z] + (h ? 1 : 0);
                    if (dist(ds[q.z], us[q.z]) > dist(nd, nu)) {
                        ds[q.z] = nd;
                        us[q.z] = nu;
                        fromY.set(q.z, fromY.get(p.z));
                        deque1.addLast(q);
                        deque2.addLast(q);
                    }
                }
            }
            for (int i = 0; i < N; i++) {
                if (fromY.get(fs[i].z) == fromY.get(ts[i].z)) {
                    continue;
                }
                int nd = ds[fs[i].z] + ds[ts[i].z] + 1;
                int nu = us[fs[i].z] + us[ts[i].z] + 1;
                if (dist(dist[i], uses[i]) > dist(nd, nu)) {
                    score += nu - uses[i];
                    dist[i] = nd;
                    uses[i] = nu;
                }
            }
        }

        static int[] ord = new int[182];
        static {
            Arrays.setAll(ord, i -> i);
        }
        List<Action> actions() {
            List<Action> nexts = new ArrayList<>();
            for (int ii = 0; ii < 40; ii++) {
                int j = ii + rand.next(182 - ii);
                int i = ord[j];
                ord[j] = ord[ii];
                ord[ii] = i;
                if (!vert.get(i)) {
                    nexts.add(new Action(this, hash ^ TABLE[i + 182], i, true));
                }
                if (!hori.get(i)) {
                    nexts.add(new Action(this, hash ^ TABLE[i], i, false));
                }
            }
            return nexts;
        }

        void advance(Trace trace, Action action) {
            hash = action.hash;
            score = action.score;
            id = trace.add(action, id);
        }

        State2 copy() {
            return new State2(this);
        }

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

    class Action implements Comparable<Action> {
        State2 prev;
        State2 opened;
        long hash;
        int score;
        int x;
        boolean v;

        Action(State2 prev, long hash, int x, boolean v) {
            this.prev = prev;
            this.hash = hash;
            this.x = x;
            this.v = v;
        }

        void open() {
            opened = prev.copy();
            opened.update(x, v);
            score = opened.score;
        }

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

    static class Trace {
        List<Action> log = new ArrayList<>();
        List<Integer> prev = new ArrayList<>();

        int add(Action action, int pi) {
            log.add(action);
            prev.add(pi);
            return log.size() - 1;
        }

        List<Action> trace(int id) {
            List<Action> actions = new ArrayList<>();
            while (id != -1) {
                actions.add(log.get(id));
                id = prev.get(id);
            }
            Collections.reverse(actions);
            return actions;
        }

        Action first(int id) {
            Action first = null;
            while (id != -1) {
                first = log.get(id);
                id = prev.get(id);
            }
            return first;
        }

        void clear() {
            log.clear();
            prev.clear();
        }
    }

    State2 beamSearch(State2 initialState, Trace trace, int beamWidth, long timeLimit, int maxTurn) {
        long[] hashes = new long[1 << 20];
        initialState.id = -1;
        State2[] beam = {initialState};
        State2 best = null;
        for (int turn = 1; ; turn++) {
            boolean sorted = false;
            int numCand = 0;
            Action[] cand = new Action[beamWidth * 2];
            for (State2 state : beam) {
                if (state == null) {
                    break;
                }
                for (Action action : state.actions()) {
                    int key = (int)(action.hash & 0xfffff);
                    if (hashes[key] != action.hash) {
                        hashes[key] = action.hash;
                        action.open();
                        if (sorted && cand[beamWidth - 1].score > action.score) {
                            continue;
                        }
                        cand[numCand++] = action;
                        if (numCand == cand.length) {
                            Arrays.sort(cand, Comparator.reverseOrder());
                            numCand = beamWidth;
                            sorted = true;
                        }
                    }
                }
            }
            Arrays.sort(cand);
            int size = Math.min(beamWidth, numCand);
            State2[] next = new State2[size];
            int j = 0;
            State2 found = null;
            for (int i = 0; i < numCand && j < size; i++) {
                Action action = cand[i];
                State2 copy = action.opened;
                copy.advance(trace, action);
                if (best == null || best.score < copy.score) {
                    best = copy;
                }
                if (turn == maxTurn) {
                    if (found == null || found.score < copy.score) {
                        found = copy;
                    }
                    continue;
                }
                next[j++] = copy;
            }
            if (found != null) {
                return found;
            }
            if (j == 0 || elapsed(timeLimit)) {
                throw new RuntimeException();
            }
            beam = next;
        }
    }

    State2 greedy(State2 state, Trace trace, int maxTurn) {
        state.id = -1;
        for (int turn = 1; ; turn++) {
            Action best = null;
            for (Action next : state.actions()) {
                next.open();
                if (best == null || best.score < next.score) {
                    best = next;
                }
            }
            state = best.opened;
            state.advance(trace, best);
            if (turn == maxTurn) {
                return state;
            }
        }
    }

    static void debug(Object... args) {
        if (!isLocal) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        System.err.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return 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(" ")));
    }

    long elapsed() {
        return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
    }

    boolean elapsed(long timeLimit) {
        return elapsed() >= timeLimit;
    }

    public static void main(String[] args) {
        new Main().solve(0);
    }

    static class BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {
        private final int n;
        private final Object[] a;
        private int size;

        public BinarySearchTree(int n) {
            this.n = n;
            this.a = new Object[n];
        }

        public int size() {
            return size;
        }

        public void add(E element) {
            if (size < n) {
                int i = size++;
                while (i > 0) {
                    int parent = (i - 1) / 2;
                    if (get(parent).compareTo(element) <= 0) {
                        break;
                    }
                    a[i] = a[parent];
                    i = parent;
                }
                a[i] = element;
            } else if (n > 0 && get(0).compareTo(element) < 0) {
                int i = 0;
                while (i * 2 + 1 < n) {
                    int child = i * 2 + 1;
                    if (child + 1 < n && get(child).compareTo(get(child + 1)) > 0) {
                        child++;
                    }
                    if (get(child).compareTo(element) >= 0) {
                        break;
                    }
                    a[i] = a[child];
                    i = child;
                }
                a[i] = element;
            }
        }

        @SuppressWarnings("unchecked")
        private E get(int index) {
            return (E)a[index];
        }

        @Override
        public Iterator<E> iterator() {
            return new Iterator<E>() {
                private int i = 0;

                @Override
                public boolean hasNext() {
                    return i < size;
                }

                @Override
                public E next() {
                    return get(i++);
                }
            };
        }
    }

    static class Random {
        private long x, y, z, w;

        Random() {
            this(ThreadLocalRandom.current().nextLong());
        }

        Random(long seed) {
            this.x = seed;
            for (int i = 0; i < 20; i++) {
                rand();
            }
        }

        private long rand() {
            long t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ t ^ (t >>> 8);
            return x & 0x7fffffff;
        }

        long next() {
            return rand() << 31 | rand();
        }

        int next(int n) {
            return (int)(rand() % n);
        }

        int next(int l, int r) {
            return (int)(rand() % (r - l) + l);
        }

        double nextDouble() {
            return rand() / 2147483647.0;
        }
    }

    static class In {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        In(InputStream input) {
            this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
        }

        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;
        }
    }
}
0