#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;

#ifdef ONLINE_JUDGE
#define whatis(x) ;
#endif
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, array<T,4> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 300007

int t[N << 2];
bool lazy[N << 2]; // czy jest xor nizej

// xor xoru = 0?
// -> nie set 1 tylko xor?

/* namespace iter{ */

/* int n; */
/* int t[N << 1]; */
/* int h = sizeof(int) * 8 - __builtin_clz(N); */
/* bool d[N]; */
/* /1* int ile[N << 1]; *1/ */

/* void calc(int p, int k) { */
/*   /1* if (d[p] == 0) t[p] = t[p<<1] + t[p<<1|1]; *1/ */
/*   /1* else t[p] = d[p] * k; *1/ */
/*   if (d[p] == 0) t[p] = t[p<<1] + t[p<<1|1]; */
/*   /1* else t[p] = (k - t[p] * k); *1/ */
/*   else t[p] = (k - t[p]); */
/* } */

/* void apply(int p, int value, int k) { */
/*     /1* if(d[p]){ *1/ */
/*     /1*     d[p] ^= 1; *1/ */
/*     /1*     return; *1/ */
/*     /1* } *1/ */
/*   /1* t[p] = value * k; *1/ */
/*   /1* if (p < n) d[p] = value; *1/ */
/*   t[p] = (k - t[p]); */
/*   /1* if (p < n) d[p] = value; *1/ */
/*   if (p < n) d[p] ^= 1; */
/* } */

/* void build(int l, int r) { */
/*   int k = 2; */
/*   for (l += n, r += n-1; l > 1; k <<= 1) { */
/*     l >>= 1, r >>= 1; */
/*     for (int i = r; i >= l; --i) calc(i, k); */
/*   } */
/* } */

/* void push(int l, int r) { */
/*   int s = h, k = 1 << (h-1); */
/*   for (l += n, r += n-1; s > 0; --s, k >>= 1) */
/*     for (int i = l >> s; i <= r >> s; ++i) if (d[i] != 0) { */
/*       apply(i<<1, d[i], k); */
/*       apply(i<<1|1, d[i], k); */
/*       d[i] = 0; */
/*     } */
/* } */

/* void modify(int l, int r, int value) { */
/*   /1* if (value == 0) return; *1/ */
/*   push(l, l + 1); */
/*   push(r - 1, r); */
/*   int l0 = l, r0 = r, k = 1; */
/*   for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) { */
/*     if (l&1) apply(l++, value, k); */
/*     if (r&1) apply(--r, value, k); */
/*   } */
/*   build(l0, l0 + 1); */
/*   build(r0 - 1, r0); */
/* } */

/* /1* void modify(int l, int r, int value) { *1/ */
/* /1*   /2* if (value == 0) return; *2/ *1/ */
/* /1*   push(l, l + 1); *1/ */
/* /1*   push(r - 1, r); *1/ */
/* /1*   bool cl = false, cr = false; *1/ */
/* /1*   int k = 1; *1/ */
/* /1*   for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) { *1/ */
/* /1*     if (cl) calc(l - 1, k); *1/ */
/* /1*     if (cr) calc(r, k); *1/ */
/* /1*     /2* if (l&1) apply(l++, value, k), cl = true; *2/ *1/ */
/* /1*     /2* if (r&1) apply(--r, value, k), cr = true; *2/ *1/ */
/* /1*     if (l&1) apply(l++, value, k), cl = true; *1/ */
/* /1*     if (r&1) apply(--r, value, k), cr = true; *1/ */
/* /1*   } *1/ */
/* /1*   for (--l; r > 0; l >>= 1, r >>= 1, k <<= 1) { *1/ */
/* /1*     if (cl) calc(l, k); *1/ */
/* /1*     if (cr && (!cl || l != r)) calc(r, k); *1/ */
/* /1*   } *1/ */
/* /1* } *1/ */

/* int query(int l, int r) { */
/*   push(l, l + 1); */
/*   push(r - 1, r); */
/*   int res = 0; */
/*   for (l += n, r += n; l < r; l >>= 1, r >>= 1) { */
/*     if (l&1) res += t[l++]; */
/*     if (r&1) res += t[--r]; */
/*   } */
/*   return res; */
/* } */
/* } */

