/*
 * This code demonstrates solution to the problem described at
 * https://stackoverflow.com/questions/3492302/
 * Copyright (c) 2020, John McClane. All rights reserved.
 *   
 */
 
import java.util.*;
 
class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;
 
        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }
 
        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }
 
    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}
 
abstract class NumberBag {
    private int passCount;
 
    public void startOver() {
        passCount++;
    }
 
    public final int getPassCount() {
        return passCount;
    }
 
    public abstract boolean hasNext();
 
    public abstract int next();
 
    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;
 
            public void startOver() {
                super.startOver();
                index = fromIndex;
            }
 
            public boolean hasNext() {
                return index < toIndex;
            }
 
            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }
 
    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }
 
    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;
 
            public void startOver() {
                super.startOver();
                it = base.iterator();
            }
 
            public boolean hasNext() {
                return it.hasNext();
            }
 
            public int next() {
                return it.next();
            }
        };
    }
}
 
class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;
 
    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }
 
    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }
 
    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }
 
    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }
 
    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }
 
    public static void main(String[] args) {
        System.out.println("\nSimple tests\n");
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());
 
        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n%n",
                inputList, Arrays.toString(output), bag.getPassCount());
 
        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("Sieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
 
        System.out.println("\n\nAdvanced test");
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 1_000);
        strideCheck(100_000, 1, 100_000, 11_111, 7);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("Success. Advanced test time: %.2f s.%n", time * 1e-9);
    }
}
 

