有一天，一位优秀的 ACMer 将离开赛场去迎接新的挑战，就像他的前辈们所做的那样。他们中的一些人接手了家族企业，一些人正在为失业的边缘而挣扎。他们中的一些人有勇气展示自己，成为一名职业 Ingress 玩家，还有一些人仍在挑战极限，试图解决 Project Euler 中的所有问题。

但对于前任王者 Benecol de Cecco 来说，这些目标都太肤浅了。他现在所做的是成为 StackOverflow 上最优秀的回答者。StackOverflow 是开发者学习、分享编程知识并建立职业生涯的最大、最受信任的在线社区。

今天，他注意到 Kevin Li 发布的一个问题，上面写着：最近，我进行了一项实验，需要找到所有与查询点 $q$ 的欧几里得距离为相同值 $r$ 的数据记录。我尝试使用 k-d 树来提高搜索效率。然而，我发现 k-d 树需要遍历所有叶子节点才能返回结果，也就是说，它仍然需要比较整个数据集才能得到结果。

这个问题可以形式化为构建一个支持实时查询和修改的数据库。起初，假设我们在平面上有 $n$ 个不同的点。第 $i$ 个点位于 $(x_i, y_i)$，权重为 $w_i$。然后我们考虑动态给出的几种查询和修改：

• 1 x y w，插入一个权重为 $w$ 的新点 $(x, y)$，保证操作前该位置没有点；
• 2 x y，删除位于 $(x, y)$ 的点，保证操作前该点存在；
• 3 x y k w，对于所有到 $(x, y)$ 的欧几里得距离为 $\sqrt{k}$ 的点，将其权重增加 $w$；
• 4 x y k，查询所有到 $(x, y)$ 的欧几里得距离为 $\sqrt{k}$ 的点的权重之和。

Benecol de Cecco 说这个问题很简单，他让我把它分享给大家。顺便提一下，两点 $(x_0, y_0)$ 和 $(x_1, y_1)$ 之间的欧几里得距离等于 $\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2}$。

输入格式

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

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，分别表示平面上的初始点数和操作次数，其中 $1 \le n, m \le 10^5$。

接下来的 $n$ 行，每行包含三个整数 $x, y$ 和 $w$，满足 $1 \le x, y, w \le 6000$，描述了初始时在 $(x, y)$ 处的一个权重为 $w$ 的点。

接下来的 $m$ 行，每行包含一个操作，可以是查询或修改。这些操作以如上所述的形式给出。为了使操作中的所有 $x$ 和 $y$ 动态化，我们使用 $lastans$ 表示最近一次查询的答案，其初始值为零。对于输入中带有 $x$ 和 $y$ 值的每个操作，它们的实际值应分别为 $(((x + lastans) \pmod{6000}) + 1)$ 和 $(((y + lastans) \pmod{6000}) + 1)$。操作中的所有系数均为整数，且满足 $0 \le k \le 10^7$ 以及 $1 \le x, y, w \le 6000$。

我们保证所有测试用例中 $n$ 的总和与 $m$ 的总和分别不超过 $10^6$。

输出格式

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

然后对于每个查询，输出一行一个整数，表示答案。

样例

输入 1

1
3 6
2999 3000 1
3001 3000 1
3000 2999 1
1 2999 3000 1
4 2999 2999 1
2 2995 2996
3 2995 2995 1 1
4 2995 2995 1
4 3000 3000 1

输出 1

Case #1:
4
6
0

说明

在样例中，如果我们忽略操作中动态 $x$ 和 $y$ 的特殊输入格式，我们可以将这些修改和查询直接以离线格式展示如下：

• 1 3000 3001 1;
• 4 3000 3000 1;
• 2 3000 3001;
• 3 3000 3000 1 1;
• 4 3000 3000 1;
• 4 3007 3007 1.