/* void build(int v, int tl, int tr, int arr[]){ */
/*     if(tl == tr){ */
/*         t[v] = arr[tl]; */
/*         return; */
/*     } */
/*     int tm = (tl+tr)>>1; */
/*     build(v<<1,tl,tm,arr); */
/*     build(v<<1|1,tm+1,tr,arr); */
/*     t[v] = t[v<<1] + t[v<<1|1]; */
/* } */

void push(int v, int tl, int tr){
    /* if(lazy[v]){ */
        int tm = (tl+tr)>>1;
        t[v<<1] = (tm-tl+1) - t[v<<1];
        t[v<<1|1] = (tr-tm) - t[v<<1|1];
        // xor xoru = 0?
        // -> nie set 1 tylko xor?
        /* lazy[v<<1] = 1; */
        /* lazy[v<<1|1] = 1; */
        lazy[v<<1] ^= 1;
        lazy[v<<1|1] ^= 1;
        lazy[v] = 0;
    /* } */
}

void modify(int v, int tl, int tr, int l, int r){
    if(l > r) return;
    if(tl == l && tr == r){
        int nval = (tr-tl+1) - t[v];
        // xor xoru = 0?
        // -> nie set 1 tylko xor?
        /* lazy[v] = 1; */
        lazy[v] ^= 1;
        t[v] = nval;
        return;
    }
    if(lazy[v])
        push(v,tl,tr);
    int tm = (tl+tr)>>1;
    /* if(l <= tm){ */
        modify(v << 1,tl,tm,l,min(tm,r));
    /* } */
    /* if(r >= tm+1){ */
        modify(v << 1 | 1,tm+1,tr,max(l,tm+1),r);
    /* } */
    t[v] = t[v<<1] + t[v<<1|1];
}

int query(int v, int tl, int tr, int l, int r){
    /* whatis(mp(tl,tr)) */
    /* whatis(t[v]) */
    if(l > r) return 0;
    if(tl == l && tr == r){
        return t[v];
    }
    if(lazy[v])
        push(v,tl,tr);
    int tm = (tl+tr)>>1;
    return query(v<<1,tl,tm,l,min(tm,r)) + query(v<<1|1,tm+1,tr,max(l,tm+1),r);
}

/* bool a[2007][2007]; */
ll n;

ll ilrz, il0col, il0row, il1col, il1row; // totals
// forgot to chg that b4 running tests
/* ll ilrzcol[2007]; */
/* ll ilrzrow[2007]; */
ll ilrzcol[N];
ll ilrzrow[N];
/* ll ilxrzcol[N]; */
/* ll ilxrzrow[N]; */
/* ll ilxodbcol[N]; */
/* ll ilxodbrow[N]; */
// nie chcemy cr, tylko sume bardziej
// niech ponizsze beda tymi sumami
/* ll crrzrowltil0col; */
/* ll crrzcolltil0row; */
/* ll crodbrowltil1col; */
/* ll crodbcolltil1row; */
// actually potrzebuje tez normalne ilosci aby aktowac sulmy
/* ll sumrzrowltil0col; */
/* ll sumrzcolltil0row; */
/* ll sumodbrowltil1col; */
/* ll sumodbcolltil1row; */

namespace lazy2 {
    //Lazy Propagation on Increment Modifications, Max queries

    ll t[N << 2];
    ll lazy[N << 2];

    void build(int v, int tl, int tr, int arr[]){
        if(tl == tr){
            t[v] = arr[tl];
            return;
        }
        int tm = (tl+tr)>>1;
        build(v<<1,tl,tm,arr);
        build(v<<1|1,tm+1,tr,arr);
        t[v] = min(t[v<<1] , t[v<<1|1]);
    }

    void push(int v){
        if(lazy[v]){
            lazy[v<<1] += lazy[v];
            lazy[v<<1|1] += lazy[v];
            t[v<<1] += lazy[v];
            t[v<<1|1] += lazy[v];
            lazy[v] = 0;
        }
    }

    void modify(int v, int tl, int tr, int l, int r, int inc){
        if(l > r) return;
        if(tl == l && tr == r){
            t[v] += inc;
            lazy[v] += inc;
            return;
        }
        push(v);
        int tm = (tl+tr)>>1;
        modify(v<<1,tl,tm,l,min(tm,r),inc);
        modify(v<<1|1,tm+1,tr,max(l,tm+1),r,inc);
        t[v] = min(t[v<<1],t[v<<1|1]);
    }

