Petya is preparing for IQ test and he has noticed that there many problems like: you are given a sequence, find the next number. Now Petya can solve only problems with arithmetic or geometric progressions.

Arithmetic progression is a sequence a1, a1 + d, a1 + 2d, ..., a1 + (n - 1)d, where a1 and d are any numbers.

Geometric progression is a sequence b1, b2 = b1q, ..., bn = bn - 1q, where b1 ≠ 0, q ≠ 0, q ≠ 1. 

Help Petya and write a program to determine if the given sequence is arithmetic or geometric. Also it should found the next number. If the sequence is neither arithmetic nor geometric, print 42 (he thinks it is impossible to find better answer). You should also print 42 if the next element of progression is not integer. So answer is always integer.

Input

The first line contains exactly four integer numbers between 1 and 1000, inclusively.

Output

Print the required number. If the given sequence is arithmetic progression, print the next progression element. Similarly, if the given sequence is geometric progression, print the next progression element.

Print 42 if the given sequence is not an arithmetic or geometric progression.

Examples

Input

836 624 412 200


Output

-12


Input

1 334 667 1000


Output

1333

Note

This problem contains very weak pretests!
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.Locale;
import java.io.OutputStream;
import java.util.RandomAccess;
import java.io.PrintWriter;
import java.util.AbstractList;
import java.io.Writer;
import java.util.List;
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Jacob Jiang
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskA {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int d = in.nextInt();
        if (d - c == c - b && c - b == b - a) {
            out.println(d + d - c);
            return;
        }
        Rational q1 = new Rational(b, a);
        Rational q2 = new Rational(c, b);
        Rational q3 = new Rational(d, c);
        if (q1.equals(q2) && q1.equals(q3)) {
            Rational e = q1.multiply(Rational.valueOf(d));
            if (e.denominator == 1) {
                out.println(e.numerator);
                return;
            }
        }
        out.println(42);
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 16];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public void skipNext() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        do {
            c = read();
        } while (!isSpaceChar(c));
    }

    public void skipNext(int times) {
        while (times-- > 0) {
            skipNext();
        }
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public char nextChar() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public boolean hasNext() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value != -1;
    }

    public String rawNextLine() {
        StringBuilder buf = new StringBuilder();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String nextLine() {
        String s = rawNextLine();
        while (s.trim().length() == 0)
            s = rawNextLine();
        return s;
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, nextInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c & 15) * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }

    public BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }

    public int[] nextIntArray(int count) {
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextInt();
        }
        return result;
    }

    public int[] nextIntArray() {
        return nextIntArray(nextInt());
    }

    public int[][] next2DIntArray(int n, int m) {
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextIntArray(m);
        }
        return result;
    }

    public int[][] next2DIntArray() {
        return next2DIntArray(nextInt(), nextInt());
    }

    public long[] nextLongArray(int count) {
        long[] result = new long[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextLong();
        }
        return result;
    }

    public long[] nextLongArray() {
        return nextLongArray(nextInt());
    }

    public long[][] next2DLongArray(int n, int m) {
        long[][] result = new long[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextLongArray(m);
        }
        return result;
    }

    public long[][] next2DLongArray() {
        return next2DLongArray(nextInt(), nextInt());
    }

    public String[] nextStringArray(int count) {
        String[] result = new String[count];
        for (int i = 0; i < count; i++) {
            result[i] = next();
        }
        return result;
    }

    public String[] nextStringArray() {
        return nextStringArray(nextInt());
    }

    public String[][] next2DStringArray(int n, int m) {
        String[][] result = new String[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextStringArray(m);
        }
        return result;
    }

    public double[] nextDoubleArray(int count) {
        double[] result = new double[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextDouble();
        }
        return result;
    }

    public double[] nextDoubleArray() {
        return nextDoubleArray(nextInt());
    }

    public double[][] next2DDoubleArray(int n, int m) {
        double[][] result = new double[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextDoubleArray(m);
        }
        return result;
    }

    public double[][] next2DDoubleArray() {
        return next2DDoubleArray(nextInt(), nextInt());
    }

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

    public char[] nextCharArray(int count) {
        char[] result = new char[count];
        for (int i = 0; i < count; i++) {
            result[i] = nextChar();
        }
        return result;
    }

    public char[][] next2DCharArray(int n) {
        char[][] result = new char[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextCharArray();
        }
        return result;
    }

    public char[][] next2DCharArray(int n, int m) {
        char[][] result = new char[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextCharArray(m);
        }
        return result;
    }

    public void close() {
        try {
            stream.close();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

}

class OutputWriter {
    private PrintWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void flush() {
        writer.flush();
    }

    public void println(long x) {
        writer.println(x);
    }

    public void print(double d) {
        writer.print(d);
    }

    public void println(int i) {
        writer.println(i);
    }

    public PrintWriter format(Locale l, String format, Object... args) {
        return writer.format(l, format, args);
    }

    public void println(char x) {
        writer.println(x);
    }

    public void print(int i) {
        writer.print(i);
    }

    public void print(char[] s) {
        writer.print(s);
    }

    public void println(float x) {
        writer.println(x);
    }

    public PrintWriter printf(String format, Object... args) {
        return writer.printf(format, args);
    }

    public PrintWriter append(char c) {
        return writer.append(c);
    }

    public PrintWriter append(CharSequence csq) {
        return writer.append(csq);
    }

    public void println(Object x) {
        writer.println(x);
    }

    public void print(Object obj) {
        writer.print(obj);
    }

    public void print(long l) {
        writer.print(l);
    }

    public boolean checkError() {
        return writer.checkError();
    }

    public void println() {
        writer.println();
    }

    public void println(boolean x) {
        writer.println(x);
    }

    public PrintWriter format(String format, Object... args) {
        return writer.format(format, args);
    }

    public void println(double x) {
        writer.println(x);
    }

    public void println(String x) {
        writer.println(x);
    }

    public void println(char[] x) {
        writer.println(x);
    }

    public void print(char c) {
        writer.print(c);
    }

    public void write(String s, int off, int len) {
        writer.write(s, off, len);
    }

    public void write(char[] buf) {
        writer.write(buf);
    }

    public void print(boolean b) {
        writer.print(b);
    }

    public void write(char[] buf, int off, int len) {
        writer.write(buf, off, len);
    }

    public void close() {
        writer.close();
    }

    public void print(String s) {
        writer.print(s);
    }

    public PrintWriter printf(Locale l, String format, Object... args) {
        return writer.printf(l, format, args);
    }

    public void print(float f) {
        writer.print(f);
    }

    public void write(int c) {
        writer.write(c);
    }

    public PrintWriter append(CharSequence csq, int start, int end) {
        return writer.append(csq, start, end);
    }

    public void write(String s) {
        writer.write(s);
    }

    public void printItems(Object... items) {
        for (int i = 0; i < items.length; i++) {
            if (i != 0) {
                print(' ');
            }
            print(items[i]);
        }
    }

    public void printLine(Object... items) {
        printItems(items);
        println();
    }

    public void printItems(int[] items) {
        for (int i = 0; i < items.length; i++) {
            if (i != 0) {
                print(' ');
            }
            print(items[i]);
        }
    }

    public void printLine(int[] items) {
        printItems(items);
        println();
    }

    public void printItems(long[] items) {
        for (int i = 0; i < items.length; i++) {
            if (i != 0) {
                print(' ');
            }
            print(items[i]);
        }
    }

    public void printLine(long[] items) {
        printItems(items);
        println();
    }

    public void printItems(double[] items) {
        for (int i = 0; i < items.length; i++) {
            if (i != 0) {
                print(' ');
            }
            print(items[i]);
        }
    }

    public void printLine(double[] items) {
        printItems(items);
        println();
    }

}

class Rational extends Number implements Comparable<Rational> {
    public final long numerator;
    public final long denominator;

    public static Rational ZERO = new Rational(0, 1);
    public static Rational ONE = new Rational(1, 1);

    public Rational(long numerator, long denominator) {
        if (denominator == 0) {
            throw new IllegalArgumentException();
        }
        if (numerator == 0) {
            this.denominator = 1;
            this.numerator = 0;
            return;
        }
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        long g = NumberUtils.gcd(numerator, denominator);
        numerator /= g;
        denominator /= g;
        this.numerator = numerator;
        this.denominator = denominator;
    }

    public Rational(long numerator) {
        this.numerator = numerator;
        denominator = 1;
    }

    public static Rational valueOf(long val) {
        return new Rational(val, 1);
    }

    public Rational add(Rational val) {
        return new Rational(numerator * val.denominator + denominator * val.numerator, denominator * val.denominator);
    }

    public Rational subtract(Rational val) {
        return new Rational(numerator * val.denominator - denominator * val.numerator, denominator * val.denominator);
    }

    public Rational multiply(Rational val) {
        return new Rational(numerator * val.numerator, denominator * val.denominator);
    }

    public Rational divide(Rational val) {
        if (val.numerator == 0) {
            throw new ArithmeticException("/ by zero");
        }
        return new Rational(numerator * val.denominator, denominator * val.numerator);
    }

    public int intValue() {
        return (int) (numerator / denominator);
    }

    public long longValue() {
        return numerator / denominator;
    }

    public float floatValue() {
        return (float) numerator / denominator;
    }

    public double doubleValue() {
        return (double) numerator / denominator;
    }

    public String toString() {
        if (denominator == 1) {
            return Long.toString(numerator);
        }
        return numerator + "/" + denominator;
    }

    public int compareTo(Rational val) {
        return NumberUtils.longCompare(numerator * val.denominator, val.numerator * denominator);
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Rational that = (Rational) o;

        if (denominator != that.denominator) return false;
        if (numerator != that.numerator) return false;

        return true;
    }

    public int hashCode() {
        int result = (int) (numerator ^ (numerator >>> 32));
        result = 31 * result + (int) (denominator ^ (denominator >>> 32));
        return result;
    }
}

class NumberUtils {
    public static int upDiv(int a, int b) {
        return a % b == 0 ? (a / b) : (a / b + 1);
    }

    public static long upDiv(long a, long b) {
        return a % b == 0 ? (a / b) : (a / b + 1);
    }

    public static long factorial(int num) {
        long result = 1;
        for (int i = 1; i <= num; i++) {
            result *= i;
        }
        return result;
    }

    public static int sqr(int x) {
        return x * x;
    }

    public static long sqr(long x) {
        return x * x;
    }

    public static double sqr(double x) {
        return x * x;
    }

    public static int gcd(int a, int b) {
        if (a == 0 && b == 0) {
            throw new IllegalArgumentException();
        }
        return gcdImpl(Math.abs(a), Math.abs(b));
    }

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

    public static long gcd(long a, long b) {
        if (a == 0 && b == 0) {
            throw new IllegalArgumentException();
        }
        return gcdImpl(Math.abs(a), Math.abs(b));
    }

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

    public static long lcm(int a, int b) {
        return ((long) a / gcd(a, b)) * b;
    }

    public static long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }

    public static boolean checkBit(int mask, int bit) {
        return (mask & (1 << bit)) != 0;
    }

    public static boolean checkBit(long mask, int bit) {
        return (mask & (1l << bit)) != 0;
    }

    public static long powMod(long a, long b, long mod) {
        if (b < 0 || mod <= 0)
            throw new IllegalArgumentException();
        a %= mod;
        if (a < 0)
            a += mod;
        return powModImpl(a, b, mod);
    }

    private static long powModImpl(long a, long b, long mod) {
        if (b == 0) {
            return 1L;
        }
        long result = powModImpl(a, b >> 1, mod);
        result = (result * result) % mod;
        if (b % 2 == 1) {
            result = (result * a) % mod;
        }
        return result;
    }

    public static int[] getDivisors(int x) {
        if (x < 0) {
            throw new IllegalArgumentException();
        }
        IntArrayBuilder result = new IntArrayBuilder();
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                result.append(i);
                if (i * i < x) {
                    result.append(x / i);
                }
            }
        }
        int[] toReturn = result.toIntArray();
        Arrays.sort(toReturn);
        return toReturn;
    }

    public static <T extends Comparable<T>> T min(T a, T b) {
        return a.compareTo(b) <= 0 ? a : b;
    }

    public static <T extends Comparable<T>> T max(T a, T b) {
        return a.compareTo(b) >= 0 ? a : b;
    }

    public static int intCompare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

    public static int longCompare(long x, long y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

    public static int twoPowerCeil(int num) {
        if (num < 0) throw new IllegalArgumentException();
        if (num == 0) return 1;
        int result = Integer.highestOneBit(num);
        if (result < num) result <<= 1;
        return result;
    }

    public static int twoPowerFloor(int num) {
        if (num <= 0) throw new IllegalArgumentException();
        return Integer.highestOneBit(num);
    }

    public static int logTwoCeil(int num) {
        return Integer.numberOfTrailingZeros(twoPowerCeil(num));
    }

    public static int logTwoFloor(int num) {
        return Integer.numberOfTrailingZeros(twoPowerFloor(num));
    }

    public static int[] generatePrimeTable(int num) {
        return generateBothPrime(num).second;
    }

    public static Pair<boolean[], int[]> generateBothPrime(int num) {
        boolean[] isPrime = generateIsPrime(num);
        IntArrayBuilder builder = new IntArrayBuilder();
        for (int i = 0; i < isPrime.length; i++) {
            if (isPrime[i])
                builder.append(i);
        }
        return Pair.makePair(isPrime, builder.toIntArray());
    }

    public static boolean[] generateIsPrime(int num) {
        if (num < 0) throw new IllegalArgumentException();
        if (num == 1) return new boolean[]{false, false};
        boolean[] isPrime = new boolean[num + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }

    public static Pair<long[], int[]> getFactors(long num) {
        LongArrayBuilder factor = new LongArrayBuilder();
        IntArrayBuilder time = new IntArrayBuilder();
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                factor.append(i);
                int curTime = 0;
                do {
                    curTime++;
                    num /= i;
                } while (num % i == 0);
                time.append(curTime);
            }
        }
        if (num > 1) {
            factor.append(num);
            time.append(1);
        }
        return Pair.makePair(factor.toLongArray(), time.toIntArray());
    }

    public static long[][] generateBinomialCoefficients(int n, long module) {
        long[][] result = new long[n + 1][n + 1];
        if (module == 1)
            return result;
        for (int i = 0; i <= n; i++) {
            result[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
                if (result[i][j] >= module)
                    result[i][j] -= module;
            }
        }
        return result;
    }

    public static int sgn(int num) {
        return num < 0 ? -1 : (num > 0 ? 1 : 0);
    }

    public static long[][] generateBinomialCoefficients(int n) {
        long[][] result = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            result[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
        }
        return result;
    }

    public static long[] generateFactorial(int count, long module) {
        long[] result = new long[count + 1];
        if (module == -1) {
            if (count != 0)
                result[0] = 1;
            for (int i = 1; i <= count; i++)
                result[i] = result[i - 1] * i;
        } else {
            if (count != 0)
                result[0] = 1 % module;
            for (int i = 1; i <= count; i++)
                result[i] = (result[i - 1] * i) % module;
        }
        return result;
    }

    public static long[] generateReverse(int count, long module) {
        if (count < 0)
            throw new IllegalArgumentException();
        long[] result = new long[count + 1];
        if (count > 0)
            result[1] = 1;
        for (int i = 2; i <= count; i++)
            result[i] = (module - module / i * result[((int) (module % i))] % module) % module;
        return result;
    }

    public static long[] generateReverseFactorials(int count, long module) {
        if (count < 0)
            throw new IllegalArgumentException();
        long[] result = generateReverse(count, module);
        result[0] = 1;
        for (int i = 1; i <= count; i++)
            result[i] = result[i] * result[i - 1] % module;
        return result;
    }
}

