#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100000;
ll c,T,t,maxnum=-1,minnum=1e9+7,tot=0;
ll num[N];
ll la[200010];
ll ra[200010];
ll lb[200010];
ll rb[200010];
int main(){
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	cin>>c>>T;
	for(int tt=1;tt<=T;tt++){
		memset(num,0,sizeof(num));
		for(int i=1;i<=200010;i++){
			la[i]=0;
			lb[i]=0;
			ra[i]=0;
			rb[i]=0;
		}
		tot=0,maxnum=-1,minnum=1e9+7;
		int nowr=0,nowl=0;
		cin>>t;
		for(int i=1;i<=t;i++){
			cin>>la[i]>>ra[i]>>lb[i]>>rb[i];
			if(rb[i]>maxnum){
				maxnum=rb[i];
			}
			if(lb[i]<minnum){
				minnum=lb[i];
			}
		}
		for(int i=1;i<=t;i++){
			if(rb[i]>=minnum&&minnum>=lb[i]){
				num[minnum]+=ra[i];
				tot+=ra[i];
			}
			else if(lb[i]>minnum){
				num[lb[i]]+=la[i];
				tot+=la[i];
			}
			
		}
		int mid=(tot+1)/2;
		while(mid>0){
			nowl++;
			mid-=num[nowl];	
		}
		tot=0;
		memset(num,0,sizeof(num));
		for(int i=1;i<=t;i++){
			if(rb[i]>=maxnum&&maxnum>=lb[i]){
				num[maxnum]+=ra[i];
				tot+=ra[i];
			}
			else if(rb[i]<maxnum){
				num[rb[i]]+=la[i];
				tot+=la[i];
			}
		}
		mid=(tot+1)/2;
		while(mid>0){
			mid-=num[++nowr];
		}
		cout<<nowr-nowl+1<<endl;
	}
	
}