    ll query(int v, int tl, int tr, int l, int r){
        /* if(l > r) return -0x7f7f7f7f; */
        if(l > r) return LONG_LONG_MAX;
        if(tl == l && tr == r){
            return t[v];
        }
        push(v);
        int tm = (tl+tr)>>1;
        return max(
        query(v<<1,tl,tm,l,min(tm,r)),
        query(v<<1|1,tm+1,tr,max(l,tm+1),r)
        );
    }
};

map<pi,bool> st;

/* array<int,4> qus[300000]; */

vector<int> int_points[N]; // [row] -> {cols} -> punkty ktore są w drugiej fazie -> chcemy ich początkową wartość

// moge nie kopiowac, tylko po prostu trzymac l,r, i samemu odpowiednio to zawężać
/* void rec(int tl, int tr, int l, int r){ */
// I guess tak ezer wsm
// to i tak nie jest bottleneckiem cnie
void rec(int tl, int tr, vector<array<int,4>> qus){
    if(tl > tr)
        return;
    // wait, jak jest empty, to wciąż muszę wszystkim rowom info wpisać
    /* if(qus.empty()) */
    /*     return; */
    // -> i guess mogę po prostu nie teturnować tak se
    /* if(l > r) */
    /*     return; */
    // -> najs, ilrow się zgadzas
    int tm = (tl+tr)/2;
    /* int m = lower_bound(qus+l,qus+r+1,tm+1,[](auto &f, int v){return f[0] < v;}) - qus - 1; */
    /* int m = -1; */
    /* for(int i = l; i <= r; ++i){ */
    /*     if(qus[i][0] <= tm) */
    /*         m = i; */
    /*     int ll = qus[i][0] */
    /*     modify(1,0,n-1,); */
    /* } */
    vector<array<int,4>> qusl, qusr;
    vector<pi> rollback;
    FORR(i,qus){
        if(i[0] == tl && i[1] == tr){
            modify(1,0,n-1,i[2],i[3]);
            /* modify(1,0,524287,i[2],i[3]); */
            /* iter::modify(i[2],i[3]+1,-1); */
            rollback.pb({i[2],i[3]});
        }
        else{
            int lr = min(tm, i[1]);
            /* int ll = max(0, i[0]); */
            /* int ll = max(tl, i[0]); */
            int ll = i[0];
            if(ll <= lr){
                qusl.push_back({ll,lr,i[2],i[3]});
            }
            /* int rr = t[1]; */
            int rr = i[1];
            int rl = max(tm+1, i[0]);
            if(rl <= rr){
                qusr.push_back({rl,rr,i[2],i[3]});
            }
        }
    }
    /* whatis(qus) */
    /* whatis(qusl) */
    /* whatis(qusr) */
    if(tl == tr){
        ilrzrow[tl] += t[1];
        /* ilrzrow[tl] += iter::query(0,n); */
        // get val for interesting points
        FORR(i,int_points[tl]){
            st[mp(tl,i)] = query(1,0,n-1,i,i);
            /* st[mp(tl,i)] = query(1,0,524287,i,i); */
            /* st[mp(tl,i)] = iter::query(i,i+1); */
        }
    }
    else{
        /* rec(tl,tm,qusl); */
        /* rec(tm+1,tr,qusr); */
        rec(tl,tm,std::move(qusl));
        rec(tm+1,tr,std::move(qusr));
        /* rec(tl,tm,l,m); */
        /* rec(tm+1,tr,m+1,r); */
    }
    // rollback
    FORR(i,rollback){
        /* iter::modify(i.e1,i.e2+1,0); */
        modify(1,0,n-1,i.e1,i.e2);
        /* modify(1,0,524287,i.e1,i.e2); */
    }
}

