{"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\"\u003eIn graph theory, a \u003cb\u003emaximum spanning tree\u003c/b\u003e is a subgraph that is a tree and connects all the vertices with maximum weight sum. And a \u003cb\u003emaximum spanning forest\u003c/b\u003e is the union of maximum spanning trees of each connected component in the graph.\u003cbr\u003e\u003cbr\u003eA big undirected graph $G\u003d(V,E)$ is given, which $V\u003d\\{(x,y) : 1 \\le x,y \\le 2,000,000,000;~x,y\\in\\mathbb{Z}\\}$ and $E\u003d\\{\\}$ initially. You\u0027re task is to write a program that support operation $x_1,y_1,x_2,y_2,c$:\u003cbr\u003e\u003cbr\u003eFirst, add some edges in $G$. You should add an edge between $(a_1, b_1)$ and $(a_2, b_2)$ with weight $c$ if $x_1 \\le a_1,a_2 \\le x_2$, $y_1 \\le b_1, b_2 \\le y_2$ and $|a_1 - a_2| + |b_1 - b_2| \u003d 1$.\u003cbr\u003e\u003cbr\u003eSecond, calculate the maximum spanning forest of $G$ after edges added.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains an integer $T$ indicating the total number of test cases.\u003cbr\u003e\u003cbr\u003eThe first line of each test case has an integers $n$, indicating the number of operations. The $n$ lines that follow describe the operations. Each of these lines has $5$ integers $x_1,y_1,x_2,y_2,c$, separated by a single space.\u003cbr\u003e\u003cbr\u003eLimitations:\u003cbr\u003e\u003cbr\u003e$1 \\le T \\le 500$\u003cbr\u003e$1 \\le n \\le 100$\u003cbr\u003e$1 \\le x_1 \\le x_2 \\le 2,000,000,000$\u003cbr\u003e$1 \\le y_1 \\le y_2 \\le 2,000,000,000$\u003cbr\u003e$1 \\le c \\le 1,000,000,000$\u003cbr\u003eThere are at most $20$ testcases with $n \u0026gt; 50$."}},{"title":"Output","value":{"format":"HTML","content":"For each operation, output a number in a line that indicates the weight of maximum spanning forest mod $10^9+7$."}},{"title":"Sample","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\u003e2\r\n3\r\n2 2 3 3 1\r\n1 2 2 3 2\r\n1 1 1 3 5\r\n1\r\n1 1 2000000000 2000000000 1000000000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n8\r\n16\r\n999998642\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}