Q2

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <cassert>
#include <cstring>

using namespace std;

#define INF 2000000000

struct inter {
    int loc;
    int delta;

    bool operator< (inter ot) const {
        return loc<ot.loc;
    }
};

inline int read_int() {
    char c;
    while ((c=getchar()) < 48 || c > 57);
    int p = c-48;
    while ((c=getchar()) >= 48 && c <= 57) p=p*10+c-48;
    return p;
}

int T, N, M,P;
inter in[20010];
int small;
int big;

int main() {
    for (T=read_int(); T; T--) {
        P=read_int();N=read_int(); M=read_int();
        small = INF;
        big = -INF;

        in[2*M].loc = N+1;
        in[2*M].delta = 0;
        for (int i = 0; i < M; i++) {
            int w,a,b,c;
            w=read_int();
            a=read_int();
            b=read_int();
            c=read_int();
            if (w==2) c = -c;

            in[2*i].delta = c;
            in[2*i+1].delta = -c;

            in[2*i].loc = a;
            in[2*i+1].loc = b+1;
        }

        sort(in, in+(2*M));

        int k = 0;
        int cur = 1;
        for (int i = 0; i <= 2*M; i++) {
            if (in[i].loc > cur) {
                big = max(big, in[i].loc-1+k);
                small = min(small, cur+k);
            }
            k += in[i].delta;
            cur = in[i].loc;
        }
        printf("%d\n",(!P)? small:big);
//        getchar();
    }
}