Mr. M is very happy celebrating his recent promotion at Endurance. He wants to show off his skills to his juniors about data structures. To do so he will solve a typical problem given below.

Design a data structure with following operations :

(1) Insert co-ordinate (x,y) in 2-D plane
(2) Remove co-ordinate (x,y) in 2-D plane
(3) Print Maximum distance between any two points in the plane.

Note : Distance between 2 points (x1,y1) and (x2,y2) is defined as max( |x1-x2|, |y1-y2| )

You will be given Q queries(operations) .

There will be 3 different types of queries :

(1) 1 x y ---> insert point (x,y) in 2D dimensional plane
(2) 2 x y ----> remove point(x,y) in 2D dimensional plane
(3) 3 -----> Print the maximum distance between any 2 points

Constraints :
(1) Q <= 10^6
(2) |x|,|y| <= 2*10^9

Input Format : (1) First line of input will contain Q , number of queries
Each of next Q lines will contains queries of 3 different types as mentioned above.

Output Format : (1) For every query of type 3 print a single line containing the required maximum distance.

Note : Initially there are no points in the plane. If there are less than or equals to one point in the plane , then for third type of query print "0" .

If points do not exist, then do nothing.

Example

Input:

6

1 1 10

1 4 9

1 5 8

3

2 1 9

3

Output:

4

4

Announcement : Test Cases are updated and correct

Author : Aayush Kapadia
Tester : Tanmay Patel