2 ЛКШ

//  #define pragma

#ifdef pragma
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // pragma

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define all(x) begin(x), end(x)
#define pb push_back
#define x first
#define y second
#define int long long
#define zero(two) memset(two, 0, sizeof(two))

using namespace std;
using namespace __gnu_pbds;


typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<vi> matrix;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    cout << fixed << setprecision(10);
    #if 0
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
}

const int MAXN = 2e3 + 10;
const int INF = 1e15 + 7;
const int MAXLOG = 31;
const int MOD = 998244353;
const int BASE = 47;

struct node {
    int mn, ind;
};

vector<int> t;
vector<node> t2;
vector<pii> a;

int dist(pii a, pii b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void build(int v, int tl, int tr) {
    if(tl == tr) {
        t[v] = dist(a[tl], a[tl + 1]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm);
    build(v * 2 + 2, tm + 1, tr);
    t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

void build2(int v, int tl, int tr) {
    if(tl == tr) {
        t2[v] = {-dist(a[tl - 1], a[tl]) - dist(a[tl], a[tl + 1]) + dist(a[tl - 1], a[tl + 1]), tl};
        return;
    }
    int tm = (tl + tr) >> 1;
    build2(v * 2 + 1, tl, tm);
    build2(v * 2 + 2, tm + 1, tr);
    if(t2[v * 2 + 1].mn < t2[v * 2 + 2].mn) {
        t2[v] = t2[v * 2 + 1];
    }
    else {
        t2[v] = t2[v * 2 + 2];
    }
}

int get_sum(int v, int tl, int tr, int l, int r) {
    if(tl > r || tr < l) {
        return 0;
    }
    if(tl >= l && tr <= r) {
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    int left = get_sum(v * 2 + 1, tl, tm, l, r);
    int right = get_sum(v * 2 + 2, tm + 1, tr, l, r);
    return left + right;
}

node get_min(int v, int tl, int tr, int l, int r) {
    if(tl > r || tr < l) {
        return {INF, -1};
    }
    if(tl >= l && tr <= r) {
        return t2[v];
    }
    int tm = (tl + tr) >> 1;
    node left = get_min(v * 2 + 1, tl, tm, l, r);
    node right = get_min(v * 2 + 2, tm + 1, tr, l, r);
    if(left.mn < right.mn) {
        return left;
    }
    else {
        return right;
    }
}

void update(int v, int tl, int tr, int pos) {
    if(tl > pos || tr < pos) {
        return;
    }
    if(tl == tr) {
        t[v] = dist(a[tl], a[tl + 1]);
        return;
    }
    int tm = (tl + tr) >> 1;
    update(v * 2 + 1, tl, tm, pos);
    update(v * 2 + 2, tm + 1, tr, pos);
    t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

void update2(int v, int tl, int tr, int pos) {
    if(tl > pos || tr < pos) {
        return;
    }
    if(tl == tr) {
        t2[v].mn = -dist(a[tl - 1], a[tl]) - dist(a[tl], a[tl + 1]) + dist(a[tl - 1], a[tl + 1]);
        return;
    }
    int tm = (tl + tr) >> 1;
    update2(v * 2 + 1, tl, tm, pos);
    update2(v * 2 + 2, tm + 1, tr, pos);
    if(t2[v * 2 + 1].mn < t2[v * 2 + 2].mn) {
        t2[v] = t2[v * 2 + 1];
    }
    else {
        t2[v] = t2[v * 2 + 2];
    }
}

signed main() {
    seriy();
    int n, q;
    cin >> n >> q;
    a.resize(n);
    t.resize(4 * n);
    t2.resize(4 * n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    build(0, 0, n - 2);
    build2(0, 1, n - 2);
    while(q--) {
        char t;
        cin >> t;
        if(t == 'Q') {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            if(x == y) {
                cout << 0 << '\n';
                continue;
            }
            int mn = 0;
            if(x + 1 <= y - 1) mn = get_min(0, 1, n - 2, x + 1, y - 1).mn;
            int ans = get_sum(0, 0, n - 2, x, y - 1) + min(mn, 0ll);
            cout << ans << '\n';
        }
        else {
            int pos, x, y;
            cin >> pos >> x >> y;
            pos--;
            a[pos] = {x, y};
            if(pos > 0 && pos < n - 1) {
                update2(0, 1, n - 2, pos);
            }
            if(pos < n - 1) {
                update(0, 0, n - 2, pos);
            }
            if(pos - 1 > 0 && pos - 1 < n - 1) {
                update2(0, 1, n - 2, pos - 1);
            }
            if(pos >= 0 && pos - 1 < n - 1) {
                update(0, 0, n - 2, pos - 1);
            }
            if(pos + 1 > 0 && pos + 1 < n - 1) {
                update2(0, 1, n - 2, pos + 1);
            }
        }
    }
    return 0;
}