Marathon (Gold)

Có $N$ điểm kiểm tra trên mặt phẳng. Một vận động viên đi từ điểm $I$ đến điểm $J$ (theo thứ tự $I,I+1,\dots ,J$), và được phép bỏ qua đúng một điểm kiểm tra trung gian (không được bỏ điểm $I$ hoặc $J$) để rút ngắn quãng đường.

Khoảng cách giữa hai điểm được tính theo khoảng cách Manhattan: $|x_1-x_2|+|y_1-y_2|$.

Cho $Q$ truy vấn, mỗi truy vấn là một trong hai loại:

• U k x y — cập nhật toạ độ điểm $k$ thành $(x,y)$.
• Q I J — hỏi quãng đường ngắn nhất từ $I$ đến $J$ (có thể bỏ qua một điểm trung gian).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $Q$.

• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$, $y_i$ — toạ độ điểm kiểm tra thứ $i$.

• $Q$ dòng tiếp theo, mỗi dòng là truy vấn dạng U k x y hoặc Q I J (với $1\le I<J\le N$).

Dữ liệu ra

Với mỗi truy vấn Q I J, in ra quãng đường ngắn nhất trên một dòng.

Ràng buộc

• $1\le N,Q\le 100000$
• $-1000\le x_i,y_i\le 1000$
• Với truy vấn Q: $1\le I<J\le N$
• Với truy vấn U: $1\le k\le N$

Ví dụ