void reccol(int tl, int tr, vector<array<int,4>> qus){
    if(tl > tr)
        return;
    // wait, jak jest empty, to wciąż muszę wszystkim rowom info wpisać
    /* if(qus.empty()) */
    /*     return; */
    // -> i guess mogę po prostu nie teturnować tak se
    /* if(l > r) */
    /*     return; */
    // -> najs, ilrow się zgadzas
    int tm = (tl+tr)/2;
    /* int m = lower_bound(qus+l,qus+r+1,tm+1,[](auto &f, int v){return f[0] < v;}) - qus - 1; */
    /* int m = -1; */
    /* for(int i = l; i <= r; ++i){ */
    /*     if(qus[i][0] <= tm) */
    /*         m = i; */
    /*     int ll = qus[i][0] */
    /*     modify(1,0,n-1,); */
    /* } */
    vector<array<int,4>> qusl, qusr;
    vector<pi> rollback;
    FORR(i,qus){
        if(i[2] == tl && i[3] == tr){
            modify(1,0,n-1,i[0],i[1]);
            /* modify(1,0,524287,i[0],i[1]); */
            /* iter::modify(i[2],i[3]+1,-1); */
            rollback.pb({i[0],i[1]});
        }
        else{
            int lr = min(tm, i[3]);
            /* int ll = max(0, i[0]); */
            /* int ll = max(tl, i[0]); */
            int ll = i[2];
            if(ll <= lr){
                qusl.push_back({i[0],i[1],ll,lr,});
            }
            /* int rr = t[1]; */
            int rr = i[3];
            int rl = max(tm+1, i[2]);
            if(rl <= rr){
                qusr.push_back({i[0],i[1],rl,rr});
            }
        }
    }
    /* whatis(qus) */
    /* whatis(qusl) */
    /* whatis(qusr) */
    if(tl == tr){
        /* ilrzrow[tl] += t[1]; */
        // 404:??
        /* whatis(t[1]) */
        ilrzcol[tl] += t[1];
        /* ilrzcol[tl] += iter::query(0,n); */
        // get val for interesting points
        // only on rec for rows
        /* FORR(i,int_points[tl]){ */
        /*     st[mp(tl,i)] = query(1,0,n-1,i,i); */
        /* } */
    }
    else{
        /* rec(tl,tm,qusl); */
        /* rec(tm+1,tr,qusr); */
        // XD, klasyk z niezmienianiem nazwy tego
        /* rec(tl,tm,std::move(qusl)); */
        /* rec(tm+1,tr,std::move(qusr)); */
        reccol(tl,tm,std::move(qusl));
        reccol(tm+1,tr,std::move(qusr));
        /* rec(tl,tm,l,m); */
        /* rec(tm+1,tr,m+1,r); */
    }
    // rollback
    FORR(i,rollback){
        /* iter::modify(i.e1,i.e2+1,0); */
        modify(1,0,n-1,i.e1,i.e2);
        /* modify(1,0,524287,i.e1,i.e2); */
    }
}

/* pi row1bnd[N]; // [,) */
/* pi col1bnd[N]; // [,) */
ll tmpcol1[N]; // sorted; not so tmp anymore
ll tmprow1[N];

void upd(int f, int s){
    /* bool was = a[f][s]; */
    /* a[f][s] ^= 1; */
    bool was = st[mp(f,s)] ^= 1;
    was ^= 1;
    if(was){
        // wait, lower/upper_bound po prostu
        // def not a bottleneck
        auto it = lower_bound(tmprow1,tmprow1+n,ilrzrow[f]);
        --*it;
        // as simple as that lol
        --ilrzrow[f];
        it = lower_bound(tmpcol1,tmpcol1+n,ilrzcol[s]);
        --*it;
        --ilrzcol[s];
        --ilrz;
        /* --ilrz; */
        /* --ilrzrow[f]; */
        /* --ilrzcol[s]; */
        /* if(ilrzrow[f] == 0){ */
        /*     ++il0row; */
        /* } */
        /* // nie else if, bo n = 1 */
        /* if(ilrzrow[f] == n-1){ */
        /*     --il1row; */
        /* } */
        /* if(ilrzcol[s] == 0){ */
        /*     ++il0col; */
        /* } */
        /* if(ilrzcol[s] == n-1){ */
        /*     --il1col; */
        /* } */
    }
    else{
        auto it = upper_bound(tmprow1,tmprow1+n,ilrzrow[f]) - 1;
        ++*it;
        ++ilrzrow[f];
        it = upper_bound(tmpcol1,tmpcol1+n,ilrzcol[s]) - 1;
        ++*it;
        ++ilrzcol[s];
        ++ilrz;
        /* ++ilrz; */
        /* ++ilrzrow[f]; */
        /* ++ilrzcol[s]; */
        /* if(ilrzrow[f] == 1){ */
        /*     --il0row; */
        /* } */
        /* // nie else if, bo n = 1 */
        /* if(ilrzrow[f] == n){ */
        /*     ++il1row; */
        /* } */
        /* if(ilrzcol[s] == 1){ */
        /*     --il0col; */
        /* } */
        /* if(ilrzcol[s] == n){ */
        /*     ++il1col; */
        /* } */
    }
}


