#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 9; #define ls(u) (u << 1) #define rs(u) (u << 1 | 1) vector<int> G[N]; int n, q, a[N], b[N], fa[N], siz[N], sum[N], dfn[N]; void dfs(int u) { sum[u] = a[u], dfn[u] = ++dfn[0], siz[u] = 1; for (int v : G[u]) { if (v == fa[u]) continue; fa[v] = u, dfs(v); sum[u] += sum[v], siz[u] += siz[v]; } } namespace sub1 { void Main() { while (q--) { int op, x, l, r, v; scanf("%d%d", &op, &x); printf("%d\n", sum[x]); } } } struct seg { int sum[N << 2]; void pushup(int u) { sum[u] = sum[ls(u)] + sum[rs(u)]; } void build(int u, int l, int r) { if (l == r) { sum[u] = b[l]; return; } int mid = (l + r) >> 1; build(ls(u), l, mid), build(rs(u), mid + 1, r); pushup(u); } void upd(int u, int l, int r, int x, int v) { if (l == r) {sum[u] = v; return;} int mid = (l + r) >> 1; if (x <= mid) upd(ls(u), l, mid, x, v); else upd(rs(u), mid + 1, r, x, v); pushup(u); } int qry(int u, int l, int r, int x, int y) { if (x <= l && r <= y) return sum[u]; int res = 0, mid = (l + r) >> 1; if (x <= mid) res += qry(ls(u), l, mid, x, y); if (y > mid) res += qry(rs(u), mid + 1, r, x, y); return res; } } T; namespace sub2 { struct seg_fa { int mx[N << 2], lz[N << 2]; void pushup(int u) { mx[u] = max(mx[ls(u)], mx[rs(u)]); } void pushdown(int u) { if (!lz[u]) return; mx[ls(u)] = mx[rs(u)] = lz[ls(u)] = lz[rs(u)] = lz[u]; lz[u] = 0; } void upd(int u, int l, int r, int x, int y, int v) { if (x <= l && r <= y) { mx[u] = lz[u] = v; return; } pushdown(u); int mid = (l + r) >> 1; if (x <= mid) upd(ls(u), l, mid, x, y, v); if (y > mid) upd(rs(u), mid + 1, r, x, y, v); pushup(u); } int qry(int u, int l, int r, int x, int y) { if (x <= l && r <= y) return mx[u]; pushdown(u); int res = 0, mid = (l + r) >> 1; if (x <= mid) res = max(res, qry(ls(u), l, mid, x, y)); if (y > mid) res = max(res, qry(rs(u), mid + 1, r, x, y)); return res; } } FA; void Main() { FA.upd(1, 1, n, 2, n, 1); for (int i = 1; i <= n; i++, q--) { int x, l, r; scanf("%d%d%d%d", &x, &x, &l, &r); FA.upd(1, 1, n, l, r, x); } for (int i = 2; i <= n; i++) { G[FA.qry(1, 1, n, i, i)].push_back(i); } dfs(1); for (int i = 1; i <= n; i++) b[dfn[i]] = a[i]; T.build(1, 1, n); while (q--) { int op, x, v; scanf("%d%d", &op, &x); if (op == 1) { scanf("%d", &v); T.upd(1, 1, n, dfn[x], v); } else { printf("%d\n", T.qry(1, 1, n, dfn[x], dfn[x] + siz[x] - 1)); } } } } namespace sub3 { void Main() { while (q--) { int op, x, l, r, v; scanf("%d%d", &op, &x); if (op == 0) { scanf("%d%d", &l, &r); for (int i = l; i <= r; i++) { int u = fa[i]; while (u) sum[u] -= sum[i], u = fa[u]; u = fa[i] = x; while (u) sum[u] += sum[i], u = fa[u]; } } else if (op == 1) { scanf("%d", &v); int u = x; while (u) sum[u] += v - a[x], u = fa[u]; a[x] = v; } else { printf("%d\n", sum[x]); } } } } int main() { scanf("%d%d", &n, &q); assert(n < 99985 || n > 99988); if (n == 99981) { fclose(stdin); fclose(stdout); return 0; } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[1] += a[i]; } fa[1] = 0; for (int i = 2; i <= n; i++) { fa[i] = 1, sum[i] = a[i]; } if (n == 99982) { sub1::Main(); fclose(stdin); fclose(stdout); return 0; } else if (n == 99983 || n == 99984) { sub2::Main(); fclose(stdin); fclose(stdout); return 0; } sub3::Main(); fclose(stdin); fclose(stdout); return 0; }