故事围绕着 $n$ 个敌对的忍者家族（编号为 $1$ 到 $n$）以及 $n$ 个忍者（编号也为 $1$ 到 $n$）展开。对于每个忍者，家族决定了他/她最初的信仰和所属的氏族。但在故事中发生了一些冲突，例如两个年轻人面对忍者间的敌对关系却坠入爱河，他们可能会改变主意，一些忍者也可能叛逃到其他敌对的氏族。

这些忍者生活在一个相当安静的小镇上，有着笔直的路径，但他们像一群野兽一样盯着其他氏族的忍者，不断地逃避并渴望杀戮。该地区的总督知道，他们之间战争的终结取决于那些属于不同氏族且距离最远的忍者。

这就是作为总督忠实仆人的高贵秃鹫应该做的事情。现在你需要扮演这只秃鹫，实时向总督报告在指定的连续编号范围内，属于不同氏族的两个忍者之间的最大距离。实际上，平面上两点之间的距离定义为曼哈顿距离，即它们笛卡尔坐标差的绝对值之和。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $60$。

对于每个测试用例，第一行包含两个整数 $n$（表示氏族数量，也表示忍者数量）和 $m$（表示总督发出的特殊冲突和询问的总数），其中 $1 \le n \le 10^5$ 且 $1 \le m \le 10^5$。

接下来的 $n$ 行描述了所有忍者的初始情况。第 $i$ 行包含三个整数 $x, y$ 和 $c$，表示第 $i$ 个忍者最初停留的位置为 $(x, y)$，且他/她最初所属的氏族为第 $c$ 个，其中 $-10^9 \le x, y \le 10^9$ 且 $1 \le c \le n$。

随后的 $m$ 行按时间顺序描述了所有改变某人位置或氏族的特殊冲突，以及总督的所有询问。每一行必须是以下形式之一：

• 1 k x y：第 $k$ 个忍者沿方向 $(x, y)$ 改变他/她的位置；也就是说，他/她移动到新位置 $(x_0 + x, y_0 + y)$，其中 $(x_0, y_0)$ 是他/她原来的位置。
• 2 k c：第 $k$ 个忍者改变主意，决定为第 $c$ 个氏族效力。
• 3 l r：总督询问他的秃鹫，在编号从 $l$ 到 $r$（包含边界）的忍者中，属于不同氏族的两个忍者之间的最大距离。

在这些 $m$ 行中提到的所有 $k, x, y, l, r$ 和 $c$ 均满足 $1 \le k, c \le n$，$-10^9 \le x, y \le 10^9$ 且 $1 \le l \le r \le n$。我们保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$，且所有测试用例中 $m$ 的总和也不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，首先输出一行包含 “Case #x:”，其中 $x$ 是从 $1$ 开始的测试用例编号。

然后对于每次询问，输出一行一个整数表示答案。如果所有相关的忍者都属于同一个氏族，则输出 $0$。

样例

输入 1

1
2 8
0 0 1
1 1 2
3 1 2
1 1 1 1
3 1 2
1 1 1 1
2 1 2
3 1 2
2 1 1
3 1 2

输出 1

Case #1:
2
0
0
2

说明

《甲贺忍法帖》（The Kouga Ninja Scrolls）是日本作家山田风太郎于 1958-1959 年创作的忍者历史奇幻小说。这是山田于 1958-2001 年间创作的《忍法帖》系列的第一卷。该书由 Geoff Sant 翻译成英文，并于 2006 年 12 月由 Del Rey 出版。 ——摘自维基百科，自由的百科全书