区间加，求一段时间内的区间平方和。
\(n, m, q \le 5 \times 10^4\)。
对时间维差分一下，变成询问区间历史平方和。
离线下来扫描线，扫描线维护时间维，数据结构维护序列维。
考虑维护二元组 \((a, s)\) 表示当前位置值为 \(a\)，历史平方和为 \(s\)。
可以发现怎么修改最后的形式都会固定在 \((a + x, s + y a^2 + za + w)\)。
所以信息要多维护一个平方和，tag 维护 \((add, add1, add2, add3)\)。
tag 的复合手算一下就行。
时间复杂度 \(O((n + q) \log n)\)。
constexpr int MAXN = 5e4 + 9;
int n, m, q, a[MAXN];
tuple<int, int, int> q1[MAXN];
vector<tuple<int, int, int, int> > q2[MAXN];
struct Modint {
int a;
Modint(): a(0) { return; }
Modint(int x): a((x % MOD + MOD) % MOD) { return; }
friend Modint operator + (Modint x, Modint y) { return Modint(add(x.a, y.a)); }
friend Modint operator - (Modint x, Modint y) { return Modint(del(x.a, y.a)); }
friend Modint operator * (Modint x, Modint y) { return Modint((int)(1ll * x.a * y.a % MOD)); }
friend Modint operator / (Modint x, Modint y) {
static auto qpow = [&](Modint a, int b) {
Modint ans = 1;
for (; b; b >>= 1, a = a * a)
if (b & 1) ans = ans * a;
return ans;
};
return x * qpow(y, MOD - 2);
}
friend Modint operator + (Modint x, int y) { return x + Modint(y); }
friend Modint operator - (Modint x, int y) { return x - Modint(y); }
friend Modint operator * (Modint x, int y) { return x * Modint(y); }
friend Modint operator / (Modint x, int y) { return x / Modint(y); }
friend Modint operator + (int x, Modint y) { return Modint(x) + y; }
friend Modint operator - (int x, Modint y) { return Modint(x) - y; }
friend Modint operator * (int x, Modint y) { return Modint(x) * y; }
friend Modint operator / (int x, Modint y) { return Modint(x) / y; }
Modint& operator += (Modint x) { return (*this) = (*this) + x; }
Modint& operator -= (Modint x) { return (*this) = (*this) - x; }
Modint& operator *= (Modint x) { return (*this) = (*this) * x; }
Modint& operator /= (Modint x) { return (*this) = (*this) / x; }
Modint& operator += (int x) { return (*this) = (*this) + x; }
Modint& operator -= (int x) { return (*this) = (*this) - x; }
Modint& operator *= (int x) { return (*this) = (*this) * x; }
Modint& operator /= (int x) { return (*this) = (*this) / x; }
operator bool() const { return a; }
} ans[MAXN];
struct Info {
Modint sum, sqr, ans;
Info(): sum(Modint()), sqr(Modint()), ans(Modint()) { return; }
Info(int _sum, int _sqr, int _ans):
sum(Modint(_sum)), sqr(Modint(_sqr)), ans(Modint(_ans)) { return; }
Info(int x): sum(Modint(x)), sqr(Modint(x) * Modint(x)), ans(0) { return; }
friend Info operator + (Info x, Info y) {
Info ans;
ans.sum = x.sum + y.sum;
ans.sqr = x.sqr + y.sqr;
ans.ans = x.ans + y.ans;
return ans;
}
};
struct Tag {
Modint add, add1, add2, add3;
// a a^2 a c
Tag(int a = 0, int b = 0, int c = 0, int d = 0):
add(Modint(a)), add1(Modint(b)), add2(Modint(c)), add3(Modint(d)) { return; }
operator bool() const { return add || add1 || add2 || add3; }
friend Tag operator * (Tag x, Tag y) {
Tag ans;
ans.add = x.add + y.add;
ans.add1 = x.add1 + y.add1;
ans.add2 = x.add2 + y.add2 + 2 * x.add1 * y.add;
ans.add3 = x.add3 + y.add3 + x.add1 * y.add * y.add + x.add2 * y.add;
return ans;
}
Info Apply(Info x, int len) {
Info ans;
ans.sum = x.sum + add * len;
ans.sqr = x.sqr + 2 * add * x.sum + add * add * len;
ans.ans = x.ans + add1 * x.sqr + add2 * x.sum + add3 * len;
return ans;
}
};
struct Node {
Info dat; Tag tag;
} sgt[MAXN << 2];
void Push_Up(int p) {
sgt[p].dat = sgt[p << 1].dat + sgt[p << 1 | 1].dat;
return;
}
void Push_Tag(int p, Tag tg, int len) {
sgt[p].tag = tg * sgt[p].tag;
sgt[p].dat = tg.Apply(sgt[p].dat, len);
return;
}
void Push_Down(int p, int l, int r) {
if (sgt[p].tag) {
int mid = l + r >> 1;
Push_Tag(p << 1, sgt[p].tag, mid - l + 1);
Push_Tag(p << 1 | 1, sgt[p].tag, r - mid);
sgt[p].tag = Tag();
}
return;
}
void Build(int l = 1, int r = n, int p = 1) {
if (l == r) { sgt[p].dat = Info(a[l]); return; }
int mid = l + r >> 1;
Build(l, mid, p << 1), Build(mid + 1, r, p << 1 | 1);
Push_Up(p); return;
}
void Update(int l, int r, int k, int L = 1, int R = n, int p = 1) {
if (l <= L && R <= r) { Push_Tag(p, Tag(k, 0, 0, 0), R - L + 1); return; }
Push_Down(p, L, R); int Mid = L + R >> 1;
if (l <= Mid) Update(l, r, k, L, Mid, p << 1);
if (Mid < r) Update(l, r, k, Mid + 1, R, p << 1 | 1);
Push_Up(p); return;
}
Modint Query(int l, int r, int L = 1, int R = n, int p = 1) {
if (l <= L && R <= r) return sgt[p].dat.ans;
Push_Down(p, L, R); int Mid = L + R >> 1;
if (r <= Mid) return Query(l, r, L, Mid, p << 1);
if (Mid < l) return Query(l, r, Mid + 1, R, p << 1 | 1);
return Query(l, r, L, Mid, p << 1) + Query(l, r, Mid + 1, R, p << 1 | 1);
}
void slv() {
n = Read<int>(), m = Read<int>(), q = Read<int>();
for (int i = 1; i <= n; i ++) a[i] = Read<int>();
for (int i = 1; i <= m; i ++) {
int l = Read<int>(), r = Read<int>(), x = Read<int>();
q1[i] = make_tuple(l, r, x);
}
for (int i = 1; i <= q; i ++) {
int l = Read<int>(), r = Read<int>(), x = Read<int>(), y = Read<int>();
if (x) q2[x - 1].emplace_back(l, r, -1, i);
q2[y].emplace_back(l, r, 1, i);
}
Build(), Push_Tag(1, Tag(0, 1, 0, 0), n);
for (auto _ : q2[0]) {
int l, r, op, id; tie(l, r, op, id) = _;
ans[id] += op * Query(l, r);
}
for (int i = 1; i <= m; i ++) {
{
int l, r, x; tie(l, r, x) = q1[i];
Update(l, r, x), Push_Tag(1, Tag(0, 1, 0, 0), n);
}
for (auto _ : q2[i]) {
int l, r, op, id; tie(l, r, op, id) = _;
ans[id] += op * Query(l, r);
}
}
for (int i = 1; i <= q; i ++) Write(ans[i].a, '\n');
return;
}