题目描述

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

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

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

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

输入格式

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

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

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