문제

마라톤을 좋아하는 민준이는 동아리 부원들을 위해 새로운 마라톤 코스를 설계했다. 이 코스는 순서대로 방문해야 하는 $N$개의 체크포인트로 이루어져 있다. ($1 \le N \le 100\,000$)

하지만 동아리 부원들은 체력이 부족하여 전체 코스를 완주하기 어려워한다. 따라서 부원들은 특정 구간(연속된 체크포인트들의 부분 수열)을 달릴 때, 중간에 있는 체크포인트 중 하나를 건너뛰어 이동 거리를 최소화하려고 한다. 단, 구간의 시작점과 끝점은 절대 건너뛸 수 없다. 만약 구간 내에 건너뛸 수 있는 체크포인트가 없다면 모든 체크포인트를 방문해야 한다.

민준이는 코스를 최적화하기 위해 중간에 체크포인트의 위치를 변경하기도 한다. 특정 구간이 주어졌을 때, 부원들이 체크포인트를 하나 건너뛰어 달릴 수 있는 최소 이동 거리를 구하는 프로그램을 작성하시오.

코스는 격자 모양의 도로망이 있는 도심에 위치하므로, 두 체크포인트 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 맨해튼 거리인 $|x_1 - x_2| + |y_1 - y_2|$로 계산한다.

입력

첫째 줄에 체크포인트의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\,000$)

이어서 $N$개의 줄에 걸쳐 각 체크포인트의 $(x, y)$ 좌표가 방문 순서대로 주어진다. 모든 좌표는 $-1,000$ 이상 $1,000$ 이하의 정수이다.

다음 $Q$개의 줄에는 업데이트 또는 쿼리 정보가 한 줄에 하나씩 주어진 순서대로 주어진다.

• U I X Y: $I$번째 체크포인트의 위치를 $(X, Y)$로 변경한다. ($1 \le I \le N$)
• Q I J: $I$번 체크포인트부터 $J$번 체크포인트까지의 구간에서, 중간에 있는 체크포인트를 최대 하나 건너뛰었을 때의 최소 이동 거리를 구한다. ($1 \le I \le J \le N$)

출력

각 Q 쿼리에 대해, 계산된 최소 이동 거리를 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

11
8
8