[USACO14DEC] Marathon G

作为一名狂热的马拉松长跑运动员，贝茜喜欢为她的同伴们开设马拉松课程。她最近设计了一个有N个检查点的路线(1 < = N < = 100,000)，必须按顺序经过。 不幸的是，贝茜意识到其他的奶牛可能没有足够的耐力跑完全程。因此，她想知道特定的子路线需要多长时间才能跑完，其中的子路线是从完整路线的检查点中截取的的连续子序列。让事情变得更复杂的是，贝西知道其他的牛十分懒惰，可能会选择在任何时候跳过一个检查点——无论哪一种方法都能在最短的时间内完成。然而，他们不允许在子路线中跳过第一个或最后一个检查点。 为了建造最好的马拉松赛道，贝茜想要研究一下在她目前的课程中对检查点位置做出改变后可能造成的后果。请帮助她确定检查点位置的哪些更改将会影响运行不同子路线所需的时间(考虑到奶牛可能会选择在子路线跑步时忽略一个检查点)。 由于该课程设置在市中心的街道网络中，两个检查点之间的距离(x1,y1)和(x2,y2)是由| x1 - x2 | + | y1 - y2 |得出的。

An avid marathon runner herself, Bessie enjoys creating marathon courses for her fellow cows to run. She has most recently designed a route specified by N checkpoints (1 <= N <= 100,000) that must be visited in sequence. Unfortunately, Bessie realizes that the other cows may not have the stamina to run the full route. She therefore wants to know how long certain sub-routes take to run, where a sub-route is a contiguous subsequence of the checkpoints from the full route. To make matters more complicated, Bessie knows that the other cows, being lazy, might choose to skip one checkpoint any time they run a sub-route -- whichever one results in a minimum total travel time. They are not allowed to skip the first or last checkpoints in a sub-route, however. In order to build the best possible marathon course, Bessie wants to investigate the ramifications of making changes to the checkpoint locations in her current course. Please help her determine how certain changes to checkpoint locations will affect the time required to run different sub-routes (taking into account that the cows might choose to omit one checkpoint any time they run a sub-route). Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

INPUT: (file marathon.in) The first line gives N and Q (1 <= Q <= 100,000). The next N lines contain (x, y) locations of N checkpoints in the sequence they must be visited along the route. All coordinates are in the range -1000 .. 1000. The next Q lines consist of updates and queries, one per line, to be processed in the order they are given. Lines will either take the form "U I X Y" or "Q I J". A line of the form "U I X Y" indicates that the location of checkpoint I (1 <= I <= N) is to be changed to location (X, Y). A line of the form "Q I J" asks for the minimum travel time of the sub-route from checkpoint I to checkpoint J (I <= J), given that the cows choose to skip one checkpoint along this sub-route (but not the endpoints I and J).

OUTPUT: (file marathon.out) For each sub-route length request, output on a single line the desired length.

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