ll greedy(){
    // 2 strong of a lemat below
    /* return max((int64_t)0, min(ilrz  - (il1col * il1row), n*n - ilrz - (il0col * il0row))); */
    /* return max((int64_t)0, min(ilrz - sumodbcolltil1row - sumodbrowltil1col + (il1col * il1row), n*n - ilrz -sumrzcolltil0row - sumrzrowltil0col + (il0col * il0row))); */
    /* ll tmpcol1[n]; */
    /* memcpy(tmpcol1,ilrzcol,n<<3); */
    /* sort(tmpcol1, tmpcol1+n); */
    /* ll tmprow1[n]; */
    /* FOR(i,0,n){ */
    /*     tmprow1[i] = ilrzrow[i]; */
    /*     /1* tmprow0[i] = n - ilrzrow[i]; *1/ */
    /* } */
    /* sort(tmprow1, tmprow1+n); */
    /* memcpy(tmprow0,ilodbrow,n<<3); */
    ll res = 0;
    /* ll cr = ilrz; */
    ll cr = 0;
    // log od q jest spox
    // log^2 though:?
    /* int low = 0, high = n-1; */
    /* while(low < high){ */
    /*     int mid = (low + high) >> 1; */
    /* } */
    ll s = 0;
    ll s1 = 0;
    int it = 0;
    // szukanie minimum w drzewie przedziałowym??
    // -> min queries *lazy* (but fine, bo tylko log jeden)
    // -> each index += row1[ind], gdzie to jest non-desc
    // -> each index -= min(0,col1[ind]-(ind+1)), gdzie col1 jest non-desc
    // on update -> po inc row1, po prostu findujesz rightmost pozycje w
    // segtree z tą wartością, i ją inkrementujesz; wsm to lookup table
    // [begintabl,endintab(exclusive)) moze w tym pomoc, wtedy w O(1) znajduje
    // ta pozycje ktora chce, i tez updatuje all w O(1)
    // (np. ind -> --end of boundary of prev val; --beg of bounday of next val
    // analogicznie dec row1
    // z col1 dokładnie to samo, po prostu inaczej updatuję to segtree
    // increment modifications segtree best i guess
    // -1,-2,-3...,-n moge na poczatku zrobic
    // wait, nie -1,-2,-3,...,-n def
    // ale może prefowe to, czyli -1,-3,-6,-10,...,-n*(n-1)/2?
    // lets try def
    // albo wait, taka suma, aby sie sumowalo do -(i+1)^2?
    // -> -1,-3,-5,-7,-9,...?
    // -> nice, passes stuff
    // small194.in bad:c
    //
    //
    // ale wait, ja chce jakby mix sume na prefixie wtedy, a nie min elem:??
    // -> segtree nic mi wsm nie daje lol
    // chyba ze trzymam tam te all rzeczy jako swe sumy prefiskowe faktycznie,
    // no i wtedy lazy update na jakims sufiksie itd; wtedy to moze miec sens
    FOR(i,0,n){
        /* cr += tmprow1[i]; */
        s1 += tmprow1[i];
        // eq suma tmpcol1[x] - ind * n?
        // i dont think so
        // suma tylko tych < / <= ind
        /* FOR(x,0,n){ */
        /*     s += tmpcol1[x]; */
        /*     /1* tmpcol1[x] -= n; *1/ */
        /*     /1* cr += tmpcol1[x]; *1/ */
        /*     /1* if(--tmpcol1[x] < 0) *1/ */
        /*     /1*     --cr; *1/ */
        /* } */
        /* cr -= (i+1)*n; */
        /* res = cr; */
        // -> moge dalsze te brać bez zwiększania o tmprow1[i] (jak zostawie
        // indeks)
        // -> 2d segtree queries?:c
        //
        // ew po prostu w segtree te drugie rzeczy nie rob w indeksach od
        // 0..n-1 tak po prostu, lecz wybieraj najlepszy poz (czyli po prostu
        // rowny tmpcol1[it], czyli przy zmianach aktualizuj nie tylko val,
        // lecz tez pozycje, i tam += to)
        // -> dla col1[] nie musze nawet trzymac tej tablicy boundowej, tylko
        // po prostu na podstawie wartosci (cnta), odpowiednio zmieniac indeks
        // -> wsm łatwiej jest lol
        // -> +{row1[0],row1[0]+row1[1]}
        // -> +{
        while(it < n && tmpcol1[it] <= i){
            s += tmpcol1[it];
            ++it;
        }
        /* cr -= s - it * (i+1); */
        /* cr += s - it * (i+1); */
        cr = s1 + s - it * (i+1);
        res = min(res,cr);
        /* whatis(cr) */
        /* whatis(res) */
    }
    /* ll s3 = 0; */
    /* FOR(i,0,n){ */
    /*     s1 += tmprow1[i]; */
    /*     s += tmpcol1[i]; */
    /*     /1* s3 -= i+1; *1/ */
    /*     s3 -= i*2+1; */
    /*     cr = s1 + s + s3; */
    /*     whatis(cr) */
    /*     res = min(res,cr); */
    /* } */
    /* whatis(res) */
    /* whatis(n*n - ilrz + res) */
    /* whatis(ilrz) */
    /* return max((int64_t)0, min(ilrz  - (il1col * il1row), n*n - ilrz - (il0col * il0row))); */
    return n*n-ilrz+res;
    /* return res; */
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m,k;
    sc(n,m,k);
    /* iter::n = 16; */
    /* iter::h = sizeof(int) * 8 - __builtin_clz(16); */
    vector<array<int,4>> qus(m);
    FOR(i,0,m){
        int x1,y1,x2,y2;
        sc(x1,y1,x2,y2);
        // forgot to reindeify
        --x1,--y1,--x2,--y2;
        assert(x1 < n);
        assert(y1 < n);
        assert(x2 < n);
        assert(y1 < n);
        /* if(x1 > x2) */
        /*     swap(x1,x2); */
        // for Maziarz's old big tests to maybe pass
        // those changes -> literally no big test passed, a b4 chyba tylko 1
        // nie przechodził ultimately
        /* if(y1 > y2) */
        /*     swap(y1,y2); */
        // wait, tera inny ordering tutaj wszędzie wykorzystywałem
        /* qus[i] = {x1,y1,x2,y2}; */
        qus[i] = {x1,x2,y1,y2};
        /* a[x1][y1] ^= 1; */
        /* a[x2+1][y1] ^= 1; */
        /* a[x1][y2+1] ^= 1; */
        /* a[x2+1][y2+1] ^= 1; */
    }
    // so valgrind doesnt say that
    /* pi quph2[k]; */
    vector<pi> quph2(k);
    FOR(q,0,k){
        int f,s;
        sc(f,s);
        --f,--s;
        quph2[q] = {f,s};
        int_points[f].pb(s);
    }
    /* sort(qus,qus+m,[](auto &f, auto &s){return f[0] < s[0];}); */
    sort(all(qus),[](auto &f, auto &s){return f[0] < s[0];});
    /* rec(0,n-1,0,m-1); */
    /* rec(0,n-1,qus); */
    /* rec(0,n-1,std::move(qus)); */
    rec(0,n-1,qus);
    // ???? XDDDD
    // najs sort
    // ciekawe jak tyle testów przeszło though
    // wait, bo wsm ja nie korzystam nigdzie z faktu posortowania w reku; ma
    // sens. ciekawe czy to właśnie to na ten duzy czas na niektorych testach
    // (i wa) wpływało
    /* sort(all(qus),[](auto &f, auto &s){return f[2] < s[3];}); */
    sort(all(qus),[](auto &f, auto &s){return f[2] < s[2];});
    reccol(0,n-1,qus);
    FOR(i,0,n){
        /* FOR(x,0,n){ */
        /*     ilrzrow[i] += a[i][x]; */
        /* } */
        /* whatis(ilrzrow[i]) */
        ilrz += ilrzrow[i];
        /* if(ilrzrow[i] == 0) */
        /*     ++il0row; */
        /* else if(ilrzrow[i] == n) */
        /*     ++il1row; */
        /* ++ilxrzrow[ilrzrow[i]]; */
        /* ++ilxodbrow[n-ilrzrow[i]]; */
    }
    /* /1* FOR(x,0,n){ *1/ */
    /* /1*     /2* FOR(i,0,n){ *2/ *1/ */
    /* /1*     /2*     ilrzcol[x] += a[i][x]; *2/ *1/ */
    /* /1*     /2* } *2/ *1/ */
    /* /1*     // 2 razy zliczałem; starczy dla rowów *1/ */
    /* /1*     /2* ilrz += ilrzcol[x]; *2/ *1/ */
    /* /1*     /2* whatis(ilrzcol[x]) *2/ *1/ */
    /* /1*     if(ilrzcol[x] == 0) *1/ */
    /* /1*         ++il0col; *1/ */
    /* /1*     else if(ilrzcol[x] == n) *1/ */
    /* /1*         ++il1col; *1/ */
    /* /1*     ++ilxrzcol[ilrzcol[x]]; *1/ */
    /* /1*     ++ilxodbcol[n-ilrzcol[x]]; *1/ */
    /* /1* } *1/ */
    /* // nie zwykle zliczenie, tylko suma impaktow */
    /* // -> wsm tez potrzebuje ilosc, aby aktualizowac sumy odpowiednio */
    /* /1* FOR(i,0,il0col){ *1/ */
    /* /1*     crrzrowltil0col += ilxrzrow[i]; *1/ */
    /* /1*     sumrzrowltil0col += crrzrowltil0col; *1/ */
    /* /1* } *1/ */
    /* /1* FOR(i,0,il0row){ *1/ */
    /* /1*     crrzcolltil0row += ilxrzcol[i]; *1/ */
    /* /1*     sumrzcolltil0row += crrzcolltil0row; *1/ */
    /* /1* } *1/ */
    /* /1* FOR(i,0,il1col){ *1/ */
    /* /1*     crodbrowltil1col += ilxodbrow[i]; *1/ */
    /* /1*     sumodbrowltil1col += crodbrowltil1col; *1/ */
    /* /1* } *1/ */
    /* /1* FOR(i,0,il1row){ *1/ */
    /* /1*     crodbcolltil1row += ilxodbcol[i]; *1/ */
    /* /1*     sumodbcolltil1row += crodbcolltil1row; *1/ */
    /* /1* } *1/ */
    // newpre
    memcpy(tmpcol1,ilrzcol,n<<3);
    sort(tmpcol1, tmpcol1+n);
    memcpy(tmprow1,ilrzrow,n<<3);
    sort(tmprow1, tmprow1+n);
    /* FOR(i,0,n){ */
    /*     /1* whatis(tmpcol1[i]) *1/ */
    /*     whatis(tmprow1[i]) */
    /* } */
    /* int init[n]; */
    /* FOR(i,0,n){ */
    /*     /1* init[i] = -(i+1) + tmprow1[i] + tmpcol1[i]; *1/ */
    /*     /1* init[i] = -(i*2+1) + tmprow1[i] + tmpcol1[i]; *1/ */
    /*     init[i] = -(i*2+1) + tmprow1[i]; */
    /* } */
    /* FOR(i,0,n){ */
    /*     tmpcol1[i]; */
    /* } */
    /* int it = 0; */
    /* FORE(i,0,n){ */
    /*     while(it < jj */
    /* } */
    /* lazy2::build(1,0,n-1,init); */
    /* whatis(ilrz) */
    /* whatis(n*n-ilrz) */
    /* whatis(il0col) */
    /* whatis(il0row) */
    /* whatis(il1col) */
    /* whatis(il1row) */
    cout << greedy() << '\n';
    /* exit(0); */
    int f,s;
    FOR(q,0,k){
        /* sc(f,s); */
        /* --f,--s; */
        f = quph2[q].e1;
        s = quph2[q].e2;
        /* a[f][s] ^= 1; */
        upd(f,s);
        cout << greedy() << '\n';
    }
}