Problem Description

The kingdom of Henryy is the most civilized country in the world. Meanwhile, the capital city H is as well the most beautiful city on the earth. Currently, the city is to build up database to maintain the statistics of the buildings in the city.
You are a little P in the company that takes this project. Your task is to calculate the maximum distance between two buildings in the city.
The Manhattan Distance is defined as: for two points P1(x1, y1) and P2(x2, y2) on a two dimension Cartesian plane, the Manhattan Distance D(P1, P2) = |x1-x2|+|y1-y2|.
Your database should support this query: after updating a data that a building has built or demolished, it should return the maximum distance between existed buildings:

N is the current number of buildings, and Pi is the coordinates of the ith building.

Input

The first line contains an integer T (T<=10), indicating the number of the test cases.
For each test case, the first line contains an integer M (M<=100000), the number of records of the changes of buildings.
Then M lines followed, each line starting with a positive integer: 1 for building that has built, and 2 for demolished. A string with less than 9 characters follows, indicating the name of the building. If this building is just built, two integers of the coordinates of this building are given afterwards.
Notice that no two buildings share the same name, even when one of these buildings has been demolished, but might share the same coordinates. It is also guaranteed that the building exists when a demolishing record is given.
A blank line is followed after each test case.

Output

For each record, output an integer in a single line, indicating the maximum Manhattan Distance among existing buildings.
Print a blank line after each test case.

1
8
1 mgj -2 1
2 mgj
1 kmoaktmr 4 -4
1 mauxizu 3 -2
2 kmoaktmr
1 md -1 4
2 md
1 umos -5 0

0
-1
0
3
0
10
0
10