LyoKICogVGhpcyBjb2RlIGRlbW9uc3RyYXRlcyBzb2x1dGlvbiB0byB0aGUgcHJvYmxlbSBkZXNjcmliZWQgYXQKICogaHR0cHM6Ly9zdGFja292ZXJmbG93LmNvbS9xdWVzdGlvbnMvMzQ5MjMwMi8KICogQ29weXJpZ2h0IChjKSAyMDIwLCBKb2huIE1jQ2xhbmUuIEFsbCByaWdodHMgcmVzZXJ2ZWQuCiAqICAgCiAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgTWlzc2luZ051bWJlcnMgewogICAgcHJpdmF0ZSBzdGF0aWMgY2xhc3MgSW50ZXJ2YWwgewogICAgICAgIGJvb2xlYW4gYW1iaWd1b3VzID0gdHJ1ZTsKICAgICAgICBmaW5hbCBpbnQgYmVnaW47CiAgICAgICAgaW50IHF1YW50aXR5OwogICAgICAgIGxvbmcgc3VtOwoKICAgICAgICBJbnRlcnZhbChpbnQgYmVnaW4sIGludCBlbmQpIHsgLy8gYmVnaW4gaW5jbHVzaXZlLCBlbmQgZXhjbHVzaXZlCiAgICAgICAgICAgIHRoaXMuYmVnaW4gPSBiZWdpbjsKICAgICAgICAgICAgcXVhbnRpdHkgPSBlbmQgLSBiZWdpbjsKICAgICAgICAgICAgc3VtID0gcXVhbnRpdHkgKiAoKGxvbmcpZW5kIC0gMSArIGJlZ2luKSAvIDI7CiAgICAgICAgfQoKICAgICAgICB2b2lkIGV4Y2x1ZGUoaW50IHgpIHsKICAgICAgICAgICAgcXVhbnRpdHktLTsKICAgICAgICAgICAgc3VtIC09IHg7CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgaW50W10gZmluZChpbnQgbWluTnVtYmVyLCBpbnQgbWF4TnVtYmVyLCBOdW1iZXJCYWcgaW5wdXRCYWcpIHsKICAgICAgICBJbnRlcnZhbCBmdWxsID0gbmV3IEludGVydmFsKG1pbk51bWJlciwgKyttYXhOdW1iZXIpOwogICAgICAgIGZvciAoaW5wdXRCYWcuc3RhcnRPdmVyKCk7IGlucHV0QmFnLmhhc05leHQoKTspCiAgICAgICAgICAgIGZ1bGwuZXhjbHVkZShpbnB1dEJhZy5uZXh0KCkpOwogICAgICAgIGludCBtaXNzaW5nQ291bnQgPSBmdWxsLnF1YW50aXR5OwogICAgICAgIGlmIChtaXNzaW5nQ291bnQgPT0gMCkKICAgICAgICAgICAgcmV0dXJuIG5ldyBpbnRbMF07CiAgICAgICAgSW50ZXJ2YWxbXSBpbnRlcnZhbHMgPSBuZXcgSW50ZXJ2YWxbbWlzc2luZ0NvdW50XTsKICAgICAgICBpbnRlcnZhbHNbMF0gPSBmdWxsOwogICAgICAgIGludFtdIGRpdmlkZXJzID0gbmV3IGludFttaXNzaW5nQ291bnRdOwogICAgICAgIGRpdmlkZXJzWzBdID0gbWluTnVtYmVyOwogICAgICAgIGludCBpbnRlcnZhbENvdW50ID0gMTsKICAgICAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgICAgICBpbnQgb2xkQ291bnQgPSBpbnRlcnZhbENvdW50OwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG9sZENvdW50OyBpKyspIHsKICAgICAgICAgICAgICAgIEludGVydmFsIGl0diA9IGludGVydmFsc1tpXTsKICAgICAgICAgICAgICAgIGlmIChpdHYuYW1iaWd1b3VzKQogICAgICAgICAgICAgICAgICAgIGlmIChpdHYucXVhbnRpdHkgPT0gMSkgLy8gbnVtYmVyIGluc2lkZSBpdHYgdW5pcXVlbHkgaWRlbnRpZmllZAogICAgICAgICAgICAgICAgICAgICAgICBpdHYuYW1iaWd1b3VzID0gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICBpbnRlcnZhbENvdW50Kys7IC8vIGl0diB3aWxsIGJlIHNwbGl0IGludG8gdHdvIGludGVydmFscwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmIChvbGRDb3VudCA9PSBpbnRlcnZhbENvdW50KQogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIGludCBuZXdJbmRleCA9IGludGVydmFsQ291bnQgLSAxOwogICAgICAgICAgICBpbnQgZW5kID0gbWF4TnVtYmVyOwogICAgICAgICAgICBmb3IgKGludCBvbGRJbmRleCA9IG9sZENvdW50IC0gMTsgb2xkSW5kZXggPj0gMDsgb2xkSW5kZXgtLSkgewogICAgICAgICAgICAgICAgLy8gbmV3SW5kZXggYWx3YXlzID49IG9sZEluZGV4CiAgICAgICAgICAgICAgICBJbnRlcnZhbCBpdHYgPSBpbnRlcnZhbHNbb2xkSW5kZXhdOwogICAgICAgICAgICAgICAgaW50IGJlZ2luID0gaXR2LmJlZ2luOwogICAgICAgICAgICAgICAgaWYgKGl0di5hbWJpZ3VvdXMpIHsKICAgICAgICAgICAgICAgICAgICAvLyBzcGxpdCBpbnRlcnZhbCBpdHYKICAgICAgICAgICAgICAgICAgICAvLyB1c2UgZmxvb3JEaXYgaW5zdGVhZCBvZiAvIGJlY2F1c2UgaW5wdXQgbnVtYmVycyBjYW4gYmUgbmVnYXRpdmUKICAgICAgICAgICAgICAgICAgICBpbnQgbWVhbiA9IChpbnQpTWF0aC5mbG9vckRpdihpdHYuc3VtLCBpdHYucXVhbnRpdHkpICsgMTsKICAgICAgICAgICAgICAgICAgICBpbnRlcnZhbHNbbmV3SW5kZXgtLV0gPSBuZXcgSW50ZXJ2YWwobWVhbiwgZW5kKTsKICAgICAgICAgICAgICAgICAgICBpbnRlcnZhbHNbbmV3SW5kZXgtLV0gPSBuZXcgSW50ZXJ2YWwoYmVnaW4sIG1lYW4pOwogICAgICAgICAgICAgICAgfSBlbHNlCiAgICAgICAgICAgICAgICAgICAgaW50ZXJ2YWxzW25ld0luZGV4LS1dID0gaXR2OwogICAgICAgICAgICAgICAgZW5kID0gYmVnaW47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBpbnRlcnZhbENvdW50OyBpKyspCiAgICAgICAgICAgICAgICBkaXZpZGVyc1tpXSA9IGludGVydmFsc1tpXS5iZWdpbjsKICAgICAgICAgICAgZm9yIChpbnB1dEJhZy5zdGFydE92ZXIoKTsgaW5wdXRCYWcuaGFzTmV4dCgpOykgewogICAgICAgICAgICAgICAgaW50IHggPSBpbnB1dEJhZy5uZXh0KCk7CiAgICAgICAgICAgICAgICAvLyBmaW5kIHRoZSBpbnRlcnZhbCB0byB3aGljaCB4IGJlbG9uZ3MKICAgICAgICAgICAgICAgIGludCBpID0gamF2YS51dGlsLkFycmF5cy5iaW5hcnlTZWFyY2goZGl2aWRlcnMsIDAsIGludGVydmFsQ291bnQsIHgpOwogICAgICAgICAgICAgICAgaWYgKGkgPCAwKQogICAgICAgICAgICAgICAgICAgIGkgPSAtaSAtIDI7CiAgICAgICAgICAgICAgICBJbnRlcnZhbCBpdHYgPSBpbnRlcnZhbHNbaV07CiAgICAgICAgICAgICAgICBpZiAoaXR2LmFtYmlndW91cykKICAgICAgICAgICAgICAgICAgICBpdHYuZXhjbHVkZSh4KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBhc3NlcnQgaW50ZXJ2YWxDb3VudCA9PSBtaXNzaW5nQ291bnQ7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBpbnRlcnZhbENvdW50OyBpKyspCiAgICAgICAgICAgIGRpdmlkZXJzW2ldID0gKGludClpbnRlcnZhbHNbaV0uc3VtOwogICAgICAgIHJldHVybiBkaXZpZGVyczsKICAgIH0KfQoKYWJzdHJhY3QgY2xhc3MgTnVtYmVyQmFnIHsKICAgIHByaXZhdGUgaW50IHBhc3NDb3VudDsKCiAgICBwdWJsaWMgdm9pZCBzdGFydE92ZXIoKSB7CiAgICAgICAgcGFzc0NvdW50Kys7CiAgICB9CgogICAgcHVibGljIGZpbmFsIGludCBnZXRQYXNzQ291bnQoKSB7CiAgICAgICAgcmV0dXJuIHBhc3NDb3VudDsKICAgIH0KCiAgICBwdWJsaWMgYWJzdHJhY3QgYm9vbGVhbiBoYXNOZXh0KCk7CgogICAgcHVibGljIGFic3RyYWN0IGludCBuZXh0KCk7CgogICAgLy8gQSBsaWdodHdlaWdodCB2ZXJzaW9uIG9mIEl0ZXJhYmxlPEludGVnZXI+IHRvIGF2b2lkIGJveGluZyBvZiBpbnQKICAgIHB1YmxpYyBzdGF0aWMgTnVtYmVyQmFnIGZyb21BcnJheShpbnRbXSBiYXNlLCBpbnQgZnJvbUluZGV4LCBpbnQgdG9JbmRleCkgewogICAgICAgIHJldHVybiBuZXcgTnVtYmVyQmFnKCkgewogICAgICAgICAgICBpbnQgaW5kZXggPSB0b0luZGV4OwoKICAgICAgICAgICAgcHVibGljIHZvaWQgc3RhcnRPdmVyKCkgewogICAgICAgICAgICAgICAgc3VwZXIuc3RhcnRPdmVyKCk7CiAgICAgICAgICAgICAgICBpbmRleCA9IGZyb21JbmRleDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHVibGljIGJvb2xlYW4gaGFzTmV4dCgpIHsKICAgICAgICAgICAgICAgIHJldHVybiBpbmRleCA8IHRvSW5kZXg7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHB1YmxpYyBpbnQgbmV4dCgpIHsKICAgICAgICAgICAgICAgIGlmIChpbmRleCA+PSB0b0luZGV4KQogICAgICAgICAgICAgICAgICAgIHRocm93IG5ldyBOb1N1Y2hFbGVtZW50RXhjZXB0aW9uKCk7CiAgICAgICAgICAgICAgICByZXR1cm4gYmFzZVtpbmRleCsrXTsKICAgICAgICAgICAgfQogICAgICAgIH07CiAgICB9CgogICAgcHVibGljIHN0YXRpYyBOdW1iZXJCYWcgZnJvbUFycmF5KGludFtdIGJhc2UpIHsKICAgICAgICByZXR1cm4gZnJvbUFycmF5KGJhc2UsIDAsIGJhc2UubGVuZ3RoKTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIE51bWJlckJhZyBmcm9tSXRlcmFibGUoSXRlcmFibGU8SW50ZWdlcj4gYmFzZSkgewogICAgICAgIHJldHVybiBuZXcgTnVtYmVyQmFnKCkgewogICAgICAgICAgICBJdGVyYXRvcjxJbnRlZ2VyPiBpdDsKCiAgICAgICAgICAgIHB1YmxpYyB2b2lkIHN0YXJ0T3ZlcigpIHsKICAgICAgICAgICAgICAgIHN1cGVyLnN0YXJ0T3ZlcigpOwogICAgICAgICAgICAgICAgaXQgPSBiYXNlLml0ZXJhdG9yKCk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHB1YmxpYyBib29sZWFuIGhhc05leHQoKSB7CiAgICAgICAgICAgICAgICByZXR1cm4gaXQuaGFzTmV4dCgpOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwdWJsaWMgaW50IG5leHQoKSB7CiAgICAgICAgICAgICAgICByZXR1cm4gaXQubmV4dCgpOwogICAgICAgICAgICB9CiAgICAgICAgfTsKICAgIH0KfQoKY2xhc3MgQmF0Y2hUZXN0IHsKICAgIHByaXZhdGUgc3RhdGljIGZpbmFsIFJhbmRvbSByYW5kID0gbmV3IFJhbmRvbSgpOwogICAgcHVibGljIHN0YXRpYyBpbnQgTUlOX05VTUJFUiA9IDE7CiAgICBwcml2YXRlIGZpbmFsIGludCBtaW5OdW1iZXIgPSBNSU5fTlVNQkVSOwogICAgcHJpdmF0ZSBmaW5hbCBpbnQgbnVtYmVyQ291bnQ7CiAgICBwcml2YXRlIGZpbmFsIGludFtdIG51bWJlcnM7CiAgICBwcml2YXRlIGludCBtaXNzaW5nQ291bnQ7CiAgICBwdWJsaWMgbG9uZyBmaW5kZXJUaW1lOwoKICAgIHB1YmxpYyBCYXRjaFRlc3QoaW50IG51bWJlckNvdW50KSB7CiAgICAgICAgdGhpcy5udW1iZXJDb3VudCA9IG51bWJlckNvdW50OwogICAgICAgIG51bWJlcnMgPSBuZXcgaW50W251bWJlckNvdW50XTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bWJlckNvdW50OyBpKyspCiAgICAgICAgICAgIG51bWJlcnNbaV0gPSBtaW5OdW1iZXIgKyBpOwogICAgfQoKICAgIHByaXZhdGUgaW50IHBhc3NCb3VuZCgpIHsKICAgICAgICBpbnQgbUJvdW5kID0gbWlzc2luZ0NvdW50ID4gMCA/IG1pc3NpbmdDb3VudCA6IDE7CiAgICAgICAgaW50IG5Cb3VuZCA9IDM0IC0gSW50ZWdlci5udW1iZXJPZkxlYWRpbmdaZXJvcyhudW1iZXJDb3VudCAtIDEpOyAvLyBjZWlsKGxvZ18yKG51bWJlckNvdW50KSkgKyAyCiAgICAgICAgcmV0dXJuIE1hdGgubWluKG1Cb3VuZCwgbkJvdW5kKTsKICAgIH0KCiAgICBwcml2YXRlIHZvaWQgZXJyb3IoU3RyaW5nIGNhdXNlKSB7CiAgICAgICAgdGhyb3cgbmV3IFJ1bnRpbWVFeGNlcHRpb24oIkVycm9yIG9uICciICsgbWlzc2luZ0NvdW50ICsgIiBmcm9tICIgKyBudW1iZXJDb3VudCArICInIHRlc3QsICIgKyBjYXVzZSk7CiAgICB9CgogICAgLy8gcmV0dXJucyB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoZSBpbnB1dCBhcnJheSB3YXMgdHJhdmVyc2VkIGluIHRoaXMgdGVzdAogICAgcHVibGljIGludCBtYWtlVGVzdChpbnQgbWlzc2luZ0NvdW50KSB7CiAgICAgICAgdGhpcy5taXNzaW5nQ291bnQgPSBtaXNzaW5nQ291bnQ7CiAgICAgICAgLy8gbnVtYmVycyBhcnJheSBpcyByZXVzZWQgd2hlbiBudW1iZXJDb3VudCBzdGF5cyB0aGUgc2FtZSwKICAgICAgICAvLyBqdXN0IEZpc2hlcuKAk1lhdGVzIHNodWZmbGUgaXQgZm9yIGVhY2ggdGVzdAogICAgICAgIGZvciAoaW50IGkgPSBudW1iZXJDb3VudCAtIDE7IGkgPiAwOyBpLS0pIHsKICAgICAgICAgICAgaW50IGogPSByYW5kLm5leHRJbnQoaSArIDEpOwogICAgICAgICAgICBpZiAoaSAhPSBqKSB7CiAgICAgICAgICAgICAgICBpbnQgdCA9IG51bWJlcnNbaV07CiAgICAgICAgICAgICAgICBudW1iZXJzW2ldID0gbnVtYmVyc1tqXTsKICAgICAgICAgICAgICAgIG51bWJlcnNbal0gPSB0OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGZpbmFsIGludCBiYWdTaXplID0gbnVtYmVyQ291bnQgLSBtaXNzaW5nQ291bnQ7CiAgICAgICAgTnVtYmVyQmFnIGlucHV0QmFnID0gTnVtYmVyQmFnLmZyb21BcnJheShudW1iZXJzLCAwLCBiYWdTaXplKTsKICAgICAgICBmaW5kZXJUaW1lIC09IFN5c3RlbS5uYW5vVGltZSgpOwogICAgICAgIGludFtdIGZvdW5kID0gTWlzc2luZ051bWJlcnMuZmluZChtaW5OdW1iZXIsIG1pbk51bWJlciArIG51bWJlckNvdW50IC0gMSwgaW5wdXRCYWcpOwogICAgICAgIGZpbmRlclRpbWUgKz0gU3lzdGVtLm5hbm9UaW1lKCk7CiAgICAgICAgaWYgKGlucHV0QmFnLmdldFBhc3NDb3VudCgpID4gcGFzc0JvdW5kKCkpCiAgICAgICAgICAgIGVycm9yKCJ0b28gbWFueSBwYXNzZXMgKCIgKyBpbnB1dEJhZy5nZXRQYXNzQ291bnQoKSArICIgd2hpbGUgb25seSAiICsgcGFzc0JvdW5kKCkgKyAiIGFsbG93ZWQpIik7CiAgICAgICAgaWYgKGZvdW5kLmxlbmd0aCAhPSBtaXNzaW5nQ291bnQpCiAgICAgICAgICAgIGVycm9yKCJ3cm9uZyByZXN1bHQgbGVuZ3RoIik7CiAgICAgICAgaW50IGogPSBiYWdTaXplOyAvLyAibWlzc2luZyIgcGFydCBiZWdpbm5pbmcgaW4gbnVtYmVycwogICAgICAgIEFycmF5cy5zb3J0KG51bWJlcnMsIGJhZ1NpemUsIG51bWJlckNvdW50KTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG1pc3NpbmdDb3VudDsgaSsrKQogICAgICAgICAgICBpZiAoZm91bmRbaV0gIT0gbnVtYmVyc1tqKytdKQogICAgICAgICAgICAgICAgZXJyb3IoIndyb25nIHJlc3VsdCBhcnJheSwgIiArIGkgKyAiLXRoIGVsZW1lbnQgZGlmZmVycyIpOwogICAgICAgIHJldHVybiBpbnB1dEJhZy5nZXRQYXNzQ291bnQoKTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgc3RyaWRlQ2hlY2soaW50IG51bWJlckNvdW50LCBpbnQgbWluTWlzc2luZywgaW50IG1heE1pc3NpbmcsIGludCBzdGVwLCBpbnQgcmVwZWF0cykgewogICAgICAgIEJhdGNoVGVzdCB0ID0gbmV3IEJhdGNoVGVzdChudW1iZXJDb3VudCk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCLilaDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilazilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilazilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilZDilaMiKTsKICAgICAgICBmb3IgKGludCBtaXNzaW5nQ291bnQgPSBtaW5NaXNzaW5nOyBtaXNzaW5nQ291bnQgPD0gbWF4TWlzc2luZzsgbWlzc2luZ0NvdW50ICs9IHN0ZXApIHsKICAgICAgICAgICAgaW50IG1pblBhc3MgPSBJbnRlZ2VyLk1BWF9WQUxVRTsKICAgICAgICAgICAgaW50IHBhc3NTdW0gPSAwOwogICAgICAgICAgICBpbnQgbWF4UGFzcyA9IDA7CiAgICAgICAgICAgIHQuZmluZGVyVGltZSA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAxOyBqIDw9IHJlcGVhdHM7IGorKykgewogICAgICAgICAgICAgICAgaW50IHBDb3VudCA9IHQubWFrZVRlc3QobWlzc2luZ0NvdW50KTsKICAgICAgICAgICAgICAgIGlmIChwQ291bnQgPCBtaW5QYXNzKQogICAgICAgICAgICAgICAgICAgIG1pblBhc3MgPSBwQ291bnQ7CiAgICAgICAgICAgICAgICBwYXNzU3VtICs9IHBDb3VudDsKICAgICAgICAgICAgICAgIGlmIChwQ291bnQgPiBtYXhQYXNzKQogICAgICAgICAgICAgICAgICAgIG1heFBhc3MgPSBwQ291bnQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3lzdGVtLm91dC5mb3JtYXQoIuKVkSAlOWQgICU5ZCAg4pWRICAlMmQgICU1LjJmICAlMmQgIOKVkSAgJTExLjNmICAgIOKVkSVuIiwgbWlzc2luZ0NvdW50LCBudW1iZXJDb3VudCwgbWluUGFzcywKICAgICAgICAgICAgICAgICAgICAoZG91YmxlKXBhc3NTdW0gLyByZXBlYXRzLCBtYXhQYXNzLCB0LmZpbmRlclRpbWUgKiAxZS02IC8gcmVwZWF0cyk7CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlxuU2ltcGxlIHRlc3RzXG4iKTsKICAgICAgICBpbnRbXSBpbnB1dCA9IHsgNywgMSwgNCwgOSwgNiwgMiB9OwogICAgICAgIE51bWJlckJhZyBiYWcgPSBOdW1iZXJCYWcuZnJvbUFycmF5KGlucHV0KTsKICAgICAgICBpbnRbXSBvdXRwdXQgPSBNaXNzaW5nTnVtYmVycy5maW5kKDEsIDEwLCBiYWcpOwogICAgICAgIFN5c3RlbS5vdXQuZm9ybWF0KCJJbnB1dDogJXMlbk1pc3NpbmcgbnVtYmVyczogJXMlblBhc3MgY291bnQ6ICVkJW4lbiIsCiAgICAgICAgICAgICAgICBBcnJheXMudG9TdHJpbmcoaW5wdXQpLCBBcnJheXMudG9TdHJpbmcob3V0cHV0KSwgYmFnLmdldFBhc3NDb3VudCgpKTsKCiAgICAgICAgTGlzdDxJbnRlZ2VyPiBpbnB1dExpc3QgPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwOyBpKyspCiAgICAgICAgICAgIGlucHV0TGlzdC5hZGQoMiAqIGkpOwogICAgICAgIENvbGxlY3Rpb25zLnNodWZmbGUoaW5wdXRMaXN0KTsKICAgICAgICBiYWcgPSBOdW1iZXJCYWcuZnJvbUl0ZXJhYmxlKGlucHV0TGlzdCk7CiAgICAgICAgb3V0cHV0ID0gTWlzc2luZ051bWJlcnMuZmluZCgwLCAxOSwgYmFnKTsKICAgICAgICBTeXN0ZW0ub3V0LmZvcm1hdCgiSW5wdXQ6ICVzJW5NaXNzaW5nIG51bWJlcnM6ICVzJW5QYXNzIGNvdW50OiAlZCVuJW4iLAogICAgICAgICAgICAgICAgaW5wdXRMaXN0LCBBcnJheXMudG9TdHJpbmcob3V0cHV0KSwgYmFnLmdldFBhc3NDb3VudCgpKTsKCiAgICAgICAgLy8gU2lldmUgb2YgRXJhdG9zdGhlbmVzCiAgICAgICAgZmluYWwgaW50IE1BWE4gPSAxXzAwMDsKICAgICAgICBMaXN0PEludGVnZXI+IG5vblByaW1lcyA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIG5vblByaW1lcy5hZGQoMSk7CiAgICAgICAgaW50W10gcHJpbWVzOwogICAgICAgIGludCBsYXN0UHJpbWVJbmRleCA9IDA7CiAgICAgICAgd2hpbGUgKHRydWUpIHsKICAgICAgICAgICAgcHJpbWVzID0gTWlzc2luZ051bWJlcnMuZmluZCgxLCBNQVhOLCBOdW1iZXJCYWcuZnJvbUl0ZXJhYmxlKG5vblByaW1lcykpOwogICAgICAgICAgICBpbnQgcCA9IHByaW1lc1tsYXN0UHJpbWVJbmRleF07IC8vIGd1YXJhbnRlZWQgdG8gYmUgcHJpbWUKICAgICAgICAgICAgaW50IHEgPSBwOwogICAgICAgICAgICBmb3IgKGludCBpID0gbGFzdFByaW1lSW5kZXgrKzsgaSA8IHByaW1lcy5sZW5ndGg7IGkrKykgewogICAgICAgICAgICAgICAgcSA9IHByaW1lc1tpXTsgLy8gbm90IG5lY2Vzc2FyaWx5IHByaW1lCiAgICAgICAgICAgICAgICBpbnQgcHEgPSBwICogcTsKICAgICAgICAgICAgICAgIGlmIChwcSA+IE1BWE4pCiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICBub25QcmltZXMuYWRkKHBxKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAocSA9PSBwKQogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICAgIFN5c3RlbS5vdXQuZm9ybWF0KCJTaWV2ZSBvZiBFcmF0b3N0aGVuZXMuICVkIHByaW1lcyB1cCB0byAlZCBmb3VuZDolbiIsCiAgICAgICAgICAgICAgICBwcmltZXMubGVuZ3RoLCBNQVhOKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHByaW1lcy5sZW5ndGg7IGkrKykKICAgICAgICAgICAgU3lzdGVtLm91dC5mb3JtYXQoIiAlNGQlcyIsIHByaW1lc1tpXSwgKGkgJSAxMCkgPCA5ID8gIiIgOiAiXG4iKTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJcblxuQWR2YW5jZWQgdGVzdCIpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigi4pWU4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWm4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWm4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWXIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCLilZEgICAgICBOdW1iZXIgY291bnQgICAgIOKVkSAgICAgIFBhc3NlcyAgICAg4pWRICBBdmVyYWdlIHRpbWUgICDilZEiKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIuKVkSAgIG1pc3NpbWcgICAgIHRvdGFsICAg4pWRICBtaW4gIGF2ZyAgIG1heCDilZEgcGVyIHNlYXJjaCAobXMpIOKVkSIpOwogICAgICAgIGxvbmcgdGltZSA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgICAgIHN0cmlkZUNoZWNrKDEwMCwgMCwgMTAwLCAxLCAxXzAwMCk7CiAgICAgICAgc3RyaWRlQ2hlY2soMTAwXzAwMCwgMSwgMTAwXzAwMCwgMTFfMTExLCA3KTsKICAgICAgICB0aW1lID0gU3lzdGVtLm5hbm9UaW1lKCkgLSB0aW1lOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigi4pWa4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWp4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWp4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWQ4pWdIik7CiAgICAgICAgU3lzdGVtLm91dC5mb3JtYXQoIlN1Y2Nlc3MuIEFkdmFuY2VkIHRlc3QgdGltZTogJS4yZiBzLiVuIiwgdGltZSAqIDFlLTkpOwogICAgfQp9Cg==