1
#include<bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
using i128 = __int128;
5
const i64 INF = 0x3f3f3f3f3f3f3f3f;
6
const i64 mod = 998244353;
7
const int mx = 1e6 + 1000;
8
i64 fac[mx + 1], invfac[mx + 1];
9
i64 fastpow(i64 x, i64 p) {
10
    i64 ans = 1;
11
    x %= mod;
12
    while (p) {
13
        if (p & 1) ans = ans * x % mod;
14
        x = x * x % mod;
15
        p >>= 1;
16
    }
17
    return ans;
18
}
19
i64 inv(i64 x) {
20
    return fastpow(x, mod - 2);
21
}
22
i64 c(i64 a, i64 b) {
23
    if(b < 0 || b > a) return 0;
24
    return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
25
}
26

27
void init() {
28
    fac[0] = 1;
29
    for (int i = 1; i <= mx; i++) {
30
        fac[i] = fac[i - 1] * i % mod;
31
    }
32
    invfac[mx] = fastpow(fac[mx], mod - 2);
33
    for (int i = mx - 1; i >= 1; i--) {
34
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
35
    }
36
}
37

38
void solve() {
39

40
}
41
int main(){
42
    std::ios_base::sync_with_stdio(false);
43
    std::cin.tie(nullptr);
44
    init();
45
    int t = 1;
46
    cin >> t;
47
    while (t--) {
48
        solve();
49
    }
50
    return 0;
51
}

1
int find(x){
2
    int l = 0, r = n + 1;
3
    while(l + 1 < r){
4
        int mid = l + r >> 1;
5
        if(a[mid] <= q) l = mid;
6
        else r = mid;
7
    }
8
    return l;
9
}

1
ld find(ld x){
2
    ld l = -100, r = 100;
3
    while(r - l > 1e-5){
4
        ld mid = (l + r)/2;
5
        if(check(mid)) l = mid;
6
        else r = mid;
7
    }
8
    return l;
9
}

1
bool isprime(int x) {
2
    if (x == 1) return false;
3
    for (int i = 2; i * i <= x; ++i)
4
        if (x % i == 0)
5
            return false;
6
    return true;
7
}

1
const int N = 1e8 + 10;
2
bitset<N> isprime;
3
vector<int> prime;
4
void sieve() {
5
    isprime.set();
6
    isprime[0] = isprime[1] = 0;
7
    for (int i = 2; i < N; ++i) {
8
        if (isprime[i]) {
9
            prime.push_back(i);
10
            if ((i64)i * i < N) {
11
                for (int j = i * i; j < N; j += i) {
12
                    isprime[j] = 0;
13
                }
14
            }
15
        }
16
    }
17
}

1
const int N = 1e6 + 10;
2
bitset<N> isprime;
3
vector<int> prime;
4
void sieve() {
5
    isprime.set();
6
    isprime[0] = isprime[1] = 0;
7
    for (int i = 2; i < N; ++i) {
8
        if (isprime[i]) prime.push_back(i);
9
        for (int p : prime) {
10
            if (1LL * i * p >= N) break;
11
            isprime[i * p] = 0;
12
            if (i % p == 0) break;
13
        }
14
    }
15
}

1
void solve(){
2
    int n, m, s;
3
    cin >> n >> m >> s;
4
    vector<int> dist(n + 1, 1e9);
5
    vector<vector<array<int, 2>>> e(n + 1);
6
    dist[s] = 0;
7
    for(int i = 1;i <= m; ++i){
8
        int u, v, w;
9
        cin >> u >> v >> w;
10
        e[u].push_back({v, w});
11
    }
12
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> q;
13
    q.push({0, s});
14
    while(q.size()){
15
        auto [d, u] = q.top();
16
        q.pop();
17
        if(d > dist[u]) continue;
18
        for(auto [v, w] : e[u]){
19
            if(d + w < dist[v]){
20
                dist[v] = d + w;
21
                q.push({dist[v], v});
22
            }
23
        }
24
    }
25
    for(int i = 1;i <= n; ++i) cout << dist[i] << " ";
26
}

1
const int N = 202020;
2
bool vis[N];
3
vector<array<int, 2>> e[N];
4
void solve(){
5
    int n, m;
6
    cin >> n >> m;
7
    for(int i = 1;i <= m; ++i){
8
        int u, v, w;
9
        cin >> u >> v >> w;
10
        e[u].push_back({v, w});
11
        e[v].push_back({u, w});
12
    }
13
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> q;
14
    int ans = 0, cnt = 0;
15
    q.push({0, 1});
16
    while(q.size() && cnt < n){
17
        auto [w, u] = q.top();
18
        q.pop();
19
        if(vis[u]) continue;
20
        ans += w;
21
        cnt++;
22
        vis[u] = 1;
23
        for(auto [v, ww] : e[u]){
24
            if(!vis[v]) q.push({ww, v});
25
        }
26
    }
27
    if(cnt == n) cout << ans << "\n";
28
    else cout << "orz\n";
29
}

1
const int maxn = 100005;
2
i64 a[maxn], t[maxn << 2], lazy[maxn << 2];
3

