Description

Facer needs to train a team of $N$ people.

Each person has an intelligence value $a_i$ and a stamina value $b_i$.

Facer wants to form teams of two, and the two people in a team should be as similar as possible.

Specifically, the similarity between person $i$ and person $j$ is $| a_i - a_j + b_j - b_i | + | a_i - a_j |$. The smaller the similarity, the more similar they are.

There are currently $N$ people in the team, but Facer wants to perform $M$ operations. There are two types of operations:

• Add a person to the team.
• Given the data of a person who is not in the team, output the minimum similarity between this person and all people in the team. Note that after the operation, do not add this person to the team, and do not remove any person found from the team.

Input Format

The first line contains two integers $N, M$.

The next $N$ lines each contain two numbers $a_i, b_i$, representing the intelligence and stamina of the $i$-th person in the team.

The next $M$ lines each describe one operation:

• 1 a b: A new person with intelligence $a$ and stamina $b$ is added to the team.
• 2 a b: There is a person not in the team with intelligence $a$ and stamina $b$. Output the minimum similarity between this person and all people in the team.

Output Format

For each operation 2, output one line containing the minimum similarity between this person and the most similar person in the team.

3 3
1 7
2 -1
6 6
1 1 5
2 4 5
2 3 0

3
1

Hint

For $40\%$ of the testdata, $1 \le N, M \le 1000$.

For $100\%$ of the testdata, $1 \le N, M \le {10}^5$.

Translated by ChatGPT 5