Степан спланував марафон, специфікувавши ~N~ контрольних точок, які слід послідовно відвідати.

Степан розуміє, що учасники можуть не захотіти бігти весь маршрут, і тому він хоче дізнатись, яку довжину мають певні підмаршрути. Підмаршрутом він називає безперервну підпослідовність контрольних точок повного маршруту. Він знає також, що деякі учасники можуть захотіти пропустити одну контрольну точку під час пробігу по підмаршруту (їм не дозволяється пропустити першу чи останню контрольну точку підмаршруту).

Для того, щоб побудувати найкращий маршрут, Степан хоче досліджувати наслідки виконання змін у розташуванні контрольних точок його поточного маршруту. Допоможіть йому визначити, як певні зміни розташування контрольних точок впливають на час, необхідний для проходження різних підмаршрутів (зважаючи на те, що учасники можуть вибрати пропуск однієї контрольної точки під час пробігу підмаршрутом).

Оскільки марафон проходить на вулицях Манхеттена, то відстань між двома точками (~x_1,y_1~) та (~x_2,y_2~) манхетенська: ~|x_1-x_2| + |y_1-y_2|~.

Input

Перший рядок вхідного файлу містить цілі числа ~N, Q~ (~1 \le N,Q \le 10^5~).

Наступні ~N~ рядків містять цілі числа ~x_i, y_i~ (~-1000 \le x_i,y_i \le 1000~). Контрольні пункти задаються у тому порядку, в якому їх треба відвідати.

Далі ідуть ~Q~ рядків, які містять запити по одному у рядку:

- рядки мають формат: "U I X Y" або "Q I J". Рядок "U I X Y" вказує, що положення точки з номером ~I~ (~1 \le I \le N~)  має бути змінено на (~X,Y~). Рядок "Q I J" опитує мінімальну відстань проходження маршруту від контрольної точки ~I~ до контрольної точки ~J~ (~I \le J~), з врахуванням того, що учасники можуть пропустити одну контрольну точку цього підмаршруту (крім точок ~I~ і ~J~).

Числа у рядках розділяються пропуском.

Output

У вихідний файл для кожного підмаршруту виведіть в окремому рядку мінімальну відстань.

Sample Input 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

Sample Output 1

11
8
8