4
// 1. 更新父节点：和 = 左儿子 + 右儿子
5
void Pushup(int k) {
6
    t[k] = t[k << 1] + t[k << 1 | 1];
7
}
8

9
void build(int k, int l, int r) {
10
    lazy[k] = 0;
11
    if (l == r) {
12
        t[k] = a[l];
13
        return;
14
    }
15
    int m = l + ((r - l) >> 1);
16
    build(k << 1, l, m);
17
    build(k << 1 | 1, m + 1, r);
18
    Pushup(k);
19
}
20

21
// 2. 懒标记下传：注意要乘以区间长度
22
void Pushdown(int k, int l, int r) {
23
    if (lazy[k] != 0) {
24
        int m = l + ((r - l) >> 1);
25

26
        // 下传给左儿子：加上的值 = 标记 * 左区间长度
27
        lazy[k << 1] += lazy[k];
28
        t[k << 1] += lazy[k] * (m - l + 1);
29

30
        // 下传给右儿子：加上的值 = 标记 * 右区间长度
31
        lazy[k << 1 | 1] += lazy[k];
32
        t[k << 1 | 1] += lazy[k] * (r - m);
33

34
        lazy[k] = 0;
35
    }
36
}
37

38
void update(int L, int R, i64 v, int l, int r, int k) {
39
    if (L <= l && r <= R) {
40
        lazy[k] += v;
41
        // 当前节点增加量 = v * 当前管辖的区间长度
42
        t[k] += v * (r - l + 1);
43
        return;
44
    }
45
    // 注意 Pushdown 现在需要知道当前的 l 和 r 来计算子区间长度
46
    Pushdown(k, l, r);
47
    int m = l + ((r - l) >> 1);
48
    if (L <= m) update(L, R, v, l, m, k << 1);
49
    if (R > m)  update(L, R, v, m + 1, r, k << 1 | 1);
50
    Pushup(k);
51
}
52

53
i64 query(int L, int R, int l, int r, int k) {
54
    if (L <= l && r <= R) {
55
        return t[k];
56
    }
57
    Pushdown(k, l, r);
58
    int m = l + ((r - l) >> 1);
59
    i64 res = 0; // 求和初始值为 0
60
    if (L <= m) res += query(L, R, l, m, k << 1);
61
    if (R > m)  res += query(L, R, m + 1, r, k << 1 | 1);
62
    return res;
63
}
64

65
void solve() {
66
    int n, q;
67
    if (!(cin >> n >> q)) return;
68
    for (int i = 1; i <= n; i++) cin >> a[i];
69
    build(1, 1, n);
70

71
    while (q--) {
72
        int op;
73
        cin >> op;
74
        if (op == 1) { // 区间加
75
            int x, y;
76
            i64 k;
77
            cin >> x >> y >> k;
78
            update(x, y, k, 1, n, 1);
79
        } else { // 区间求和
80
            int x, y;
81
            cin >> x >> y;
82
            cout << query(x, y, 1, n, 1) << "\n";
83
        }
84
    }
85
}

1
const int maxn = 100005;
2
i64 a[maxn], t[maxn << 2], lazy[maxn << 2];
3
// 更新父节点信息（当前是最大值 RMQ）
4
void Pushup(int k) {
5
    t[k] = max(t[k << 1], t[k << 1 | 1]);
6
}
7
// 递归建树：build(1, 1, n)
8
void build(int k, int l, int r) {
9
    lazy[k] = 0; // 习惯性初始化，防止多组数据干扰
10
    if (l == r) {
11
        t[k] = a[l];
12
        return;
13
    }
14
    int m = l + ((r - l) >> 1);
15
    build(k << 1, l, m);
16
    build(k << 1 | 1, m + 1, r);
17
    Pushup(k);
18
}
19
// 懒标记下传
20
void Pushdown(int k) {
21
    if (lazy[k] != 0) { // 如果有标记
22
        lazy[k << 1] += lazy[k];
23
        lazy[k << 1 | 1] += lazy[k];
24
        t[k << 1] += lazy[k];
25
        t[k << 1 | 1] += lazy[k];
26
        lazy[k] = 0; // 必须归零
27
    }
28
}
29
// 区间修改：update(L, R, v, 1, n, 1)
30
void update(int L, int R, i64 v, int l, int r, int k) {
31
    if (L <= l && r <= R) { // 当前节点被目标区间完全覆盖
32
        lazy[k] += v;
33
        t[k] += v;
34
        return;
35
    }
36
    Pushdown(k); // 只有不完全覆盖且需要继续往下走时才 pushdown
37
    int m = l + ((r - l) >> 1);
38
    if (L <= m) update(L, R, v, l, m, k << 1);
39
    if (R > m)  update(L, R, v, m + 1, r, k << 1 | 1);
40
    Pushup(k); // 回溯时更新
41
}
42

43
// 区间查询：query(L, R, 1, n, 1)
44
i64 query(int L, int R, int l, int r, int k) {
45
    if (L <= l && r <= R) {
46
        return t[k];
47
    }
48
    Pushdown(k);
49
    int m = l + ((r - l) >> 1);
50
    i64 res = -INF;
51
    if (L <= m) res = max(res, query(L, R, l, m, k << 1));
52
    if (R > m)  res = max(res, query(L, R, m + 1, r, k << 1 | 1));
53
    return res;
54
}
55

