{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e总有一天,一位优秀的ACMer会离开这个领域,去面对新的挑战,就像前辈们所做的一样。他们中的一些人接管了家族企业,有些人在与失业边缘挣扎。有些人有勇气展示自己,成为专业的Ingress玩家,还有一些人仍在不断挑战自己的极限,努力解决Project Euler中的所有问题。\u003c/p\u003e\u003cp\u003e但是对于前国王Benecol de Cecco来说,所有这些目标都太肤浅了。他现在所做的就是成为StackOverflow中最优秀的回答者。StackOverflow是开发者学习、分享编程知识和发展职业的最大、最值得信赖的在线社区。\u003c/p\u003e\u003cp\u003e今天,他注意到了一条由Kevin Li发布的问题,内容是:最近,我实现了一个实验,需要找到所有数据记录,它们与查询点$$$q$$$的欧几里得距离相同,即值为$$$r$$$。我尝试使用k-d树来提高搜索效率。然而,我发现k-d树需要遍历所有叶节点才能返回结果,也就是说,它仍然需要比较所有数据集才能得到结果。\u003c/p\u003e\u003cp\u003e这个问题可以形式化为构建一个具有实时查询和修改的数据库。一开始,假设我们在平面上有$$$n$$$个不同的点。第$$$i$$$个点位于$$$(x_i, y_i)$$$,并且具有权重$$$w_i$$$。然后我们考虑一些动态给定的查询和修改,如下\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e1 x y w\u003c/span\u003e,插入一个新点,位于$$$(x, y)$$$,权重为$$$w$$$,在此操作之前保证该位置没有点; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e2 x y\u003c/span\u003e,删除位于$$$(x, y)$$$的点,在此操作之前保证该点存在; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e3 x y k w\u003c/span\u003e,对于每个到$$$(x, y)$$$的欧几里得距离为$$$\\sqrt{k}$$$的点,增加其权重$$$w$$$; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e4 x y k\u003c/span\u003e,查询所有到$$$(x, y)$$$的欧几里得距离为$$$\\sqrt{k}$$$的点的权重之和。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eBenecol de Cecco说这个问题很简单,他让我和大家分享这个问题。顺便说一句,两点$$$(x_0, y_0)$$$和$$$(x_1, y_1)$$$之间的欧几里得距离等于$$$\\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2}$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包含多个测试用例,第一行包含一个正整数$$$T$$$,表示测试用例的数量,最多为$$$1000$$$。\u003c/p\u003e\u003cp\u003e对于每个测试用例,第一行包含两个整数$$$n$$$和$$$m$$$,表示平面上初始点的数量和操作的数量,其中$$$1 \\le n, m \\le 10^5$$$。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行包含三个整数$$$x, y$$$和$$$w$$$,满足$$$1 \\le x, y, w \\le 6000$$$,描述了一开始位于$$$(x, y)$$$,权重为$$$w$$$的点。\u003c/p\u003e\u003cp\u003e接下来的$$$m$$$行中,每行包含一个操作,可以是查询或修改。这些操作的形式如上所述。为了使所有操作中的$$$x$$$和$$$y$$$都是动态的,我们使用$$$lastans$$$表示最近查询的答案,初始值为零。对于输入中的$$$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$$$。\u003c/p\u003e\u003cp\u003e我们保证所有测试用例中$$$n$$$的总和和$$$m$$$的总和分别不超过$$$10^6$$$。\u003c/p\u003e\u003cp\u003e\u0026nbsp; \u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,首先输出一行包含\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x:\u003c/span\u003e\"(不包括引号),其中\u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e是从$$$1$$$开始的测试用例编号。\u003c/p\u003e\u003cp\u003e然后对于每个查询,输出一个整数表示答案。\u003c/p\u003e"}},{"title":"样例1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n3 6\n2999 3000 1\n3001 3000 1\n3000 2999 1\n1 2999 3000 1\n4 2999 2999 1\n2 2995 2996\n3 2995 2995 1 1\n4 2995 2995 1\n4 3000 3000 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n4\n6\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在样例中,如果忽略操作中动态的$$$x$$$和$$$y$$$的特殊输入格式,我们可以直接以离线格式显示这些修改和查询,如下:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e1 3000 3001 1\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e4 3000 3000 1\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e2 3000 3001\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e3 3000 3000 1 1\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e4 3000 3000 1\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e4 3007 3007 1\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e"}}]}