题目描述

农民约翰的新谷仓由${N}$个巨大的圈组成${(2 <= N <= 3,000,000)，}$编号为${0..N-1，}$失速点${N-1}$与失速点${0}$相邻

在每天结束的时候，${FJ}$的奶牛一个接一个地回到谷仓，每个奶牛都有一个它们想要占据的首选马厩。

然而，如果一头奶牛喜欢的牛栏已经被另一头奶牛占用了，她就会从这个牛栏连续向前扫描，直到她找到第一个空闲的牛栏，然后她就会申请。如果她扫描过了失速${N-1，}$她会从失速${0}$继续扫描。

给定每头奶牛的首选牛栏，请确定在所有奶牛返回牲棚后仍未占用的牛栏的最小指数。请注意，这个问题的答案与奶牛返回谷仓的顺序无关。

为了避免读取大量输入的问题，这个问题的输入以简洁的格式指定，使用${K}$行${(1 <= K <= 10,000)}$每个形式:

${X y a b}$

其中一条线指定${XY}$头奶牛的首选牛栏:${X}$头奶牛偏好${f(1)}$的每个牛栏。${f(Y)，}$其中${f(i) = (Ai + B) ~mod~ n}$。${A}$和${B}$的取值范围为${0 \sim}$ ${1000,000,000}$。

不要忘记所有问题的标准内存限制是${64MB}$。

约翰的谷仓中有${N(2 <= N <=3,000,000)}$个房间，编号${0}$到${N-1，}$这些房间排布成环状,编号${0}$的和编号${N-1}$的相邻。

每天傍晚，奶牛们一只一只排队回到谷仓，每头奶牛都有一个喜欢的房间，但是，如果它喜欢的房间已被其他奶牛占了，它会向前挨个探索其他房间（如果它探索过了${N-1}$号房间，它会继续探索${0}$号房间，以此继续下去）直到探到第一个没有被占用的房间，这时它会宣布占用这个房间。

告诉你每头奶牛喜欢的房间，当所有奶牛都找到房间后，剩下的没被占用的房间中，编号最小的是哪个。很明显，问题的答案与奶牛进入谷仓的顺序无关。

为避免输入内容过多。本题的输入数据采用一种简洁的方式：一共${K(1 <= K <=10,000)}$行，每行格式如下：

${X Y A B}$

表示有${Y}$批奶牛，每批${X}$头，也就是总共${X*Y}$只奶牛喜欢的房间号。${Y}$批奶牛编号${1}$到${Y，}$第${i}$批${X}$头奶牛喜欢的房间号为${(A\times i+B)~ Mod~ N.}$

${A}$和${B}$的取值范围为${0...1,000,000,000}$

注意，只有${64M}$的空间。

输入格式

第一行:两个用空格分隔的整数:${N}$和${K}$。

第${2 . .1+K:}$每一行包含整数${X Y~ A B，}$解释如上。所有这些品系指定的奶牛总数最多为${N-1}$头。奶牛可以通过几条线添加到同一个畜栏中。

输出格式

第一行:空置摊位的最低指数。

样例

输入样例

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

输出样例

5