Là một người rất mê chạy marathon, Bessie thích tạo ra các đường chạy marathon cho những cô bò khác. Gần đây nhất, cô đã thiết kế một đường chạy gồm \(N\) checkpoint (\(1 \le N \le 100\,000\)) phải được ghé thăm theo thứ tự.

Không may, Bessie nhận ra rằng những cô bò khác có thể không đủ sức bền để chạy toàn bộ đường chạy. Vì vậy, cô muốn biết một số đường chạy con cần bao lâu để hoàn thành, trong đó một đường chạy con là một dãy con liên tiếp của các checkpoint trên toàn bộ đường chạy. Mọi chuyện còn phức tạp hơn vì Bessie biết rằng những cô bò khác vốn lười biếng có thể chọn bỏ qua một checkpoint mỗi khi chạy một đường chạy con — checkpoint nào giúp tổng thời gian di chuyển nhỏ nhất. Tuy nhiên, họ không được phép bỏ qua checkpoint đầu tiên hoặc cuối cùng của một đường chạy con.

Để xây dựng đường chạy marathon tốt nhất có thể, Bessie muốn nghiên cứu hệ quả của việc thay đổi vị trí các checkpoint trên đường chạy hiện tại. Hãy giúp cô xác định những thay đổi nhất định đối với vị trí checkpoint sẽ ảnh hưởng thế nào đến thời gian cần thiết để chạy các đường chạy con khác nhau, có tính đến việc các cô bò có thể chọn bỏ qua một checkpoint mỗi khi chạy một đường chạy con.

Vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1 \le Q \le 100\,000\)).

\(N\) dòng tiếp theo chứa các vị trí \((x,y)\) của \(N\) checkpoint theo thứ tự phải ghé thăm trên đường chạy. Tất cả các tọa độ đều nằm trong khoảng từ \(-1000\) đến \(1000\).

\(Q\) dòng tiếp theo gồm các thao tác cập nhật và truy vấn, mỗi dòng một thao tác, được xử lý theo đúng thứ tự xuất hiện. Mỗi dòng có dạng U I X Y hoặc Q I J. Dòng có dạng U I X Y cho biết vị trí của checkpoint \(I\) (\(1 \le I \le N\)) được đổi thành \((X,Y)\). Dòng có dạng Q I J yêu cầu thời gian di chuyển nhỏ nhất của đường chạy con từ checkpoint \(I\) đến checkpoint \(J\) (\(I \le J\)), với điều kiện các cô bò chọn bỏ qua một checkpoint trên đường chạy con này, nhưng không bỏ qua hai đầu mút \(I\) và \(J\).

Dữ liệu ra

Với mỗi yêu cầu tính độ dài đường chạy con, in độ dài cần tìm trên một dòng riêng.

Ví dụ

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

Nguồn

USACO 2014 December Contest, Gold — Marathon. Tác giả đề: Nick Wu, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=495