给定一个长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

1. C l r d，表示把 $A[l],A[l+1],…,A[r]$ 都加上 $d$。
2. Q l r，表示询问数列中第 $l \sim r$ 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $A[i]$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1 \le N,M \le 10^5$,
$|d| \le 10000$,
$|A[i]| \le 10^9$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

4
55
9
15

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int w[N];

struct Node
{
    int l, r;
    long long sum, add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    if (tr[u].add)
    {
        tr[u << 1].add += tr[u].add, tr[u << 1].sum += (long long) (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
        tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += (long long) (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
        tr[u].add = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (long long) (tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

long long query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    long long res = 0;
    if (l <= mid ) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> w[i];
    build(1, 1, n);
    char op;
    int l, r, d;
    while (m --)
    {
        cin >> op >> l >> r;
        if (op == 'C')
        {
            cin >> d;
            modify(1, l, r, d);
        }
        else cout << query(1, l, r) << '\n';
    }

    return 0;
}