Problem Description
In graph theory, a maximum spanning tree is a subgraph that is a tree and connects all the vertices with maximum weight sum. And a maximum spanning forest is the union of maximum spanning trees of each connected component in the graph.
A big undirected graph G=(V,E) is given, which V={(x,y):1≤x,y≤2,000,000,000; x,y∈Z} and E={} initially. You're task is to write a program that support operation x1,y1,x2,y2,c:
First, add some edges in G. You should add an edge between (a1,b1) and (a2,b2) with weight c if x1≤a1,a2≤x2, y1≤b1,b2≤y2 and |a1−a2|+|b1−b2|=1.
Second, calculate the maximum spanning forest of G after edges added.
Input
The first line of input contains an integer T indicating the total number of test cases.
The 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 x1,y1,x2,y2,c, separated by a single space.
Limitations:
1≤T≤500
1≤n≤100
1≤x1≤x2≤2,000,000,000
1≤y1≤y2≤2,000,000,000
1≤c≤1,000,000,000
There are at most 20 testcases with n>50.
Output
For each operation, output a number in a line that indicates the weight of maximum spanning forest mod 109+7.
Sample Input
2
3
2 2 3 3 1
1 2 2 3 2
1 1 1 3 5
1
1 1 2000000000 2000000000 1000000000
Sample Output
3
8
16
999998642