56
void solve() {
57
    int n, q;
58
    if (!(cin >> n >> q)) return;
59
    for (int i = 1; i <= n; i++) cin >> a[i];
60

61
    build(1, 1, n);
62

63
    while (q--) {
64
        int opt;
65
        cin >> opt;
66
        if (opt == 1) { // 修改
67
            int L, R;
68
            i64 v;
69
            cin >> L >> R >> v;
70
            update(L, R, v, 1, n, 1);
71
        } else { // 查询
72
            int L, R;
73
            cin >> L >> R;
74
            cout << query(L, R, 1, n, 1) << "\n";
75
        }
76
    }
77
}

1
const int maxn = 100005;
2
i64 a[maxn], t[maxn << 2];
3
i64 add[maxn << 2], mul[maxn << 2];
4
i64 n, m, p; // p 为模数，如果题目没要求模，可以去掉相关取模
5

6
void Pushup(int k) {
7
    t[k] = (t[k << 1] + t[k << 1 | 1]) % p;
8
}
9

10
void build(int k, int l, int r) {
11
    add[k] = 0;
12
    mul[k] = 1; // 乘法标记初始化为 1
13
    if (l == r) {
14
        t[k] = a[l] % p;
15
        return;
16
    }
17
    int mid = l + ((r - l) >> 1);
18
    build(k << 1, l, mid);
19
    build(k << 1 | 1, mid + 1, r);
20
    Pushup(k);
21
}
22

23
// 核心：下传函数
24
void push_eval(int k, int l, int r, i64 m_v, i64 a_v) {
25
    // 1. 更新当前节点的值：(值 * 乘) + (加 * 长度)
26
    t[k] = (t[k] * m_v % p + a_v * (r - l + 1) % p) % p;
27
    // 2. 更新乘法标记：旧乘 * 新乘
28
    mul[k] = mul[k] * m_v % p;
29
    // 3. 更新加法标记：(旧加 * 新乘) + 新加
30
    add[k] = (add[k] * m_v % p + a_v) % p;
31
}
32

33
void Pushdown(int k, int l, int r) {
34
    int mid = l + ((r - l) >> 1);
35
    // 把当前的 mul[k] 和 add[k] 传给左右儿子
36
    push_eval(k << 1, l, mid, mul[k], add[k]);
37
    push_eval(k << 1 | 1, mid + 1, r, mul[k], add[k]);
38
    // 标记归位
39
    mul[k] = 1;
40
    add[k] = 0;
41
}
42

43
// 区间乘法
44
void update_mul(int L, int R, i64 v, int l, int r, int k) {
45
    if (L <= l && r <= R) {
46
        push_eval(k, l, r, v, 0); // 加法增量为 0
47
        return;
48
    }
49
    Pushdown(k, l, r);
50
    int mid = l + ((r - l) >> 1);
51
    if (L <= mid) update_mul(L, R, v, l, mid, k << 1);
52
    if (R > mid)  update_mul(L, R, v, mid + 1, r, k << 1 | 1);
53
    Pushup(k);
54
}
55

56
// 区间加法
57
void update_add(int L, int R, i64 v, int l, int r, int k) {
58
    if (L <= l && r <= R) {
59
        push_eval(k, l, r, 1, v); // 乘法增量为 1
60
        return;
61
    }
62
    Pushdown(k, l, r);
63
    int mid = l + ((r - l) >> 1);
64
    if (L <= mid) update_add(L, R, v, l, mid, k << 1);
65
    if (R > mid)  update_add(L, R, v, mid + 1, r, k << 1 | 1);
66
    Pushup(k);
67
}
68

69
i64 query(int L, int R, int l, int r, int k) {
70
    if (L <= l && r <= R) return t[k];
71
    Pushdown(k, l, r);
72
    int mid = l + ((r - l) >> 1);
73
    i64 res = 0;
74
    if (L <= mid) res = (res + query(L, R, l, mid, k << 1)) % p;
75
    if (R > mid)  res = (res + query(L, R, mid + 1, r, k << 1 | 1)) % p;
76
    return res;
77
}
78
void solve() {
79
    // 这里的 p 建议设为一个大质数（如 1e9+7）或者题目要求的模数
80
    // 如果没有模数要求，把代码里所有的 % p 去掉即可
81
    cin >> n >> m >> p;
82
    for (int i = 1; i <= n; i++) cin >> a[i];
83
    build(1, 1, n);
84

85
    while (m--) {
86
        int op, x, y;
87
        i64 k;
88
        cin >> op;
89
        if (op == 1) { // 乘法
90
            cin >> x >> y >> k;
91
            update_mul(x, y, k, 1, n, 1);
92
        } else if (op == 2) { // 加法
93
            cin >> x >> y >> k;
94
            update_add(x, y, k, 1, n, 1);
95
        } else { // 求和
96
            cin >> x >> y;
97
            cout << query(x, y, 1, n, 1) << "\n";
98
        }
99
    }
100
}