Với một khao khát trở thành một vận động viên chạy marathon thực thụ, Bessie rất hào hứng khi tạo ra một đường đua chạy marathon cho những con bò cùng trang lứa với cô ta. Cô ta vừa tạo ra một tuyến đường gồm ~n~ cột mốc ~(1 \le n \le 10^5)~ mà phải được chạy qua theo thứ tự.

Không may thay, Bessie nhận ra rằng những con bò khác có thể không có đủ thể lực để chạy hết quãng đường này. Vì vậy cô ta muốn biết độ dài của một số đoạn đường con nhất định, trong đó một đoạn đường con là một dãy liên tiếp các cột mốc từ tuyến đường ban đầu.

Để làm mọi thứ trở nên phức tạp hơn, Bessie biết rằng những con bò lười khác có thể bỏ qua một cột mốc ở bất kỳ lúc nào khi chúng chạy trên một tuyến đường con, miễn là kết quả chạy tuyến đường con này là nhỏ nhất. Tuy nhiên, chúng không được bỏ qua cột mốc đầu tiên và cột mốc cuối cùng.

Ngoài ra, để xây dựng đường đua chạy marathon tốt nhất có thể, Bessie muốn tìm ra sự ảnh hưởng của việc thay đổi những cột mốc mà cô ta đã có trên đường đua hiện tại. Hãy giúp cô ta xác định những thay đổi cột mốc này sẽ ảnh hưởng tới thời gian cần thiết để những con bò chạy những tuyến đường con khác nhau như thế nào.

Tại vì đường đua được thiết kế ở khu vực 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|~.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n,Q~ ~(1 \le n,Q \le 10^5)~;

• ~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 con bò phải chạy qua trên tuyến đường. Tọa độ có giá trị nằm trong khoảng ~[-10^3,10^3]~;

• ~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ó có một trong hai dạng:

  • U ~i,x,y~: Cột mốc ~i~ sẽ được di chuyển đến vị trí ~(x,y)~;

  • Q ~i,j~: Thời gian cần thiết nhỏ nhất để chạy từ cột mốc ~i~ đến cột mốc ~j~ ~(i \le j)~ với điều kiện những con bò 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 1

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 1

11
8
8