P17398 [ICPC 2018 Shenyang R] Best ACMer Solves the Hardest Problem

终有一天，优秀的 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$。然后我们考虑若干动态给出的查询和修改，以如下形式表示： * $\text{1 x y w}$：在 $(x, y)$ 处插入一个权重为 $w$ 的新点，保证在此操作前该位置没有点； * $\text{2 x y}$：删除位于 $(x, y)$ 的点，保证此操作前该点存在； * $\text{3 x y k w}$：对于每个与 $(x, y)$ 的欧几里得距离为 $\sqrt{k}$ 的点，将其权重增加 $w$； * $\text{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$ 表示最近一次查询的答案，其初始值为 $0$。对于输入中每个拥有值 $x$ 和 $y$ 的操作，它们的真实值应分别为 $(((x + lastans) \bmod 6000) + 1)$ 和 $(((y + lastans) \bmod 6000) + 1)$。所有操作中的系数均为整数，且满足 $0 \le k \leq 10^7$，$1 \le x, y, w \le 6000$。 我们保证所有测试数据中 $n$ 的总和以及 $m$ 的总和各自不超过 $10^6$。

对于每组测试数据，首先输出一行 “Case #x:”（不含引号），其中 $x$ 是测试数据的编号，从 $1$ 开始。 然后对于每个查询，在一行中输出一个整数表示答案。

在样例中，如果我们忽略操作中 $x$ 和 $y$ 动态调整的特殊输入格式，我们可以以离线形式直接展示这些修改与查询如下： * $\text{1 3000 3001 1}$； * $\text{4 3000 3000 1}$； * $\text{2 3000 3001}$； * $\text{3 3000 3000 1 1}$； * $\text{4 3000 3000 1}$； * $\text{4 3007 3007 1}$。 翻译由 DeepSeek V4 Pro 完成