[E. The Kouga Ninja Scrolls][http://codeforces.com/gym/101955/problem/E]

The story centres around nn rival ninja clans labelled from 11 to nn, and nn ninjas also labelled from 11 to nn. For each ninja, the family decides his/her initial belief and affiliation of a clan. But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans.

These ninjas are living in a pretty quiet town with straightforward footpaths, but they live like a group of wild animals eyeing up ninjas of other clans, continually escaping and looking forward to killing. The governor of this region knows that the end of the war between them depends on those ninjas belonging to different clans who have the farthest distance.

That is what a noble vulture as the honest servant of the governor should do. Now you need to act as a vulture, and report in real time to the governor the largest distance between two ninjas that belong to different clans and whose labels are in a specified consecutive range. As a practical matter, the distance between two points in the plane is defined as the Manhattan distance, which is equal to the sum of the absolute differences of their Cartesian coordinates.

Input

The input contains several test cases, and the first line contains a positive integer TT indicating the number of test cases which is up to 6060.

For each test case, the first line contains two integers nn, indicating the number of clans and also the number of ninjas, and mm, indicating the total number of special conflicts and inquiries from the governor, where 1≤n≤1051≤n≤10^5 and 1≤m≤1051≤m≤10^5.

The following nn lines describe the initial situations of all ninjas. The ii-th line of them contains three integers x,yx,y and cc indicating the initial position where the ii-th ninja stays is (x,y)(x,y) and the initial clan which he/she belongs to is the cc-th one, where −109≤x,y≤109−10^9≤x,y≤10^9and 1≤c≤n1≤c≤n.

Then the following mm lines describe all special conflicts that change someone’s position or his/her clan, and all inquiries from the governor in chronological order. Each of them must be in one of the following forms.

  • 1 k x y, the kk-th ninja changes his/her position along the direction (x,y)(x,y); that is to say, he/she moves to the new position (x0+x,y0+y)(x_0+x,y_0+y) where (x0,y0)(x_0,y_0) is his/her original position.
  • 2 k c, the kk-th ninja changes his/her mind and decides to work for the cc-th clan.
  • 3 l r, the governor asks his vulture for ninjas labelled from ll to rr (inclusive) the largest distance between two of them belonging to different clans.

All k,x,y,l,rk,x,y,l,r and cc mentioned in these mm lines satisfy 1≤k,c≤n1≤k,c≤n, −109≤x,y≤109−10^9≤x,y≤10^9 and 1≤l≤r≤n1≤l≤r≤n.

We guarantee that the sum of nn in all test cases is no larger than 5×1055×10^5, and the sum of mm in all test cases is no larger than 5×1055×10^5 as well.

Output

For each test case, output a line containing “Case #x:” (without quotes) at first, where x is the test case number starting from 11.

Then for each inquire, output an integer in a line indicating the answer. If all of the related ninjas belong to the same clan, output 00 instead.

Example

input

1
12 80 0 11 1 23 1 21 1 1 13 1 21 1 1 12 1 23 1 22 1 13 1 2

output

1
Case #1:2002

Note

‘The Kouga Ninja Scrolls’ is a historical fantasy novel about ninja written in 1958−19591958-1959 by the Japanese author Futaro Yamada. This is the first volume of the Ninja Scrolls series written by Yamada in 1958−20011958-2001. The book has been translated into English by Geoff Sant and was published by Del Rey in December 20062006.

– from Wikipedia, the free encyclopedia

 

曼哈顿距离转切比雪夫距离 max(∣x1−x2∣,∣y1−y2∣)max(|x_1-x_2|,|y_1-y_2|)

原图 (x,y)(x,y) -> 新图 (x+y,x−y)(x+y,x-y)，曼哈顿距离->切比雪夫距离

原图 (x,y)(x,y) -> 新图 (x+y2,x−y2)(\frac{x+y}{2},\frac{x-y}{2})，切比雪夫距离->曼哈顿距离

之后x，y坐标就可以分开来维护了，只要各自求出最大值，最小值，相减得到x，y各自的最大差值，再比一下，得到答案。

但是有一点注意，x的最大值和最小值可能属于同一派，y也类似。

所以需要再维护次大和次小值，并且要求次大和最大的派别不同，次小和最小的派别不同。这可以保证维护这四个值一定可以得到派别不同的最大差值。

线段树维护，和不同线段树不同点在于pushup更新次大，次小时要比较和最大，最小的派别不同。

查询也类似。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
typedef pair<ll, int> pii;
#define mid ((l + r) >> 1)
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1 
const int maxn = 1e6 + 10;
const ll INF = 1e18;

int T, n, m;
ll x[maxn], y[maxn];
int c[maxn];
pii trmin[2][maxn << 2][2], trmax[2][maxn << 2][2];//x,y;rt;最大，次大
void pushup(int rt, int id) {
	if (id == 0) {
		for (int i = 0; i < 2; i++) {
			trmin[i][rt][0] = min(trmin[i][rt << 1][0], trmin[i][rt << 1 | 1][0]);
			pii tmp[4];
			pii res{ INF,0 };
			int p = c[trmin[i][rt][0].second];
			tmp[0] = trmin[i][rt << 1][0]; tmp[1] = trmin[i][rt << 1][1]; tmp[2] = trmin[i][rt << 1 | 1][0]; tmp[3] = trmin[i][rt << 1 | 1][1];
			for (int j = 0; j < 4; j++) {
				if (c[tmp[j].second] != p)res = min(res, tmp[j]);
			}
			trmin[i][rt][1] = res;
		}
	}
	else {
		for (int i = 0; i < 2; i++) {
			trmax[i][rt][0] = max(trmax[i][rt << 1][0], trmax[i][rt << 1 | 1][0]);
			pii tmp[4];
			pii res{ -INF,0 };
			int p = c[trmax[i][rt][0].second];
			tmp[0] = trmax[i][rt << 1][0]; tmp[1] = trmax[i][rt << 1][1]; tmp[2] = trmax[i][rt << 1 | 1][0]; tmp[3] = trmax[i][rt << 1 | 1][1];
			for (int j = 0; j < 4; j++) {
				if (c[tmp[j].second] != p)res = max(res, tmp[j]);
			}
			trmax[i][rt][1] = res;
		}
	}
}
void build(int l, int r, int rt) {
	if (l == r) {
		trmin[0][rt][0] = trmax[0][rt][0] = pii(x[l] + y[l], l);
		trmin[0][rt][1] = pii(INF, l); trmax[0][rt][1] = pii(-INF, l);
		trmin[1][rt][0] = trmax[1][rt][0] = pii(x[l] - y[l], l);
		trmin[1][rt][1] = pii(INF, l); trmax[1][rt][1] = pii(-INF, l);
		return;
	}
	build(lson);
	build(rson);
	pushup(rt, 0);
	pushup(rt, 1);
}
pii big, big2, small, small2;
void query(int ql, int qr, int l, int r, int rt, int idxy) {
	if (ql <= l && qr >= r) {
		pii tmp[4];
		tmp[0] = small, tmp[1] = small2, tmp[2] = trmin[idxy][rt][0], tmp[3] = trmin[idxy][rt][1];
		small = min(small, trmin[idxy][rt][0]);
		int p = c[small.second];
		pii res = pii(INF, 0);
		for (int j = 0; j < 4; j++) {
			if (c[tmp[j].second] != p)res = min(res, tmp[j]);
		}
		small2 = res;
		tmp[0] = big, tmp[1] = big2, tmp[2] = trmax[idxy][rt][0], tmp[3] = trmax[idxy][rt][1];
		big = max(big, trmax[idxy][rt][0]);
		p = c[big.second];
		res = pii(-INF, 0);
		for (int j = 0; j < 4; j++) {
			if (c[tmp[j].second] != p)res = max(res, tmp[j]);
		}
		big2 = res;
		return;
	}
	if (ql <= mid)query(ql, qr, lson, idxy);
	if (qr > mid)query(ql, qr, rson, idxy);
}

void update(int q, int l, int r, int rt) {
	if (l == r) {
		trmin[0][rt][0] = trmax[0][rt][0] = pii(x[l] + y[l], l);
		trmin[1][rt][0] = trmax[1][rt][0] = pii(x[l] - y[l], l);
		return;
	}
	if (q <= mid)update(q, lson);
	else update(q, rson);
	pushup(rt, 0);
	pushup(rt, 1);
}
int main() {
	scanf("%d", &T);
	for (int tt = 1; tt <= T; tt++) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)scanf("%I64d%I64d%d", &x[i], &y[i], &c[i]);
		build(1, n, 1);
		printf("Case #%d:\n", tt);
		for (int i = 0; i < m; i++) {
			int op;
			scanf("%d", &op);
			if (op == 1) {
				int k, dx, dy;
				scanf("%d%d%d", &k, &dx, &dy);
				x[k] += dx; y[k] += dy;
				update(k, 1, n, 1);
			}
			else if (op == 2) {
				int k, dc;
				scanf("%d%d", &k, &dc);
				c[k] = dc;
				update(k, 1, n, 1);
			}
			else {
				int l, r;
				scanf("%d%d", &l, &r);
				ll resx = -INF, resy = -INF;
				small = small2 = pii(INF, 0); big = big2 = pii(-INF, 0);
				query(l, r, 1, n, 1, 0);

				if (big2.second == 0 || small2.second == 0) {
					printf("0\n");
					continue;
				}

				if (c[big.second] != c[small.second])resx = big.first - small.first;
				else resx = max(big.first - small2.first, big2.first - small.first);

				small = small2 = pii(INF, 0); big = big2 = pii(-INF, 0);
				query(l, r, 1, n, 1, 1);

				if (big2.second == 0 || small2.second == 0) {
					printf("0\n");
					continue;
				}

				if (c[big.second] != c[small.second])resy = big.first - small.first;
				else resy = max(big.first - small2.first, big2.first - small.first);

				printf("%I64d\n", max(resx, resy));
			}
		}
	}
	return 0;
}