题目描述

$\red{Farmer John }$的新谷仓由 $\red{N }$个畜栏组成$\red{（2 <= N <= 3,000,000）}$，编号为 $\red{0..N-1，}$其中 $\red{N-1 }$畜栏与 $\red{0 }$畜栏相邻。每天结束时，$\red{FJ }$的奶牛一个个回到谷仓，每个人都有一个他们想占据的首选摊位。

然而，如果一头奶牛的首选隔间已被另一头奶牛占据，她会从该隔间按顺序向前扫描，直到找到第一个空置的隔间，然后她声称该隔间。如果她扫描过$\red{N-1 }$隔间，她将继续从 $\red{0 }$号隔间开始扫描。

给定每头奶牛的首选隔间，请确定在所有奶牛都返回谷仓后仍然无人占用的隔间的最小索引。请注意，这个问题的答案并不取决于奶牛返回谷仓的顺序。

为了避免读取大量输入时出现问题，此问题的输入以简洁的格式指定，使用$\red{K }$行 $\red{(1 <= K <= 10,000)，}$每个格式如下： $\red{XYAB }$其中一行指定了$\red{XY }$奶牛总数：$\red{X }$头奶牛更喜欢每个畜栏 $\red{f(1) .. f(Y)，}$其中 $\red{f(i) = (Ai + B) mod N}$。$\red{A }$和 $\red{B }$的值在 $\red{0... }$范围内$\red{1,000,000,000}$。不要忘记所有问题的标准内存限制为 $\red{64MB}$。

没有绕成一个个圈成为$\red{（0...n-1）}$，有很多头牛，每头牛喜欢一个并且有一个会场编号位置，如果这个有牛的位置后面找到第一个位置一个牛的位置占领；由于数据过大，采用了更多的方法读入，读入$\red{x，}$$\red{y，}$$\red{a，}$$\red{b}$表示有$\red{x}$个牛喜欢$\red{f(1)..f(y),f(i ) = (a\times i+b)\%n}$;

输入格式

第$\red{1 }$行：两个空格分隔的整数：$\red{N }$和 $\red{K}$。

第$\red{2..1+K }$行：每行包含整数 $\red{XYAB，}$解释如上。

所有这些行指定的奶牛总数最多为 $\red{N-1}$。可以通过其中几条线将奶牛添加到同一个畜栏。

输出格式

第$\red{1 }$行：空置摊位的最小索引。

样例

输入样例

10 3
3 2 2 4
2 1 0 1
1 1 1 7

输出样例

5

提示

输入细节：

谷仓有 $\red{10 }$个摊位，编号 $\red{0..9}$。

第二行输入表明 $\red{3 }$头奶牛更喜欢失速 $\red{(2\times 1+4) mod 10 = 6，}$$\red{3 }$头奶牛更喜欢失速 $\red{(2\times 2+4) mod 10 = 8}$。

第三行表明 $\red{2 }$头奶牛更喜欢失速 $\red{( 0\times 1+1) mod 10 = 1}$。

第四行指定 $\red{1 }$头奶牛喜欢摊位 $\red{(1\times 1+7) mod 10 = 8}$（所以总共有 $\red{4 }$头奶牛喜欢这个摊位）。

输出详情：

除 $\red{5 }$号摊位外，所有摊位都将被占用。