An avid marathon runner herself, Bessie enjoys creating marathon courses. She has designed a route specified by N checkpoints (1 <= N <= 100,000) that must be visited in sequence.

Bessie wants to know how long certain sub-routes take to run, where a sub-route is a contiguous subsequence of the checkpoints. 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.

Bessie wants to investigate making changes to checkpoint locations. Please help her determine how certain changes will affect the time required to run different sub-routes (taking into account that the cows might omit one checkpoint). The distance between (x1, y1) and (x2, y2) is the Manhattan distance |x1-x2| + |y1-y2|.

Line 1: N and Q (1 <= Q <= 100,000).

Lines 2..1+N: The (x, y) locations of N checkpoints in sequence. All coordinates in the range -1000 .. 1000.

Lines 2+N..1+N+Q: Updates and queries, one per line. "U I X Y" changes the location of checkpoint I to (X, Y). "Q I J" asks for the minimum travel time of the sub-route from checkpoint I to checkpoint J (I <= J), given the cows skip one checkpoint along this sub-route (but not the endpoints).

For each query, output on a single line the desired minimum sub-route length.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Gold