class IntArrayBuilder {
    int[] data;
    int length;
    int capacity;

    public IntArrayBuilder() {
        this(16);
    }

    public IntArrayBuilder(int initialCapacity) {
        this.capacity = initialCapacity;
        length = 0;
        data = new int[initialCapacity];
    }

    private void ensureCapacity(int neededCapacity) {
        while (neededCapacity > capacity) {
            capacity = (capacity << 1) + 1;
        }
        if (data.length < capacity) {
            data = Arrays.copyOf(data, capacity);
        }
    }

    public IntArrayBuilder append(int item) {
        ensureCapacity(length + 1);
        data[length++] = item;
        return this;
    }

    public IntArrayBuilder append(int[] items) {
        ensureCapacity(length + items.length);
        System.arraycopy(items, 0, data, length, items.length);
        length += items.length;
        return this;
    }

    public int[] toIntArray() {
        return ArrayUtils.copyOf(data, length);
    }


}

class Pair<A,B> implements Comparable<Pair<A, B>> {
    public final A first;
    public final B second;

    public Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }

    public static <A, B> Pair<A, B> makePair(A first, B second) {
        return new Pair<A, B>(first, second);
    }

    public int compareTo(Pair<A, B> anotherPair) {
        //noinspection unchecked
        int result = ((Comparable<A>)first).compareTo(anotherPair.first);
        if (result != 0) {
            return result;
        }
        //noinspection unchecked
        return ((Comparable<B>)second).compareTo(anotherPair.second);
    }


    public String toString() {
        return "(" + first + ", " + second + ")";
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Pair pair = (Pair) o;

        if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
        if (second != null ? !second.equals(pair.second) : pair.second != null) return false;

        return true;
    }

    public int hashCode() {
        int result = first != null ? first.hashCode() : 0;
        result = 31 * result + (second != null ? second.hashCode() : 0);
        return result;
    }
}

