I. Manhattan Project
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a seven-dimensional space there is a six-dimensional institution where five-dimensional workers run a four-dimensional data base. The database contains information about the points defined by four coordinated. The institution receives three kinds of requests :

  1. Add a point with the given coordinates
  2. Delete a point with the given coordinates.
  3. Provide a distance between the given point and the most distant point.

In this space the distance between the points (x1, x2, x3, x4) and (y1, y2, y3, y4) is calculated as |x1 - y1| + |x2 - y2| + |x3 - y3| + |x4 - y4|.

There going to be some staff reduction in the institution, so it is necessary to have the above mentioned work automated.

Input

The first line contains an integer N (1 ≤ N ≤ 105) — a number of requests. Each of the next N lines contains five integers: t, x1, x2, x3, x4 — a kind of request and four coordinates of the point respectively (1 ≤ t ≤ 3,  - 108 ≤ x1, x2, x3, x4 ≤ 108).

It is guaranteed that at the moment of request of type 1 (add) the point (x1, x2, x3, x4) does not exist, at the moment of request of type 2 (delete) the point (x1, x2, x3, x4) exists, at the moment of request of type 3 (distance request) at least one point exists. There is no points in the database until the first request arrives.

Output

For each request of 3 kind output the request's result in a separate line.

Examples
Input
5
1 0 0 0 0
1 -10 2 6 -9
3 -8 0 9 -5
2 0 0 0 0
3 -8 0 9 -5
Output
22
11
Input
9
1 2 0 0 0
1 4 3 0 0
1 1 5 0 0
3 2 3 0 0
3 -1 2 0 0
2 4 3 0 0
3 -1 2 0 0
2 2 0 0 0
3 1 5 0 0
Output
3
6
5
0