import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } /* t -> t + y t -> (t + x) % 2 + y (x \in {0, 1}) */ struct S { long x, y; S opBinary(string op)(in S a) const if (op == "*") { if (x == -1 && a.x == -1) { return S(-1, y + a.y); } else { return S((((x == -1) ? 0 : x) + y + ((a.x == -1) ? 0 : a.x)) & 1, a.y); } } } enum IDENTITY = S(-1, 0); struct Info { long cnt0, cnt1, sum; void apply(in S s) { if (s.x == -1) { sum += (cnt0 + cnt1) * s.y; if (s.y & 1) { swap(cnt0, cnt1); } } else { sum = cnt0 * (((0 + s.x) & 1) + s.y) + cnt1 * (((1 + s.x) & 1) + s.y); if ((s.x + s.y) & 1) { swap(cnt0, cnt1); } } } Info opBinary(string op)(in Info a) const if (op == "*") { return Info(cnt0 + a.cnt0, cnt1 + a.cnt1, sum + a.sum); } } class SegmentTree { int n; Info[] info; S[] mul; this(Info[] ini) { const n_ = cast(int)(ini.length); for (n = 1; n < n_; n <<= 1) {} info = new Info[n << 1]; mul = new S[n << 1]; mul[] = IDENTITY; foreach (i; 0 .. n_) { info[n + i] = ini[i]; } foreach_reverse (a; 1 .. n) { info[a] = info[a << 1] * info[a << 1 | 1]; } } private Info query(int u, int x, int y, int a, int b, in S val) { chmax(a, x); chmin(b, y); if (a >= b) { return Info(0, 0, 0); } if (a == x && b == y) { info[u].apply(val); mul[u] = mul[u] * val; return info[u]; } assert(u < n); const uL = u << 1 | 0; const uR = u << 1 | 1; const mid = (x + y) >> 1; if (mul[u] != IDENTITY) { info[uL].apply(mul[u]); info[uR].apply(mul[u]); mul[uL] = mul[uL] * mul[u]; mul[uR] = mul[uR] * mul[u]; mul[u] = IDENTITY; } const resL = query(uL, x, mid, a, b, val); const resR = query(uR, mid, y, a, b, val); info[u] = info[uL] * info[uR]; return resL * resR; } Info query(int a, int b, in S val) { return query(1, 0, n, a, b, val); } } int N, Q; long[] A; int[] T, L, R; long[] X; void main() { try { for (; ; ) { N = readInt(); Q = readInt(); A = new long[N]; foreach (i; 0 .. N) { A[i] = readLong(); } T = new int[Q]; L = new int[Q]; R = new int[Q]; X = new long[Q]; foreach (q; 0 .. Q) { T[q] = readInt(); L[q] = readInt() - 1; R[q] = readInt(); if (T[q] == 2) { X[q] = readLong(); } } auto ini = new Info[N]; foreach (i; 0 .. N) { ini[i].cnt0 = ((A[i] & 1) == 0); ini[i].cnt1 = ((A[i] & 1) == 1); ini[i].sum = A[i]; } auto seg = new SegmentTree(ini); foreach (q; 0 .. Q) { if (T[q] == 1) { seg.query(L[q], R[q], S(0, 0)); } else if (T[q] == 2) { seg.query(L[q], R[q], S(-1, X[q])); } else { const res = seg.query(L[q], R[q], IDENTITY); writeln(res.sum); } } } } catch (EOFException e) { } }