It gives WA on test 8.
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
using ll = __int128;
const int N = 3e5 + 5, M = N << 2, mod = 1000000000000000009LL;
int n, m, q, x[N], v[N], sum[M], mul[M], add[M];
set<pair<int, int>> s;
int inv(int x) {
if (x == 1) return 1;
return (ll)(mod - mod / x) * inv(mod % x) % mod;
}
auto findLeft(int p) {
return prev(s.upper_bound({p, 1e9}));
}
auto findRight(int p) {
return s.upper_bound({p, 0});
}
int calc(int p) {
return findLeft(p)->second * (findRight(p)->first - p);
}
void pushup(int p) {
sum[p] = (sum[ls] + sum[rs]) % mod;
}
void build(int p, int l, int r) {
// cerr << "build " << p << " " << l << " " << r << endl;
mul[p] = 1;
add[p] = 0;
if (l == r) {
sum[p] = calc(l);
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void pushdown(int p, int l, int r) {
// cerr << "pushdown " << p << " " << l << " " << r << endl;
sum[ls] = ((ll)sum[ls] * mul[p] + (ll)add[p] * (mid - l + 1)) % mod;
sum[rs] = ((ll)sum[rs] * mul[p] + (ll)add[p] * (r - mid)) % mod;
mul[ls] = ((ll)mul[ls] * mul[p]) % mod;
mul[rs] = ((ll)mul[rs] * mul[p]) % mod;
add[ls] = ((ll)add[ls] * mul[p] + add[p]) % mod;
add[rs] = ((ll)add[rs] * mul[p] + add[p]) % mod;
mul[p] = 1;
add[p] = 0;
}
void update1(int p, int l, int r, int L, int R, int k) {
// cerr << "update1 " << p << " " << l << " " << r << " " << L << " " << R << " " << k << endl;
if (L <= l && r <= R) {
add[p] = (add[p] + k) % mod;
sum[p] = (sum[p] + k * (r - l + 1)) % mod;
return;
}
pushdown(p, l, r);
if (L <= mid) update1(ls, l, mid, L, R, k);
if (R > mid) update1(rs, mid + 1, r, L, R, k);
pushup(p);
}
void update2(int p, int l, int r, int L, int R, int k) {
// cerr << "update2 " << p << " " << l << " " << r << " " << L << " " << R << " " << k << endl;
if (L <= l && r <= R) {
sum[p] = (ll)sum[p] * k % mod;
mul[p] = (ll)mul[p] * k % mod;
add[p] = (ll)add[p] * k % mod;
return;
}
pushdown(p, l, r);
if (L <= mid) update2(ls, l, mid, L, R, k);
if (R > mid) update2(rs, mid + 1, r, L, R, k);
pushup(p);
}
int query(int p, int l, int r, int L, int R) {
// cerr << "query " << p << " " << l << " " << r << " " << L << " " << R << endl;
if (L <= l && r <= R) return sum[p];
pushdown(p, l, r);
int res = 0;
if (L <= mid) res = (res + query(ls, l, mid, L, R)) % mod;
if (R > mid) res = (res + query(rs, mid + 1, r, L, R)) % mod;
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) cin >> x[i];
for (int i = 1; i <= m; i++) cin >> v[i];
for (int i = 1; i <= m; i++) s.emplace(x[i], v[i]);
build(1, 1, n);
// cerr << "Segment Tree built" << endl;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int nx, nv;
cin >> nx >> nv;
pair<int, int> L = *findLeft(nx);
pair<int, int> R = *findRight(nx);
// cerr << "L = {" << L.first << ", " << L.second << "}" << endl;
// cerr << "R = {" << R.first << ", " << R.second << "}" << endl;
s.emplace(nx, nv);
update1(1, 1, n, L.first, nx, -L.second * (R.first - nx));
update2(1, 1, n, nx + 1, R.first, (ll)nv * inv(L.second) % mod);
} else {
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << endl;
}
}
return 0;
}