[IOI Camp Judge 37]動態曼哈頓最短距離 (題目備份)

IOI Camp Judge是暫時性的，因此在此做題目備份
題解在這裡

動態曼哈頓最短距離

Time Limit: 8s

Description

定義二維平面上兩個點 (x1,y1),(x2,y2)$(x_1,y_1),(x_2,y_2)$ 的曼哈頓距離為 |x1−x2|+|y1−y2|$|x_1-x_2|+|y_1-y_2|$。

你現在要維護一個集合 S$S$（一開始為空集合），並且將進行一連串操作，操作有兩種：

• 將二維平面上一個整數點（座標皆為整數）(x,y)$(x,y)$ 放到 S$S$ 裏面
• 問 S$S$ 裏面與 (x,y)$(x,y)$ 曼哈頓距離最近點的距離為多少

Input Format

第一行有一個正整數 T$T$，代表總共有幾筆測試資料。每筆測試資料第一行包含一個正整數 N$N$，代表操作數。接下來包含 N$N$ 行，每行包含三個正整數 t,x,y$t,x,y$。若 t$t$ 爲 0$0$ 代表插入操作，請將 (x,y)$(x,y)$ 放進 S$S$ 裡。若 t$t$ 爲 1$1$ 代表詢問操作，請輸出 S$S$ 裡離 (x,y)$(x,y)$ 的曼哈頓距離最小是多少。

• 1≤T≤5$1\le T\le 5$
• 1≤N≤2×105$1\le N\le 2\times {10}^5$
• 1≤x,y≤106$1\le x,y\le {10}^6$
• 保證第一個操作是插入操作

Output Format

對於每個詢問操作，請輸出一行包含一個整數，代表詢問的答案。

Sample Input

1
10
0 1 3
0 2 4
1 3 4
1 2 120
0 1 4
0 1 3
1 1 2
1 1 1
0 1 4
1 2 4

Sample Output

1
116
1
2
0