{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e中国南方的F市正在准备沿街放置灯笼来庆祝灯笼节。 \u003cbr\u003e由于去年市民出去赏灯时发生了频繁的事故,F市计划开发一个系统来计算两条街道交叉口的拥挤程度。 \u003cbr\u003eF市的地图是一个N×N的网格(N条南北街道和N条东西街道)。对于每个街道交叉口,我们定义了人群密度值。 \u003cbr\u003e最初,每个交叉口的密度值都是零。随着时间的推移,密度值可能会经常变化。一组具有新图形识别技术的摄像头可以在短时间内轻松计算交叉口的密度值。\u003cbr\u003e但是警察局的管理员计划开发一个系统来计算拥挤程度。出于某种考虑,他们提出了一个叫做“k维拥挤程度”的概念。交叉口(x0,y0)的“k维拥挤程度”表示为“c(x0,y0,k)”,可以通过以下公式计算:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/6927c3c55a6e64ed5b56ad968cd6d195?v\u003d1701000611\"\u003e\u003c/center\u003e \u003cbr\u003e这里,d(x,y)代表交叉口(x,y)上的密度值,(x,y)必须在N×N网格中。该公式表示从(x0,y0)的曼哈顿距离为k的范围内的所有交叉口对(x0,y0)的k维拥挤程度产生相等的影响,因此我们只需简单地将它们相加即可得到(x0,y0)的k维拥挤程度。 \u003cbr\u003e下图显示了一个7×7的网格,并且显示了如果要得到交叉口(4,2)的2维拥挤程度,则应该将所有标记交叉口的密度值相加。\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/253598e28f9fe033c4d79bfe6023a588?v\u003d1701000611\"\u003e\u003c/center\u003e \u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"这里有多个测试用例。 \u003cbr\u003e每个测试用例以两个整数N、M开头,表示城市是一个N×N的网格,并且随着时间的推移会有M个查询或事件。(1 ≤ N ≤10 000, 1 ≤ M ≤ 80 000) 然后是M行。每行表示一个查询或事件,格式为(p, x, y, z),这里p \u003d 1或2,1 ≤ x ≤ N,1 ≤ y ≤ N。 \u003cbr\u003e不同p的含义如下所示。\u003cbr\u003e1. p \u003d 1,d(x,y)的值增加z,这里-100 ≤ z ≤ 100。\u003cbr\u003e2. p \u003d 2,查询c(x,y,z)的值,这里0 ≤ z ≤ 2N-1。\u003cbr\u003e输入以N\u003d0结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个查询,在一行中输出c(x,y,z)的值。\u003cbr\u003e"}},{"title":"样例","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\u003e8 5\r\n1 8 8 1\r\n1 1 1 -2\r\n2 5 5 6\r\n1 5 5 3\r\n2 2 3 9\r\n3 2\r\n1 3 2 -9\r\n2 3 2 0\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1\r\n-9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}