THICHAY Thi chạy

Giờ kiểm tra thể dục, lớp chuyên Tin phải thực hiện bài chạy qua các khu vực trong sân thể thao của trường. Sơ đồ đường chạy gồm N trạm được đánh số từ 1 đến N. Mỗi trạm là một điểm trên sân có tọa độ (x, y). Khoảng cách giữa hai trạm (x₁, y₁) và (x₂, y₂) được tính theo công thức |x₁ - x₂| + | y₁ - y₂|.

            Mỗi bạn phải chạy qua một số trạm liên tiếp nhau của sơ đồ đường chạy theo thứ tự. Bạn thứ i sẽ chạy qua các trạm A_i, A_i+1, …, B_i (A_i < B_i). Trạm A_i là trạm bắt đầu và trạm B_i là trạm thúc kết thúc. Ưu tiên cho lớp chuyên tin, thầy giáo cho phép mỗi bạn được bỏ qua 1 trạm để rút ngắn tổng khoảng cách chạy của mình. Đương nhiên không được bỏ trạm xuất phát A_i và trạm đích B_i.

            Trong quá trình thi, thầy giáo có thể thay đổi vị trí một số trạm để tạo ra sơ đồ đường chạy mới. Các bạn thi sau phải chạy theo sơ đồ mới này.

            Yêu cầu: em hãy giúp các bạn lớp chuyên Tin tính khoảng cách tối thiểu mà mỗi bạn phải chạy nếu được bỏ qua 1 trạm.

Input

• Dòng đầu tiên cho các giá trị của N Q. (3 ≤ N ≤ 500; Q ≤ 10⁵)
•  N dòng tiếp theo, dòng thứ i ghi hai số nguyên X_i Y_i, là tọa độ trạm thứ i (-1000 ≤ X_i, Y_i ≤ 1000). Các trạm được ghi theo thứ tự phải chạy.
• Q dòng tiếp theo, mỗi dòng dạng U I X Y hoặc Q I J.
• Dòng có dạng U I X Y cho biết thầy giáo sẽ thay đổi vị trí trạm I đến tọa đô mới (X, Y). (1 ≤ I ≤ N).
• Dòng có dạng Q A B, yêu cầu cho biết quãng đường chạy ngắn nhất của một học sinh từ trạm A đến trạm B (A+2 ≤ B), học sinh đó được bỏ qua 1 trạm (khác A và B).

Output: Mỗi dòng ghi câu trả lời cho một truy vấn loại Q theo thứ tự.

Input	Output	Giải thích
5 5 -4 4 -5 -3 -1 5 -3 4 0 5 Q 1 5 U 4 0 1 U 4 -1 1 Q 2 4 Q 1 4	11 8 8	truy vấn 1, học sinh phải chạy qua các trạm 1 – 3 – 4 – 5, bỏ trạm 2 truy vấn 2, học sinh chạy qua các trạm 2 – 4, bỏ trạm 3 truy vấn 3, học sinh chạy qua các trạm 1 – 3 – 4, bỏ trạm 2.