#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

inline void set_file_IO(string);
inline void close_IO(void);
inline int read(void);
inline void work(void);

class segment_tree {
    private:
        static const int segmentTreeSize = 400000;
        struct meta {
            int leftBound, rightBound, tag, value;
        } node[segmentTreeSize];
        virtual inline void downTag(int index) {
            if (!node[index].tag) {
                return;
            }
            node[index << 1].tag   += node[index].tag;
            node[index << 1].value += node[index].tag;
            node[(index << 1) + 1].tag   += node[index].tag;
            node[(index << 1) + 1].value += node[index].tag;
            node[index].tag = 0;
        }
    public:
        virtual inline void build(int index, int leftBound, int rightBound) {
            node[index].leftBound  = leftBound;
            node[index].rightBound = rightBound;
            node[index].value      = 0;
            node[index].tag        = 0;
            if (leftBound == rightBound) {
                return;
            }
            int mid = (leftBound + rightBound) >> 1;
            build( index << 1     , leftBound, mid       );
            build((index << 1) + 1, mid + 1  , rightBound);
        }
        virtual inline void edit(int index, int leftBound, int rightBound, int delta) {
            if (leftBound <= node[index].leftBound && node[index].rightBound <= rightBound) {
                node[index].value += delta;
                node[index].tag   += delta;
                return;
            }
            downTag(index);
            int mid = (node[index].leftBound + node[index].rightBound) >> 1;
            if (leftBound <= mid) {
                edit(index << 1, leftBound, rightBound, delta);
            }
            if (rightBound > mid) {
                edit((index << 1) + 1, leftBound, rightBound, delta);
            }
            node[index].value = node[index << 1].value + node[(index << 1) + 1].value;
        }
        virtual inline int request(int index, int leftBound, int rightBound) {
            if (leftBound <= node[index].leftBound && node[index].rightBound <= rightBound) {
                return node[index].value;
            }
            downTag(index);
            int mid = (node[index].leftBound + node[index].rightBound) >> 1, result = 0;
            if (leftBound <= mid) {
                result += request(index << 1, leftBound, rightBound);
            }
            if (rightBound > mid) {
                result += request((index << 1) + 1, leftBound, rightBound);
            }
            return result;
        }
};