class LongArrayBuilder {
    long[] data;
    int length;
    int capacity;

    public LongArrayBuilder() {
        this(16);
    }
    
    public LongArrayBuilder(int initialCapacity) {
        this.capacity = initialCapacity;
        length = 0;
        data = new long[initialCapacity];
    }

    private void ensureCapacity(int neededCapacity) {
        while (neededCapacity > capacity) {
            capacity = (capacity << 1) + 1;
        }
        if (data.length < capacity) {
            data = Arrays.copyOf(data, capacity);
        }
    }

    public LongArrayBuilder append(long item) {
        ensureCapacity(length + 1);
        data[length++] = item;
        return this;
    }

    public LongArrayBuilder append(long[] items) {
        ensureCapacity(length + items.length);
        System.arraycopy(items, 0, data, length, items.length);
        length += items.length;
        return this;
    }

    public long[] toLongArray() {
        return ArrayUtils.copyOf(data, length);
    }


}

class ArrayUtils {

    public static int max(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.max(result, array[i]);
        }
        return result;
    }

    public static long max(long[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        long result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.max(result, array[i]);
        }
        return result;
    }

    public static double max(double[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        double result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.max(result, array[i]);
        }
        return result;
    }

    public static int min(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.min(result, array[i]);
        }
        return result;
    }

    public static double min(double[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        double result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.min(result, array[i]);
        }
        return result;
    }

    public static long min(long[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }
        long result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.min(result, array[i]);
        }
        return result;
    }

    public static int maxIndex(int[] array) {
        int maxNumber = max(array);
        for (int i = 0; i < array.length; i++) {
            if (array[i] == maxNumber) {
                return i;
            }
        }
        return -1;
    }

    public static int minIndex(int[] array) {
        int minNumber = min(array);
        for (int i = 0; i < array.length; i++) {
            if (array[i] == minNumber) {
                return i;
            }
        }
        return -1;
    }

    public static void readIntArrays(InputReader in, int[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                arrays[j][i] = in.nextInt();
            }
        }
    }

    public static void readDoubleArrays(InputReader in, double[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                arrays[j][i] = in.nextDouble();
            }
        }
    }



    public static void readLongArrays(InputReader in, long[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                arrays[j][i] = in.nextLong();
            }
        }
    }

    public static void readStringArrays(InputReader in, String[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                arrays[j][i] = in.next();
            }
        }
    }

    public static void readGraphArrays(InputReader in, int[] from, int[] to, long[] weight) {
        for (int i = 0; i < from.length; i++) {
            from[i] = in.nextInt();
            to[i] = in.nextInt();
            weight[i] = in.nextLong();
        }
    }

    public static void readArrays(InputReader in, Object... arrays) {
        int length = java.lang.reflect.Array.getLength(arrays[0]);
        for (int i = 0; i < length; i++) {
            for (Object array : arrays) {
                if (array instanceof int[]) {
                    java.lang.reflect.Array.setInt(array, i, in.nextInt());
                } else if (array instanceof long[]) {
                    java.lang.reflect.Array.setLong(array, i, in.nextLong());
                } else if (array instanceof double[]) {
                    java.lang.reflect.Array.setDouble(array, i, in.nextDouble());
                } else if (array instanceof String[]) {
                    java.lang.reflect.Array.set(array, i, in.next());
                } else if (array instanceof char[]) {
                    java.lang.reflect.Array.setChar(array, i, in.nextChar());
                } else throw new IllegalArgumentException();
            }
        }
    }

    public static void fill(int[][] array, int val) {
        for (int[] subArray : array) {
            Arrays.fill(subArray, val);
        }
    }

    public static void fill(long[][] array, long val) {
        for (long[] subArray : array) {
            Arrays.fill(subArray, val);
        }
    }

    public static void fill(boolean[][] array, boolean val) {
        for (boolean[] subArray : array) {
            Arrays.fill(subArray, val);
        }
    }

    public static void fill(int[][][] array, int val) {
        for (int[][] subArray : array) {
            ArrayUtils.fill(subArray, val);
        }
    }

    public static void fill(int[][][][] array, int val) {
        for (int[][][] subArray : array) {
            fill(subArray, val);
        }
    }

    public static void fill(int[][][][][] array, int val) {
        for (int[][][][] subArray : array) {
            fill(subArray, val);
        }
    }

    public static void fill(long[][][] array, long val) {
        for (long[][] subArray : array) {
            ArrayUtils.fill(subArray, val);
        }
    }

    public static void fill(boolean[][][] array, boolean val) {
        for (boolean[][] subArray : array) {
            ArrayUtils.fill(subArray, val);
        }
    }

    public static void fill(long[][][][] array, int val) {
        for (long[][][] subArray : array) {
            ArrayUtils.fill(subArray, val);
        }
    }

    public static void decreaseByOne(int[]... arrays) {
        for (int[] array : arrays) {
            for (int i = 0; i < array.length; i++) {
                array[i]--;
            }
        }
    }

    public static void increaseByOne(int[]... arrays) {
        for (int[] array : arrays) {
            for (int i = 0; i < array.length; i++) {
                array[i]++;
            }
        }
    }

    public static void increaseByOne(Integer[]... arrays) {
        for (Integer[] array : arrays) {
            for (int i = 0; i < array.length; i++) {
                array[i]++;
            }
        }
    }

    public static int[] reverse(int[] array) {
        int a = 0, b = array.length - 1;
        while (a < b) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            a++;
            b--;
        }
        return array;
    }

    public static long[] reverse(long[] array) {
        int a = 0, b = array.length - 1;
        while (a < b) {
            long temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            a++;
            b--;
        }
        return array;
    }
    public static boolean[] reverse(boolean[] array) {
        int a = 0, b = array.length - 1;
        while (a < b) {
            boolean temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            a++;
            b--;
        }
        return array;
    }

    public static char[] reverse(char[] array) {
        int a = 0, b = array.length - 1;
        while (a < b) {
            char temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            a++;
            b--;
        }
        return array;
    }

    public static int[] unique(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                count++;
            }
        }
        int[] result = new int[count];
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                result[count++] = array[i];
            }
        }
        return result;
    }

    public static long[] unique(long[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                count++;
            }
        }
        long[] result = new long[count];
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                result[count++] = array[i];
            }
        }
        return result;
    }

    public static double[] unique(double[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                count++;
            }
        }
        double[] result = new double[count];
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                result[count++] = array[i];
            }
        }
        return result;
    }

    public static char[] unique(char[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                count++;
            }
        }
        char[] result = new char[count];
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || array[i - 1] != array[i]) {
                result[count++] = array[i];
            }
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    public static Object[] unique(Object[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || !array[i - 1].equals(array[i])) {
                count++;
            }
        }
        Object[] result = new Object[count];
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (i == 0 || !array[i - 1].equals(array[i])) {
                result[count++] = array[i];
            }
        }
        return result;
    }

    public static String toString(boolean[] array) {
        StringBuilder builder = new StringBuilder();
        for (boolean item : array) {
            builder.append(item ? '1' : '0');
        }
        return builder.toString();
    }



    public static char[][] to2DCharArray(String[] array) {
        char[][] result = new char[array.length][];
        for (int i = 0; i < array.length; i++) {
            result[i] = array[i].toCharArray();
        }
        return result;
    }

    public static long sum(int[] array) {
        long result = 0;
        for (int i : array) {
            result += i;
        }
        return result;
    }

    public static long sum(long[] array) {
        long result = 0;
        for (long i : array) {
            result += i;
        }
        return result;
    }

    public static double sum(double[] array) {
        double result = 0;
        for (double i : array) {
            result += i;
        }
        return result;
    }

    public static String sum(String[] array) {
        StringBuilder result = new StringBuilder();
        for (String s : array) {
            result.append(s);
        }
        return result.toString();
    }

    public static int[][] deepCopy(int[][] origin) {
        if (origin == null)
            return null;
        int[][] result = new int[origin.length][];
        for (int i = 0; i < result.length; i++) {
            result[i] = origin[i] == null ? null : origin[i].clone();
        }
        return result;
    }

    public static long[][] deepCopy(long[][] origin) {
        if (origin == null)
            return null;
        long[][] result = new long[origin.length][];
        for (int i = 0; i < result.length; i++) {
            result[i] = origin[i] == null ? null : origin[i].clone();
        }
        return result;
    }

    public static boolean[][] deepCopy(boolean[][] origin) {
        if (origin == null)
            return null;
        boolean[][] result = origin.clone();
        for (int i = 0; i < result.length; i++) {
            result[i] = origin[i] == null ? null : origin[i].clone();
        }
        return result;
    }

    public static List<Integer> asList(int[] array) {
        return new IntList(array);
    }

    public static long[] getSum(int[] array) {
        long[] result = new long[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            result[i + 1] = result[i] + array[i];
        }
        return result;
    }

    public static long[] getSum(long[] array) {
        long[] result = new long[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            result[i + 1] = result[i] + array[i];
        }
        return result;
    }

    private static long[][] getSum(int[][] array) {
        int height = array.length;
        int width = array[0].length;
        long[][] result = new long[height + 1][width + 1];
        for (int i = 0; i < height; i++) {
            long curSum = 0;
            for (int j = 0; j < width; j++) {
                curSum += array[i][j];
                result[i + 1][j + 1] = result[i][j + 1] + curSum;
            }
        }
        return result;
    }

    private static long[][] getSum(long[][] array) {
        int height = array.length;
        int width = array[0].length;
        long[][] result = new long[height + 1][width + 1];
        for (int i = 0; i < height; i++) {
            long curSum = 0;
            for (int j = 0; j < width; j++) {
                curSum += array[i][j];
                result[i + 1][j + 1] = result[i][j + 1] + curSum;
            }
        }
        return result;
    }

    public static void fill(double[][] array, double value) {
        for (double[] subArray : array) {
            Arrays.fill(subArray, value);
        }
    }

    public static void fill(double[][][] array, double value) {
        for (double[][] subArray : array) {
            fill(subArray, value);
        }
    }

    public static void fill(char[][] array, char value) {
        for (char[] subArray : array) {
            Arrays.fill(subArray, value);
        }
    }

    public static int getTrueCount(boolean[] array) {
        int result = 0;
        for (boolean b : array) {
            if (b) result++;
        }
        return result;
    }

    public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                Math.min(original.length, newLength));
        return copy;
    }

    public static double[] copyOf(double[] original, int newLength) {
        double[] copy = new double[newLength];
        System.arraycopy(original, 0, copy, 0,
                Math.min(original.length, newLength));
        return copy;
    }

    public static long[] copyOf(long[] original, int newLength) {
        long[] copy = new long[newLength];
        System.arraycopy(original, 0, copy, 0,
                Math.min(original.length, newLength));
        return copy;
    }


    private static class IntList extends AbstractList<Integer> implements RandomAccess {

        int[] array;

        private IntList(int[] array) {
            this.array = array;
        }

        public Integer get(int index) {
            return array[index];
        }

        public Integer set(int index, Integer element) {
            int result = array[index];
            array[index] = element;
            return result;
        }

        public int size() {
            return array.length;
        }
    }

    public static List<Long> asList(long[] array) {
        return new LongList(array);
    }

    private static class LongList extends AbstractList<Long> implements RandomAccess {
        long[] array;

        private LongList(long[] array) {
            this.array = array;
        }

        public Long set(int index, Long element) {
            long result = array[index];
            array[index] = element;
            return result;
        }

        public Long get(int index) {
            return array[index];
        }

        public int size() {
            return array.length;
        }
    }

    public static List<Double> asList(double[] array) {
        return new DoubleList(array);
    }

    private static class DoubleList extends AbstractList<Double> implements RandomAccess {
        double[] array;

        private DoubleList(double[] array) {
            this.array = array;
        }

        public Double set(int index, Double element) {
            double result = array[index];
            array[index] = element;
            return result;
        }

        public Double get(int index) {
            return array[index];
        }

        public int size() {
            return array.length;
        }
    }

    public static List<Character> asList(char[] array) {
        return new CharList(array);
    }

    private static class CharList extends AbstractList<Character> implements RandomAccess {
        char[] array;

        private CharList(char[] array) {
            this.array = array;
        }

        public Character set(int index, Character element) {
            char result = array[index];
            array[index] = element;
            return result;
        }

        public Character get(int index) {
            return array[index];
        }

        public int size() {
            return array.length;
        }
    }

    public static int discretization(int[]... arrays) {
        int length = 0;
        for (int[] array : arrays) {
            length += array.length;
        }
        int[] all = new int[length];
        length = 0;
        for (int[] array : arrays) {
            System.arraycopy(array, 0, all, length, array.length);
            length += array.length;
        }
        Arrays.sort(all);
        int[] uniqued = unique(all);
        for (int[] array : arrays) {
            for (int i = 0; i < array.length; i++) {
                array[i] = Arrays.binarySearch(uniqued, array[i]);
            }
        }
        return uniqued.length;
    }

    public static void safeSort(int[] array) {
        Collections.shuffle(asList(array));
        Arrays.sort(array);
    }

    public static void safeSort(double[] array) {
        Collections.shuffle(asList(array));
        Arrays.sort(array);
    }

    public static void safeSort(long[] array) {
        Collections.shuffle(asList(array));
        Arrays.sort(array);
    }

    public static void safeSort(char[] array) {
        Collections.shuffle(asList(array));
        Arrays.sort(array);
    }

    public static void safeSort(Object[] array) {
        Collections.shuffle(Arrays.asList(array));
        Arrays.sort(array);
    }

    public static long[] partialSum(long[] array) {
        int n = array.length;
        long[] result = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = result[i - 1] + array[i - 1];
        }
        return result;
    }

    public static long[] partialSum(int[] array) {
        int n = array.length;
        long[] result = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = result[i - 1] + array[i - 1];
        }
        return result;
    }

    // min i thar array[i] >= val
    public static int lowerBound(int[] array, int val) {
        int n = array.length;
        if (array[n - 1] < val)
            return n;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (array[mid] >= val)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

    public static int lowerBound(long[] array, long val) {
        int n = array.length;
        if (array[n - 1] < val)
            return n;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (array[mid] >= val)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

    // min i that array[i] > val
    public static int upperBound(int[] array, int val) {
        int n = array.length;
        if (array[n - 1] <= val)
            return n;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (array[mid] > val)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

    public static void reorder(int[] order, int[]... arrays) {
        for (int[] array : arrays) {
            if (array.length != order.length)
                throw new IllegalArgumentException();
        }
        for (int[] array : arrays) {
            int[] tmp = array.clone();
            for (int i = 0; i < order.length; i++) {
                array[i] = tmp[order[i]];
            }
        }
    }


    public static void reorder(int[] order, long[]... arrays) {
        for (long[] array : arrays) {
            if (array.length != order.length)
                throw new IllegalArgumentException();
        }
        for (long[] array : arrays) {
            long[] tmp = array.clone();
            for (int i = 0; i < order.length; i++) {
                array[i] = tmp[order[i]];
            }
        }
    }

    public static void reorder(int[] order, double[]... arrays) {
        for (double[] array : arrays) {
            if (array.length != order.length)
                throw new IllegalArgumentException();
        }
        for (double[] array : arrays) {
            double[] tmp = array.clone();
            for (int i = 0; i < order.length; i++) {
                array[i] = tmp[order[i]];
            }
        }
    }

}

