Với một khao khát trở thành một vận động viên chạy marathon thực thụ trên con đường Olympic, thầy Luna rất hào hứng khi tạo ra một đường đua chạy marathon cho những SV của mình, điều mà thầy đã từng không làm được. Thầy vừa tạo ra một tuyến đường gồm ~n~ cột mốc trong mặt phẳng tọa độ Oxy được đánh số theo thứ tự từ ~1~ đến ~n~. Không may thay, thầy nhận ra rằng những SV có thể không có đủ thể lực để chạy hết quãng đường này. Vì vậy thầy muốn biết độ dài của một số đoạn đường con nhất định: bắt đầu từ cột mốc ~i~ và kết thúc tại cột mốc ~j~, SV phải tìm đường đi trên đoạn này có độ dài nhỏ nhất. Vì đường đua được thiết kế ở khu vụ trung tâm thành phố gồm mạng lưới các đường phố nên khoảng cách giữa hai cột mốc ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~|x_1-x_2| + |y_1-y_2|~. Ngoài ra, để xây dựng đường đua chạy marathon tốt nhất có thể, thầy muốn tìm ra sự ảnh hưởng của việc thay đổi những cột mốc mà thầy đã có trên đường đua hiện tại. Hãy giúp thầy xác định những thay đổi cột mốt này sẽ ảnh hưởng tới thời gian cần thiết để những SV chạy những tuyến đường con khác nhau như thế nào?

Input

Dòng đầu tiên ghi hai số nguyên dương ~n,Q~ với ~1≤n, Q≤10^5~, trong ~n~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~x,y~ là tọa độ một cột mốc theo thứ tự mà các SV phải chạy qua trên tuyến đường. Tọa độ có giá trị nằm trong khoảng ~[-10^3,10^3]~.

Trong ~Q~ dòng tiếp theo, mỗi dòng mô tả một câu hỏi hoặc một thay đổi cần thực hiện theo thứ tự. Nó sẽ có một trong hai dạng:

• U i x y: điểm cột mốc ~i~ sẽ được di chuyển đến vị trí ~(x,y)~
• Q i j : thời cần thiết nhỏ nhất để chạy từ cột mốc ~i~ đến cột mốc ~j~ với ~i≤j~ với điều kiện những SV có thể bỏ qua một cột mốc dọc theo tuyến đường từ ~i~ đến ~j~ (không bao gồm ~i~ và ~j~.

Output:

Với mỗi câu hỏi về thời gian đi trên một tuyến đường in ra một số nguyên trên một dòng là thời gian nhỏ nhất tìm được.

Sample input

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

Sample output

11
8
8