Marathon Course Optimization

Bessie, an avid marathon runner, has designed a marathon course with N checkpoints (1 ≤ N ≤ 100,000) that must be visited in order. However, she worries that some of the cows might not have enough stamina to run the full route. Therefore, when the cows run any sub‐route (a contiguous segment of checkpoints), they are allowed to skip one checkpoint, other than the first and last in that sub-route, in order to minimize the total travel time.

The travel distance between two checkpoints at coordinates \( (x_1, y_1) \) and \( (x_2, y_2) \) is defined using the Manhattan distance formula: \[ |x_1 - x_2| + |y_1 - y_2| \]

If a cow chooses to skip an internal checkpoint \(b\) (with neighbors \(a\) and \(c\)), the saving is computed as follows:

[ \text{saving} = d(a, b) + d(b, c) - d(a, c) ]

Bessie also plans to make changes to checkpoint locations. Your task is to process a sequence of operations which include queries and updates. For a query, you should output the minimum total travel time for a specified sub‐route, taking into account the possibility of skipping one checkpoint. For an update, you are given a new coordinate for a checkpoint.

inputFormat

The first line contains two integers N and Q, where N is the number of checkpoints and Q is the number of operations.

The next N lines each contain two integers x and y, representing the initial coordinates of the checkpoints (1-indexed).

The following Q lines each describe an operation in one of the two formats:

• Q l r — Query the minimum travel time on the sub-route from checkpoint l to checkpoint r (inclusive). The cows are allowed to skip one checkpoint from the sub-route except for the endpoints.
• U i x y — Update the coordinates of checkpoint i to new values x and y.

outputFormat

For each query (operation starting with Q), output the minimum travel time for the specified sub-route.

sample

5 5
0 0
2 2
3 1
5 3
6 4
Q 1 5
U 3 4 4
Q 2 4
U 5 10 10
Q 1 5

10
4
20