题目描述

$\red{yjq }$要被 $\red{n(n<=100,000)}$个 $\red{zhx }$按顺序吊打，第 $\red{i }$个 $\red{zhx }$在平面上的坐标为$\red{(xi, yi)}$。 从$\red{(x1,y1)}$被吊打到$\red{(x2,y2)}$的代价为$\red{|x1-x2|+|y1-y2|}$ 有 $\red{m(m<=100,000)}$次操作。

$\red{U }$操作：第 $\red{i }$个 $\red{zhx }$的位置改为$\red{(xnew, ynew)}$。

$\red{Q }$操作：$\red{yjq }$要被编号从 $\red{i }$到 $\red{j }$的 $\red{zhx }$按顺序吊打，但是 $\red{yjq }$可以选择跳过编号在$\red{[i+1, j-1]}$中的 一个 $\red{zhx，}$问 $\red{yjq }$最少要走多远的路。

输入格式

第一行 $\red{n,m}$ 下面 $\red{n }$行每行两个数 $\red{x,y,}$表示第 $\red{i }$个点的坐标$\red{(x,y)(}$范围是$\red{-1000 .. 1000)}$ 下面 $\red{m }$行，两种类型操作：

$\red{U i (xnew, ynew)}$

$\red{Q i j}$ 意义如上所述

输出格式

每个询问输出最小代价

样例

输入样例

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