MAIN8_B - Overlapping Squares

no tags 

you are given N (1<=N<=20000) squares on X-Y plane. Your task is to find the area which is common to all the squares (Area of intersection of all the squares)

Input

First line contain T the number of test cases. then t test cases follow. First line of each test case contains N, the number of squares 
Each of following N line contains 3 integer (X, Y, L) cordinate of lower left vertex and size of the square.

First line contain T the number of test cases. Then T test cases follow. First line of each test case contains N, the number of squares Each of following N line contains 3 integer (X, Y, L) cordinate of lower left vertex and size of the square.

-10^9<=X,Y<=10^9    1<=L<=10^9

Output

 

For each test case print the answer in a new line.

 

Example

Input:
2
2
0 0 10
1 1 11
2
10 10 25
1 1 3

Output:
81
0

hide comments
Manik: 2015-05-21 17:41:33

Does anybody have a gun?

Last edit: 2015-05-21 17:43:38

Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:0.442s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8