• Trong tọa độ Oxy, có nhiều điểm (x1, y1), (x2, y2) ... là vị trí taxi
• Cho 1 điểm (x, y), vấn đề là tìm taxi còn hoạt động và có khoảng cách gần nhất với (x, y).   Công thức tính khoảng cách từ (x1, y1) đến (x, y) là: d = | x1 - x | + | y1 - y |

Nhiệm vụ của bạn là thực hiện các API dưới đây:

• Turn_on (id, x, y) ứng với cmd = 1: taxi hoạt động tại vị trí (x, y)
• Turn_off (id) ứng với cmd = 2: taxi (id) ngừng hoạt động
• update_location (id, x, y) ứng với cmd = 3: taxi di chuyển đến địa điểm mới (x, y)
• get_min_distance (x, y) ứng với cmd = 4 : trả lại khoảng cách minimun từ (x, y) đến taxi đã còn hoạt động, trả về -1 nếu không tìm thấy bất kỳ taxi nào còn hoạt động

Giới hạn:

• Ban đầu chưa có taxi nào hoạt động
• \(0 \le x, y \le 10^5\) và \(0 < id <= 10 ^ 9\)
• Tổng số cuộc gọi get_min_distance () không vượt quá \(10 ^ 5\)
• Tổng số cuộc gọi API không vượt quá \(10 ^ 6\)
• Hãy thử sức với việc không sử dụng bất kỳ thư viện có sẵn nào ngoài nhập/xuất.

Input:

• Dòng đầu tiên là số test case \(T ( 1 \le T \le 50)\)
• Các dòng tiếp theo là 1 chữ số ứng với lệnh cmd tương ứng :
  • Nếu cmd = 1: tiếp theo sẽ là 3 số nguyên id, x, y, tương ứng với Turn_on (id, x, y)
  • Nếu cmd = 2: tiếp theo sẽ là 1 số nguyên id, tương ứng với Turn_off (id)
  • Nếu cmd = 3: tiếp theo sẽ là 3 số nguyên id, x, y, tương ứng với update_location (id, x, y)
  • Nếu cmd = 4: tiếp theo sẽ là 2 số nguyên x, y, tương ứng với get_min_distance (x, y)
  • Nếu cmd = 0: kết thúc testcase.

Output:

• với mỗi lệnh cmd = 4: get_min_distance (x, y) in ra độ dài nhỏ nhất từ tọa độ (x, y) tới chiếc taxi còn hoạt động gần nhất, nếu không có in ra -1;

Example:

Input:

1
1 18467 4 0
4 4 3
4 2 4
2 18467
1 16827 1 1
2 16827
1 5436 1 4
1 153 2 2
1 18716 3 0
4 1 1
4 4 2
4 4 0
0

Output:

3
6
2
2
1