John Doe offered his sister Jane Doe find the gcd of some set of numbers a.

Gcd is a positive integer g, such that all number from the set are evenly divisible by g and there isn't such g' (g' > g), that all numbers of the set are evenly divisible by g'.

Unfortunately Jane couldn't cope with the task and John offered her to find the ghd of the same subset of numbers.

Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g and there isn't such g' (g' > g) that at least half of the numbers from the set are evenly divisible by g'.

Jane coped with the task for two hours. Please try it, too.

Input

The first line contains an integer n (1 ≤ n ≤ 106) showing how many numbers are in set a. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1012). Please note, that given set can contain equal numbers.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64d specifier.

Output

Print a single integer g — the Ghd of set a.

Examples

Input

6
6 2 3 4 5 6


Output

3


Input

5
5 5 6 10 15


Output

5
1
1
 1
7
 2
1 7
 100
32 40 7 3 7560 21 7560 7560 10 12 3 7560 7560 7560 7560 5 7560 7560 6 7560 7560 7560 35 7560 18 7560 7560 7560 7560 7560 48 2 7 25 7560 2 2 49 7560 7560 15 16 7560 7560 2 7560 27 7560 7560 7560 7560 3 5 7560 8 7560 42 45 5 7560 5 7560 4 7 3 7560 7 3 7560 7 2 7560 7560 5 3 7560 7560 28 7560 7560 14 7560 5 7560 20 7560 24 7560 2 9 36 7 7560 7560 7560 7560 7560 30 7560 50
 1
3

1
 7
 7
 7560
 3

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Random;
import java.util.HashSet;
import java.util.OptionalLong;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.stream.LongStream;
import java.util.Collection;
import java.util.Set;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.stream.Stream;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DGhd solver = new DGhd();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DGhd {
        OrderedDivisorIterator visitor = new OrderedDivisorIterator(true);
        DivisionPrefixSum ps = new DivisionPrefixSum(0, Long::sum);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            long[] a = in.rl(n);
            if (n <= 2) {
                long max = Arrays.stream(a).max().orElse(-1);
                out.println(max);
                return;
            }

            long ans = 0;
            long end = System.currentTimeMillis() + 3500;
            while (System.currentTimeMillis() < end) {
                long x = RandomWrapper.INSTANCE.range(a);
                long cand = search((n + 1) / 2, a, x);
                ans = Math.max(ans, cand);
            }

            out.println(ans);
        }

        public long search(int atLeast, long[] a, long g) {
            LongFactorization factorization = new LongFactorization(g);
            visitor.init(factorization);
            ps.init(factorization);
            for (long x : a) {
                ps.add(g / GCDs.gcd(g, x), 1);
            }
            while (visitor.hasNext()) {
                long x = visitor.next();
                if (ps.prefixSum(x) >= atLeast) {
                    return g / x;
                }
            }
            return 1;
        }

    }

    static interface LongFunction {
        long apply(long x);

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper();

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public RandomWrapper(long seed) {
            this(new Random(seed));
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

        public long nextLong(long n) {
            return Math.round(random.nextDouble() * (n - 1));
        }

        public long range(long... x) {
            return x[nextInt(0, x.length - 1)];
        }

    }

    static class LongHashSet {
        private int now;
        private int[] slot;
        private int[] version;
        private int[] next;
        private long[] keys;
        private int alloc;
        private boolean[] removed;
        private int mask;
        private int size;
        private boolean rehash;
        private Hasher hasher = new Hasher();

        public LongHashSet(int cap, boolean rehash) {
            now = 1;
            this.mask = (1 << (32 - Integer.numberOfLeadingZeros(cap - 1))) - 1;
            this.rehash = rehash;
            slot = new int[mask + 1];
            version = new int[slot.length + 1];
            next = new int[cap + 1];
            keys = new long[cap + 1];
            removed = new boolean[cap + 1];
        }

        private void access(int i) {
            if (version[i] != now) {
                version[i] = now;
                slot[i] = 0;
            }
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            keys = Arrays.copyOf(keys, newSize);
            removed = Arrays.copyOf(removed, newSize);
        }

        public void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
            removed[alloc] = false;
            size++;
        }

        private int hash(long x) {
            return hasher.hash(x);
        }

        public void add(long x) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                alloc();
                slot[s] = alloc;
                keys[alloc] = x;
                return;
            } else {
                int index = findIndexOrLastEntry(s, x);
                if (keys[index] != x) {
                    alloc();
                    next[index] = alloc;
                    keys[alloc] = x;
                }
            }
            if (rehash && size >= slot.length) {
                rehash();
            }
        }

        private void rehash() {
            int[] newSlots = new int[Math.max(16, slot.length * 2)];
            int[] newVersions = new int[newSlots.length];
            int newMask = newSlots.length - 1;
            for (int i = 0; i < slot.length; i++) {
                access(i);
                if (slot[i] == 0) {
                    continue;
                }
                int head = slot[i];
                while (head != 0) {
                    int n = next[head];
                    int s = hash(keys[head]) & newMask;
                    next[head] = newSlots[s];
                    newSlots[s] = head;
                    head = n;
                }
            }
            this.slot = newSlots;
            this.version = newVersions;
            now = 0;
            this.mask = newMask;
        }

        public boolean contain(long x) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                return false;
            }
            return keys[findIndexOrLastEntry(s, x)] == x;
        }

        private int findIndexOrLastEntry(int s, long x) {
            int iter = slot[s];
            while (keys[iter] != x) {
                if (next[iter] != 0) {
                    iter = next[iter];
                } else {
                    return iter;
                }
            }
            return iter;
        }

        public void clear() {
            alloc = 0;
            size = 0;
            now++;
        }

        public LongIterator iterator() {
            return new LongIterator() {
                int index = 1;


                public boolean hasNext() {
                    while (index <= alloc && removed[index]) {
                        index++;
                    }
                    return index <= alloc;
                }


                public long next() {
                    if (!hasNext()) {
                        throw new IllegalStateException();
                    }
                    return keys[index++];
                }
            };
        }

        public String toString() {
            LongIterator iterator = iterator();
            StringBuilder builder = new StringBuilder("{");
            while (iterator.hasNext()) {
                builder.append(iterator.next()).append(',');
            }
            if (builder.charAt(builder.length() - 1) == ',') {
                builder.setLength(builder.length() - 1);
            }
            builder.append('}');
            return builder.toString();
        }

    }

    static class LongModular implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModular(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            if (b == 0) {
                return 0;
            }
            long ans = mul(a, b >> 1) << 1;
            if (ans >= m) {
                ans -= m;
            }
            ans += a * (b & 1);
            if (ans >= m) {
                ans -= m;
            }
            return ans;
        }

    }

    static class Bits {
        private Bits() {
        }

        public static long tailMask(int n) {
            if (n == 0) {
                return 0;
            }
            return -1L << (64 - n);
        }

    }

    static interface ILongModular {
        long getMod();

        default long plus(long a, long b) {
            return DigitUtils.modplus(a, b, getMod());
        }

        long mul(long a, long b);

        static ILongModular getInstance(long mod) {
            if (mod <= Integer.MAX_VALUE) {
                return new SmallLongModular(mod);
            }
            if (mod <= (1L << 50)) {
                return new LongModularDanger(mod);
            }
            if (mod == (1L << 61) - 1) {
                return LongModular2305843009213693951.getInstance();
            }
            return new LongModular(mod);//new BigLongModular(mod);//new LongModular(mod);
        }

    }

    static class LongMillerRabin {
        static ILongModular mod;
        static LongPower power;

        public static boolean mr(long n, int s) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            if (n % 2 == 0) {
                return false;
            }
            long m = n - 1;
            while (m % 2 == 0) {
                m /= 2;
            }
            mod = ILongModular.getInstance(n);
            power = new LongPower(mod);
            for (int i = 0; i < s; i++) {
                long x = RandomWrapper.INSTANCE.nextLong(n - 2) + 2;
                if (!mr0(x, n, m)) {
                    return false;
                }
            }
            return true;
        }

        private static boolean mr0(long x, long n, long m) {
            return test(power.pow(x, m), m, n);
        }

        private static boolean test(long y, long exp, long n) {
            long y2 = mod.mul(y, y);
            if (!(exp == n - 1 || test(y2, exp * 2, n))) {
                return false;
            }
            if (exp != n - 1 && y2 != 1) {
                return true;
            }
            if (y != 1 && y != n - 1) {
                return false;
            }
            return true;
        }

    }

    static interface LongIterator {
        boolean hasNext();

        long next();

    }

    static class OrderedDivisorIterator implements LongIterator {
        LongFactorization factorization;
        LongPriorityQueue pq = new LongPriorityQueue((int) 2e5, LongComparator.REVERSE_ORDER);
        LongHashSet set = new LongHashSet((int) 2e5, false);
        boolean inc;

        public OrderedDivisorIterator(boolean inc) {
            this.inc = inc;
        }

        public void init(LongFactorization factorization) {
            this.factorization = factorization;
            set.clear();
            pq.clear();
            pq.add(factorization.g);
        }

        public boolean hasNext() {
            return !pq.isEmpty();
        }

        public long next() {
            long head = pq.pop();
            for (long p : factorization.primes) {
                long cand = head / p;
                if (cand * p != head || set.contain(cand)) {
                    continue;
                }
                set.add(cand);
                pq.add(cand);
            }
            return inc ? factorization.g / head : head;
        }

    }

    static class LongModular2305843009213693951 implements ILongModular {
        private static long mod = 2305843009213693951L;
        private static final LongModular2305843009213693951 INSTANCE = new LongModular2305843009213693951();
        private static long mask = (1L << 32) - 1;

        private LongModular2305843009213693951() {
        }

        public static final LongModular2305843009213693951 getInstance() {
            return INSTANCE;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            long l1 = a & mask;
            long h1 = (a >> 32) & mask;
            long l2 = b & mask;
            long h2 = (b >> 32) & mask;
            long l = l1 * l2;
            long m = l1 * h2 + l2 * h1;
            long h = h1 * h2;
            long ret = (l & mod) + (l >>> 61) + (h << 3) + (m >>> 29) + ((m << 35) >>> 3) + 1;
            ret = (ret & mod) + (ret >>> 61);
            ret = (ret & mod) + (ret >>> 61);
            return ret - 1;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long round(double x) {
            if (x >= 0) {
                return (long) (x + 0.5);
            } else {
                return (long) (x - 0.5);
            }
        }

        public static long modplus(long a, long b, long mod) {
            long ans = a + b;
            if (ans >= mod) {
                ans -= mod;
            }
            return ans;
        }

        public static long mod(long x, long mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

        public static long modmul(long a, long b, long mod) {
            long k = DigitUtils.round((double) a / mod * b);
            return DigitUtils.mod(a * b - k * mod, mod);
        }

    }

    static interface LongBinaryFunction {
        long apply(long a, long b);

    }

    static interface LongComparator {
        public static final LongComparator REVERSE_ORDER = (a, b) -> Long.compare(b, a);

        public int compare(long a, long b);

    }

    static class SmallLongModular implements ILongModular {
        long mod;

        public SmallLongModular(long mod) {
            this.mod = mod;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            return a * b % mod;
        }

    }

    static class LongFactorization {
        public long g;
        public long[] primes;
        long numberOfFactors = -1;

        public LongFactorization(long g) {
            init(g);
        }

        public void init(long g) {
            assert 0 < g && g <= 1e18;
            this.g = g;
            primes = LongPollardRho.findAllFactors(g).stream().mapToLong(Long::valueOf).toArray();
            numberOfFactors = -1;
        }

        public String toString() {
            return g + "=>" + Arrays.toString(primes);
        }

    }

    static class SequenceUtils {
        public static void swap(long[] data, int i, int j) {
            long tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class Hasher {
        private long time = System.nanoTime() + System.currentTimeMillis() * 31L;

        public int shuffle(long z) {
            z += time;
            z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L;
            return (int) (((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
        }

        public int hash(long x) {
            return shuffle(x);
        }

    }

    static class GCDs {
        private GCDs() {
        }

        public static long gcd(long a, long b) {
            return a >= b ? gcd0(a, b) : gcd0(b, a);
        }

        private static long gcd0(long a, long b) {
            return b == 0 ? a : gcd0(b, a % b);
        }

    }

    static interface LongEntryIterator {
        boolean hasNext();

        void next();

        long getEntryKey();

        long getEntryValue();

    }

    static class LongPriorityQueue implements Cloneable {
        private long[] data;
        private LongComparator comparator;
        private int size;

        public LongPriorityQueue(int n, LongComparator comparator) {
            this.data = new long[n + 1];
            this.comparator = comparator;
        }

        public LongPriorityQueue(int n, LongComparator comparator, LongFunction generator) {
            this.data = new long[n + 1];
            this.comparator = comparator;

            for (int i = 1; i <= n; i++) {
                data[i] = generator.apply(i - 1);
            }
            size = n;
            for (int i = n; i >= 1; i--) {
                shiftDown(i);
            }
        }

        private int left(int i) {
            return i << 1;
        }

        private int right(int i) {
            return (i << 1) | 1;
        }

        private int parent(int i) {
            return i >> 1;
        }

        public void add(long x) {
            data[++size] = x;
            shiftUp(size);
        }

        private void shiftUp(int index) {
            while (index != 1) {
                int pid = parent(index);
                if (comparator.compare(data[pid], data[index]) <= 0) {
                    break;
                }
                SequenceUtils.swap(data, index, pid);
                index = pid;
            }
        }

        private void shiftDown(int index) {
            while (true) {
                int lid = left(index);
                int rid = right(index);
                if (lid > size) {
                    break;
                }
                int challenger = lid;
                if (rid <= size && comparator.compare(data[rid], data[lid]) < 0) {
                    challenger = rid;
                }
                if (comparator.compare(data[challenger], data[index]) >= 0) {
                    break;
                }
                SequenceUtils.swap(data, index, challenger);
                index = challenger;
            }
        }

        public long pop() {
            long ans = data[1];
            SequenceUtils.swap(data, 1, size);
            size--;
            shiftDown(1);
            return ans;
        }

        public void clear() {
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public LongPriorityQueue clone() {
            try {
                LongPriorityQueue c = (LongPriorityQueue) super.clone();
                c.data = data.clone();
                return c;
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            LongPriorityQueue queue = clone();
            while (!queue.isEmpty()) {
                builder.append(queue.pop()).append(',');
            }
            if (builder.length() > 0) {
                builder.setLength(builder.length() - 1);
            }
            return builder.toString();
        }

    }

    static class LongPollardRho {
        static long[] smallPrimes = new long[]{2, 3, 5, 7, 11, 13, 17, 19};

        public static long findFactor(long n) {
            if (n == 1) {
                return 1;
            }
            if (LongMillerRabin.mr(n, 10)) {
                return n;
            }
            while (true) {
                long f = rho(n);
                if (f != n) {
                    return f;
                }
            }
        }

        public static Set<Long> findAllFactors(long n) {
            if (n == 0) {
                throw new IllegalArgumentException();
            }

            Set<Long> set = new HashSet<>();
            for (long p : smallPrimes) {
                if (n % p != 0) {
                    continue;
                }
                set.add(p);
                while (n % p == 0) {
                    n /= p;
                }
            }
            findAllFactors(set, n);
            return set;
        }

        private static void findAllFactors(Set<Long> set, long n) {
            if (n == 1) {
                return;
            }
            long f = findFactor(n);
            if (f == n) {
                set.add(f);
                return;
            }
            long otherPart = n / f;
//        long g = GCDs.gcd(f, otherPart);
//        while (g != 1) {
//            otherPart /= g;
//            g = GCDs.gcd(f, otherPart);
//        }
            findAllFactors(set, f);
            findAllFactors(set, otherPart);
        }

        private static long rho(long n) {
            if (n % 2 == 0) {
                return 2;
            }
            if (n % 3 == 0) {
                return 3;
            }
            ILongModular modular = ILongModular.getInstance(n);
            long x = 0, y = x, t, q = 1, c = RandomWrapper.INSTANCE.nextLong(n - 1);
            for (int k = 2; ; k <<= 1, y = x, q = 1) {
                for (int i = 1; i <= k; ++i) {
                    x = modular.plus(modular.mul(x, x), c);
                    q = modular.mul(q, Math.abs(x - y));
                    if ((i & 127) == 0) {
                        t = GCDs.gcd(q, n);
                        if (t > 1) {
                            return t;
                        }
                    }
                }
                if ((t = GCDs.gcd(q, n)) > 1) {
                    return t;
                }
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(long[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readLong();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public long[] rl(int n) {
            long[] ans = new long[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class DivisionPrefixSum {
        LongFactorization factorization;
        LongHashMap values;
        LongHashMap ps;
        LongBinaryFunction merger;
        long identity;
        long[] primes;
        boolean dirty = false;

        public DivisionPrefixSum(long identity, LongBinaryFunction merger) {
            values = new LongHashMap((int) 2e5, false);
            ps = new LongHashMap((int) 2e6, false);
            this.merger = merger;
            this.identity = identity;
        }

        public void init(LongFactorization factorization) {
            this.factorization = factorization;
            this.primes = factorization.primes;
            ps.clear();
            values.clear();
            dirty = false;
        }

        public void add(long x, long mod) {
            assert factorization.g % x == 0;
            values.modify(x, mod);
            dirty = true;
        }

        private void build() {
            if (dirty) {
                ps.clear();
                dirty = false;
            }
        }

        public long prefixSum(long x) {
            build();
            return get0(mask(0, x));
        }

        private long mask(long head, long body) {
            return (head << 60) | body;
        }

        private long get0(long x) {
            long ans = ps.getOrDefault(x, Long.MIN_VALUE);
            if (ans == Long.MIN_VALUE) {
                int head = (int) (x >>> 60);
                long body = x & ~Bits.tailMask(4);
                ans = identity;
                if (head >= primes.length) {
                    ans = values.getOrDefault(body, identity);
                } else {
                    if (body % primes[head] == 0) {
                        ans = merger.apply(ans, get0(mask(head, body / primes[head])));
                    }
                    ans = merger.apply(ans, get0(mask(head + 1, body)));
                }
                ps.put(x, ans);
            }
            return ans;
        }

    }

    static class LongHashMap {
        private int now;
        private int[] slot;
        private int[] version;
        private int[] next;
        private long[] keys;
        private long[] values;
        private int alloc;
        private boolean[] removed;
        private int mask;
        private int size;
        private boolean rehash;
        private Hasher hasher = new Hasher();

        public LongHashMap(int cap, boolean rehash) {
            now = 1;
            this.mask = (1 << (32 - Integer.numberOfLeadingZeros(cap - 1))) - 1;
            slot = new int[mask + 1];
            version = new int[slot.length];
            next = new int[cap + 1];
            keys = new long[cap + 1];
            values = new long[cap + 1];
            removed = new boolean[cap + 1];
            this.rehash = rehash;
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            keys = Arrays.copyOf(keys, newSize);
            values = Arrays.copyOf(values, newSize);
            removed = Arrays.copyOf(removed, newSize);
        }

        public void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
            removed[alloc] = false;
            size++;
        }

        private void rehash() {
            int[] newSlots = new int[Math.max(16, slot.length * 2)];
            int[] newVersions = new int[newSlots.length];
            int newMask = newSlots.length - 1;
            for (int i = 0; i < slot.length; i++) {
                access(i);
                if (slot[i] == 0) {
                    continue;
                }
                int head = slot[i];
                while (head != 0) {
                    int n = next[head];
                    int s = hash(keys[head]) & newMask;
                    next[head] = newSlots[s];
                    newSlots[s] = head;
                    head = n;
                }
            }
            this.slot = newSlots;
            this.version = newVersions;
            now = 0;
            this.mask = newMask;
        }

        private int hash(long x) {
            return hasher.hash(x);
        }

        public void put(long x, long y) {
            put(x, y, true);
        }

        public void modify(long x, long dy) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                alloc();
                slot[s] = alloc;
                keys[alloc] = x;
                values[alloc] = dy;
            } else {
                int index = findIndexOrLastEntry(s, x);
                if (keys[index] != x) {
                    alloc();
                    next[index] = alloc;
                    keys[alloc] = x;
                    values[alloc] = dy;
                } else {
                    values[index] += dy;
                }
            }
            if (rehash && size >= slot.length) {
                rehash();
            }
        }

        public void put(long x, long y, boolean cover) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                alloc();
                slot[s] = alloc;
                keys[alloc] = x;
                values[alloc] = y;
            } else {
                int index = findIndexOrLastEntry(s, x);
                if (keys[index] != x) {
                    alloc();
                    next[index] = alloc;
                    keys[alloc] = x;
                    values[alloc] = y;
                } else if (cover) {
                    values[index] = y;
                }
            }
            if (rehash && size >= slot.length) {
                rehash();
            }
        }

        public long getOrDefault(long x, long def) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                return def;
            }
            int index = findIndexOrLastEntry(s, x);
            return keys[index] == x ? values[index] : def;
        }

        private int findIndexOrLastEntry(int s, long x) {
            int iter = slot[s];
            while (keys[iter] != x) {
                if (next[iter] != 0) {
                    iter = next[iter];
                } else {
                    return iter;
                }
            }
            return iter;
        }

        public void clear() {
            alloc = 0;
            size = 0;
            now++;
        }

        private void access(int i) {
            if (version[i] != now) {
                version[i] = now;
                slot[i] = 0;
            }
        }

        public LongEntryIterator iterator() {
            return new LongEntryIterator() {
                int index = 1;
                int readIndex = -1;


                public boolean hasNext() {
                    while (index <= alloc && removed[index]) {
                        index++;
                    }
                    return index <= alloc;
                }


                public long getEntryKey() {
                    return keys[readIndex];
                }


                public long getEntryValue() {
                    return values[readIndex];
                }


                public void next() {
                    if (!hasNext()) {
                        throw new IllegalStateException();
                    }
                    readIndex = index;
                    index++;
                }
            };
        }

        public String toString() {
            LongEntryIterator iterator = iterator();
            StringBuilder builder = new StringBuilder("{");
            while (iterator.hasNext()) {
                iterator.next();
                builder.append(iterator.getEntryKey()).append("->").append(iterator.getEntryValue()).append(',');
            }
            if (builder.charAt(builder.length() - 1) == ',') {
                builder.setLength(builder.length() - 1);
            }
            builder.append('}');
            return builder.toString();
        }

    }

    static class LongPower {
        final ILongModular modular;

        public LongPower(ILongModular modular) {
            this.modular = modular;
        }

        public long pow(long x, long n) {
            if (n == 0) {
                return 1;
            }
            long r = pow(x, n >> 1);
            r = modular.mul(r, r);
            if ((n & 1) == 1) {
                r = modular.mul(r, x);
            }
            return r;
        }

    }

    static class LongModularDanger implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModularDanger(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            return DigitUtils.modmul(a, b, m);
        }

    }
}

