题目描述

农民约翰的新谷仓由$\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{X y a b}$

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

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

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

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

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

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

$\red{X Y A B}$

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

5