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|.

#3900 upload - done - how_to_reg -

Marathon timer 1s memory 256MB

#3900

Marathon 1s 256MB