题目描述

作为一名狂热的马拉松运动员，贝西喜欢创造马拉松 她的母牛同伴要跑的路线。她最近设计了一个 由$\red{N}$个检查点$\red{（1<=N<=100000）}$指定的路线，必须 按顺序访问。

不幸的是，贝西意识到其他奶牛可能没有 跑完全程的耐力。因此她想知道要多久 某些子路由需要运行，其中子路由是连续的 完整路径中检查点的子序列。制造问题 更复杂的是，贝西知道，其他懒惰的奶牛可能会 选择在运行子路由时跳过一个检查点$\red{--}$ 无论哪一个导致最小总行程时间。他们不是 但是，允许跳过子路由中的第一个或最后一个检查点。

为了建造最好的马拉松球场，贝西想 调查更改检查点的后果 她当前课程中的位置。请帮助她确定如何 检查点位置的某些更改将影响所需时间 运行不同的子路线（考虑到奶牛可能 选择在运行子路由时忽略一个检查点）。

由于球场设置在市中心，街道呈网格状，因此 位置$\red{（x1，}$$\red{y1）}$和$\red{（x2，}$$\red{y2）}$处两个检查点之间的距离为 由$\red{| x1-x2 |+| y1-y2 |}$给出。

输入格式

第一行给出$\red{N}$和$\red{Q（}$$\red{1<=Q<=100000）}$。

接下来的$\red{N}$行包含中$\red{N}$个检查点的$\red{（x，}$$\red{y）}$位置 他们必须沿途参观。所有坐标 在范围内$\red{-1000}$。。$\red{1000}$

接下来的$\red{Q}$行由更新和查询组成，每行一个 按给定顺序处理。行将采用以下形式： "$\red{U I X Y}$"或"$\red{Q I J}$"。"$\red{U I X Y}$"形式的一行表示 检查点$\red{I（}$$\red{1<=I<=N）}$的位置将更改为位置$\red{（X，}$$\red{Y）}$。形式为"$\red{Q I J}$"的一行要求最小行程时间 从检查点$\red{I}$到检查点$\red{J（}$$\red{I<=J）}$的子路径，给定 奶牛选择跳过此子路线上的一个检查点（但是 不是端点$\red{I}$和$\red{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