class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string res;
        int i = 0, x = 0;
        while(res.size() != s.size()){
            if(indices[x] == i) {
                res += s[x];
                i++;
                x = 0;
            } else {
                x++;
            }
        }

        return res;
    }
};

//双指针简单
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        vector<int> tmp(arr), res;
        int n = arr.size();
        sort(tmp.begin(), tmp.end());
        int med = tmp[(tmp.size()-1)/2];

        bool flag = false;
        for(int i = 0; i < n; i) {
            for(int j = n-1; j >= 0; j) {
                int abs1 = abs(tmp[i] - med), abs2 = abs(tmp[j] - med);
                if(abs1 > abs2) res.push_back(tmp[i++]);
                else if(abs1 < abs2) res.push_back(tmp[j--]);
                else {
                    if(tmp[i] > tmp[j]) res.push_back(tmp[i++]);
                    else res.push_back(tmp[j--]);
                }
                if(res.size() == k) {
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> res, tmp1, tmp2;
        for(int i = 0; i < nums.size(); i++) {
            if(i < n) tmp1.push_back(nums[i]);
            else tmp2.push_back(nums[i]);
        }
        for(int i = 0; i < n; i++) {
            res.push_back(tmp1[i]);
            res.push_back(tmp2[i]);
        }
        return res;
    }
};

Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true
Example 2:

Input: S = "0110", N = 4
Output: false

Note:

1 <= S.length <= 1000
1 <= N <= 10^9

class Solution {
public:

    string to_str(int N) {
        string num = "";
        while(N) {
            int tmp = N % 2;
            N /= 2;
            num += tmp + '0';
        }
        reverse(num.begin(), num.end());
        return num;
    }
    bool queryString(string S, int N) {
        for(int i = 1; i <= N; i++) {
            if(S.find(to_str(i)) == -1)) 
                return false;
        }
        return true;
    }
};

/*
--------------------
h[N]-牛高
ans[N]-记录答案
tr[N]-线段树存储
--------------------
int lowbit(int x);
void add(int x, int c);
int sum(int x);
---------------------
1.从剩余的数中找到第k小的数~找到一个最大的x使得k==sum(x)
2.删除某个数
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
int h[N], res[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

int sum(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main() {
    cin >> n;

    for(int i = 2; i <= n; i++) cin >> h[i];

    for(int i = 1; i <= n ;i++) tr[i] = lowbit(i);

    for(int i = n; i; i--) {
        int k = h[i] + 1;
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        res[i] = r;
        add(r, -1);
    }

    for(int i = 1; i <= n; i++) cout << res[i] << endl;

    return 0;
}

/*
--------------------
h[N]-牛高
ans[N]-记录答案
tr[N]-线段树存储
--------------------
int lowbit(int x);
void add(int x, int c);
int sum(int x);
---------------------
1.从剩余的数中找到第k小的数~找到一个最大的x使得k==sum(x)
2.删除某个数
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
int h[N], res[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

int sum(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main() {
    cin >> n;

    for(int i = 2; i <= n; i++) cin >> h[i];

    for(int i = 1; i <= n ;i++) tr[i] = lowbit(i);

    for(int i = n; i; i--) {
        int k = h[i] + 1;
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        res[i] = r;
        add(r, -1);
    }

    for(int i = 1; i <= n; i++) cout << res[i] << endl;

    return 0;
}

/*
-----------
tr1[i]-bi的前缀和数组
tr2[i]-i*bi的前缀和数组
a[1~x] == (x+1) * b[1~x](即tr1[x]) - tr2[i]
-----------
int lowbit(int x);
void add(LL tr[], int x, LL c);
LL sum(LL tr[], int x);
LL prefix_sum(int x);
*/
#include<iostream>
#include<cstring>
#include<algorithm>

typedef long long LL;

using namespace std;

const int N = 1e5+10;
int n, m;
LL a[N], tr1[N], tr2[N];

int lowbit(int x) {
    return x & -x;
}

void add(LL tr[], int x, LL c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x) {
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL prefix_sum(int x) {
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> a[i];

    for(int i = 1; i <= n; i++) {
        int b = a[i] - a[i-1];
        add(tr1, i, b);
        add(tr2, i, (LL)b*i);
    }
    while(m--) {
        char op[2];
        int l, r, d;

        cin >> op;
        if(op[0] == 'Q') {
            cin >> l >> r;
            cout << prefix_sum(r) - prefix_sum(l-1) << endl;
        } else {
            cin >> l >> r >> d;
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r+1, -d), add(tr2, r+1, (r+1) * -d);
        }
    }
    return 0;
}

// 这破题我居然写了半小时，吐了
// class Solution {
// public:
//     int isPrefixOfWord(string sentence, string searchWord) {
//     // typedef pair<string, int> sent[110];
//     int res = -1,cnt = 1;;
//     for(int i = 0; i < sentence.size(); i++) {
//         string tmp;
//         if(sentence[i] != ' ') continue;
//         else if(sentence[i] == ' ' || i == sentence.size()){
//             tmp = sentence.substr(0, i-1);
//             sentence = sentence.substr(i+1);
//             cout << "---" << cnt << ' ' << tmp << ' ' << sentence << endl;
//             for(int i = 0; i < searchWord.size(); i++) {
//                 if(searchWord[i] != tmp[i]) {
//                     break;
//                 }
//                 if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) res = cnt;
//             } 
//             cnt++;
//             // sent[cnt] = make_pair(tmp, cnt++);
//             // sent[cnt].first = tmp;
//             // sent[cnt].second = cnt++; 
//         } 
//     }
//     // for(int i = 1; i <= cnt; i++) {
//     //     for(int j = 0; j < searchWord.size(); j++) {
//     //         if(sent[i].first[j] != searchWord[j]) continue;
//     //         if(j == searchWord.size() - 1) res = sent[i].second;
//     //     }
//     // } 
//     // cout << res << endl;
//     return res;
// }
// };
class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
    int res = -1,cnt = 1;
    for(int i = 0; i < sentence.size(); i++) {
        string tmp;
        if(sentence[i] == ' '){
            tmp = sentence.substr(0, i);
            sentence = sentence.substr(i+1);
            // cout << "---" << cnt << "---" << tmp << "---" << sentence << endl;

            for(int i = 0; i < searchWord.size(); i++) {
                if(searchWord[i] != tmp[i]) {
                    break;
                }
                if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) return cnt;

            } 

            for(int i = 0; i < searchWord.size(); i++) {
                if(sentence[i] != searchWord[i]) {
                    break;
                }
                if(sentence[i] == searchWord[i] && i == searchWord.size() - 1) return cnt+1;
            }
            cnt++;
            i = 0;
        } 
    }
    return res;
}
};