마라톤 부분 코스

베시는 마라톤을 즐겨 달리는 소이고, 동료 소가 달릴 마라톤 코스를 직접 설계한다. 가장 최근에 만든 코스는 체크포인트 $N$개로 이루어지고, 소는 이 체크포인트를 주어진 순서대로 방문해야 한다.

코스가 도로가 격자로 놓인 도심에 있어서, 위치가 $(x_1, y_1)$인 체크포인트와 위치가 $(x_2, y_2)$인 체크포인트 사이의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

동료 소는 코스 전체를 완주할 체력이 없을지도 모른다. 그래서 베시는 부분 코스를 달리는 데 걸리는 시간을 알고 싶다. 부분 코스는 코스 전체에서 연속으로 잘라낸 체크포인트 구간이다. 소는 게을러서 부분 코스를 달릴 때 체크포인트 하나를 건너뛸 수 있고, 이동 거리의 합이 가장 작아지는 체크포인트를 고른다. 아무것도 건너뛰지 않아도 된다. 다만 부분 코스의 첫 번째 체크포인트와 마지막 체크포인트는 건너뛸 수 없다. 따라서 체크포인트가 한 개나 두 개인 부분 코스에는 건너뛸 체크포인트가 없다.

베시는 코스를 다듬으면서 체크포인트 위치를 옮겨 보려 한다. 위치를 바꾸는 갱신과 부분 코스를 묻는 질의를 주어진 순서대로 처리하라.

첫째 줄에 $N$과 $Q$가 주어진다. ($1 \le N \le 100000$, $1 \le Q \le 100000$)

다음 $N$개 줄에는 방문해야 하는 순서대로 체크포인트의 좌표 $x$와 $y$가 주어진다. 모든 좌표는 $-1000$ 이상 $1000$ 이하의 정수다.

다음 $Q$개 줄에는 갱신 또는 질의가 한 줄에 하나씩 주어지고, 주어진 순서대로 처리해야 한다. 각 줄은 U I X Y 또는 Q I J 형식이다.

• U I X Y는 $I$번 체크포인트의 위치를 $(X, Y)$로 바꾼다. ($1 \le I \le N$, $-1000 \le X, Y \le 1000$)
• Q I J는 $I$번 체크포인트에서 $J$번 체크포인트까지의 부분 코스를 달릴 때 이동 거리 합의 최솟값을 묻는다. ($1 \le I \le J \le N$) 이때 $I$번과 $J$번을 제외한 체크포인트 중 최대 하나를 건너뛸 수 있다.

Q 질의마다 이동 거리 합의 최솟값을 한 줄에 출력한다.