public abstract class SegmentsTree {

    public abstract int defaultDelta();
    public abstract int operation(int a, int b);
    public abstract int defaultValue();
    public abstract void change(int v, int delta);
    protected int[] func;
    protected int[] delta;
    protected int[] left;
    protected int[] right;
    protected int size;

    public SegmentsTree(int[] a) {
        size = a.length;
        func = new int[4 * size + 2];
        delta = new int[4 * size + 2];
        left = new int[4 * size + 2];
        right = new int[4 * size + 2];
        build(0, size - 1, 1, a);
    }
    private void build(int left, int right, int v, int[] a) {
        this.left[v] = left;
        this.right[v] = right;
        delta[v] = defaultDelta();
        if (left == right) {
            func[v] = a[left];
        } else {
            int middle = (left + right) >> 1;
            build(left, middle, v << 1, a);
            build(middle + 1, right, (v << 1) + 1, a);
            func[v] = operation(func[v << 1], func[(v << 1) + 1]);
        }
    }
    public void change(int left, int right, int delta) {
        change(0, size - 1, left, right, 1, delta);
    }
    private void change(int lTree, int rTree, int left, int right, int v, int delta) {
        if (rTree < left || right < lTree)
            return;
        push(v);
        if (left <= lTree && rTree <= right) {
            change(v, delta);
        } else {
            int middle = (lTree + rTree) >> 1;
            change(lTree, middle, left, right, v << 1, delta);
            change(middle + 1, rTree, left, right, (v << 1) + 1, delta);
            func[v] = operation(func[v << 1], func[(v << 1) + 1]);
        }
    }
    public int get(int left, int right) {
        return get(0, size - 1, left, right, 1);
    }

    private int get(int lTree, int rTree, int left, int right, int v) {
        if (rTree < left || right < lTree)
            return defaultValue();
        push(v);
        if (left <= lTree && rTree <= right)
            return func[v];
        else {
            int middle = (lTree + rTree) >> 1;
            return operation(
                    get(lTree, middle, left, right, v << 1),
                    get(middle + 1, rTree, left, right, (v << 1) + 1)
            );
        }
    }
    private void push(int v) {
        if (delta[v] != defaultDelta()) {
            if ((v << 1) < func.length)
                change(v << 1, delta[v]);
            if ((v << 1) + 1 < func.length)
                change((v << 1) + 1, delta[v]);
            delta[v] = defaultDelta();
        }
    }
}