#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)#define Max(a,b) ((a) > (b) ? (a) : (b))#define Min(a,b) ((a) < (b) ? (a) : (b))#define Fill(a,b) memset(a, b, sizeof(a))#define Swap(a,b) a^=b^=a^=b#define ll long long#define ON_DEBUG#ifdef ON_DEBUG#define D_e_Line printf("\n\n----------\n\n")#define D_e(x)  cout << #x << " = " << x << endl#define Pause() system("pause")#else#define D_e_Line ;#endifstruct ios{    template
         
          ios& operator >> (ATP &x){ x = 0; int f = 1; char c; for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar(); x*= f; return *this; }}io;using namespace std;int f[3000007];int main(){ int n, m; io >> n >> m; R(i,1,m){ int x, y, a, b; io >> x >> y >> a >> b; R(j,1,y) f[1ll * (1ll * a * j + b) % n] += x; } int flag = false; while(!flag || f[0] > 1){ R(i,0,n - 1){ if(f[i] > 1){ f[(i + 1) % n] += f[i] - 1; f[i] = 1; } } flag = true; } R(i,0,n){ if(f[i] == 0){ printf("%d", i); return 0; } } return 0;}