1946. 马拉松

【题目描述】

作为一个狂热的马拉松爱好者，Bessie喜欢为她的同行们设计马拉松比赛。她最近刚设计了一款包含N(1 <= N <= 100,000)个检查站的马拉松比赛，比赛要求选手们必须依次通过这N个检查站。

不过，Bessie意识到很多牛们都没有体力跑完全程，她们会选择只跑其中一段。因此，她想知道其中的一段子赛程的长度，子赛程是由全赛程中一些相邻的检查站所组成的。Bessie还知道其它牛们都很懒，她们在跑某段子赛程时会跳过其中一个检查站——那个会导致该段赛程总长最小的检查站。不过不允许她们跳过该段子赛程中的第一个和最后一个点。

为了创建最可行的马拉松比赛，Bessie想调查一下如果改变当前赛程中某个检查站的位置会带来什么影响，请帮她计算改变某个检查站的位置后，跑完某段子赛程所需的最小长度，请注意奶牛们会在这段子赛程中跳过一个检查站。

因为比赛场地设在一个网格区域内，两个检查站之间距离的计算方法是：设两者位置坐标分别为(x1, y1)和(x2, y2)，则距离为|x1-x2| + |y1-y2|。

【输入格式】

第一行有两个数N和Q(1 <= Q <= 100,000)；

接下来有N行，每行为一个检查站的位置坐标x,y，这N个点给出的顺序即为跑完全程所需依次经过的顺序，所有的坐标值均为-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

【提示】

在此键入。

【来源】

在此键入。