1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <cstdio>
#include <algorithm>
using namespace std;
typedef int LL;
const int INF = 1009999999;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
struct point_type {
	int a[3], mi[3], mx[3], lc, rc;
	LL val, sum;
	int& operator [] (int x) {
		return a[x];
	}
} p[160005];
struct query_type {
	int x1, y1, x2, y2, t, square;
} q[10005];
int s, w, n, m, D, L[3], R[3];
LL ans;
inline bool operator < (point_type a, point_type b) {
	return a[D] < b[D];
}
inline double sqr(double x) {
	return x * x;
}
inline void pu(int x) {
	int lc = p[x].lc, rc = p[x].rc;
	if (lc) {
		for (int i = 0; i < 3; ++i) {
			p[x].mi[i] = min(p[x].mi[i], p[lc].mi[i]);
			p[x].mx[i] = max(p[x].mx[i], p[lc].mx[i]);
		}
		p[x].sum += p[lc].sum;
	}
	if (rc) {
		for (int i = 0; i < 3; ++i) {
			p[x].mi[i] = min(p[x].mi[i], p[rc].mi[i]);
			p[x].mx[i] = max(p[x].mx[i], p[rc].mx[i]);
		}
		p[x].sum += p[rc].sum;
	}
}
int build(int l, int r) {
	if (l > r) return 0;
	if (l == r) return l;
	double mxfc = -1, fc, avg;
	for (int i = 0; i < 3; ++i) {
		fc = avg = 0;
		for (int j = l; j <= r; ++j)
			avg += p[j][i];
		avg /= (r - l + 1);
		for (int j = l; j <= r; ++j)
			fc += sqr(avg - p[j][i]);
		if (fc > mxfc) {
			mxfc = fc;
			D = i;
		}
	}
	int mid = (l + r) >> 1;
	nth_element(p + l, p + mid, p + r + 1);
	p[mid].lc = build(l, mid - 1);
	p[mid].rc = build(mid + 1, r);
	pu(mid);
	return mid;
}
bool check(int x) {
	if (p[x].mi[0] > R[0] || p[x].mx[0] < L[0] || p[x].mi[1] > R[1] || p[x].mx[1] < L[1] || p[x].mi[2] > R[2])
		return false;
	return true;
}
void query(int x) {
	if (L[0] <= p[x].mi[0] && p[x].mx[0] <= R[0] && L[1] <= p[x].mi[1] && p[x].mx[1] <= R[1] && p[x].mx[2] <= R[2])
		return (void)(ans += p[x].sum);
	if (L[0] <= p[x][0] && p[x][0] <= R[0] && L[1] <= p[x][1] && p[x][1] <= R[1] && p[x][2] <= R[2])
		ans += p[x].val;
	int lc = p[x].lc, rc = p[x].rc;
	if (lc && check(lc)) query(lc);
	if (rc && check(rc)) query(rc);
}
int main() {
	s = getint(); w = getint();
	int opt, a, b, c, d, t = 0, n = 0;
	while (true) {
		opt = getint();
		if (opt == 3) break;
		++t;
		if (opt == 1) {
			++n;
			a = getint(); b = getint(); c = getint();
			p[n][0] = p[n].mi[0] = p[n].mx[0] = a;
			p[n][1] = p[n].mi[1] = p[n].mx[1] = b;
			p[n][2] = p[n].mi[2] = p[n].mx[2] = t;
			p[n].val = p[n].sum = c;
		}
		if (opt == 2) {
			++m;
			a = getint(); b = getint(); c = getint(); d = getint();
			q[m].x1 = a; q[m].y1 = b; q[m].x2 = c; q[m].y2 = d;
			q[m].t = t; q[m].square = (c - a + 1) * (d - b + 1);
		}
	}
	int root = build(1, n);
	for (int i = 1; i <= m; ++i) {
		L[0] = q[i].x1; R[0] = q[i].x2;
		L[1] = q[i].y1; R[1] = q[i].y2;
		R[2] = q[i].t;
		ans = 0; query(root); ans += q[i].square * s;
		printf("%d\n", ans);
	}
	return 0;
}