Team Training Similarity

Facer wants to train his team. Each person is characterized by an intelligence value \(a_i\) and a physical strength value \(b_i\). The similarity between person \(i\) and person \(j\) is defined as:

[ \text{sim}(i,j)=\left|a_i - a_j + b_j - b_i\right| + \left|a_i - a_j\right| ]

Facer has an initial team of \(N\) people. Then he will perform \(M\) operations. There are two types of operations:

1. Add Operation: A new person with values \(a\) and \(b\) is added to the team.
2. Query Operation: Given the data of a person not in the team (with values \(a\) and \(b\)), output the minimum similarity between this person and any person in the current team. Note that this person is not added to the team, and no one is removed from the team.

Your task is to process all operations and for each query operation, output the corresponding minimum similarity value.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the initial number of people in the team and the number of operations, respectively.

The next \(N\) lines each contain two integers \(a_i\) and \(b_i\) representing the attributes of each team member.

Each of the following \(M\) lines describes an operation in one of the two formats:

• If the operation is an add operation, the line starts with 1 followed by two integers \(a\) and \(b\).
• If the operation is a query operation, the line starts with 2 followed by two integers \(a\) and \(b\).

outputFormat

For each query operation (operation type 2), output a single line containing one integer — the minimum similarity value between the given person and all persons in the current team.

sample

2 3
1 2
3 4
2 2 3
1 2 3
2 2 2

1
1