题目描述

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

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

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

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

$X\ Y\ A\ B$

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

$A$ 和 $B$ 的取值范围为 $0\dots 10^{9}$。

注意，只有 64M 的空间。

输入格式

第一行，两个用空格隔开的整数,$N$ 和 $K$。

第二行到第 $K+1$ 行，每行包含四个整数 $X,Y,A,B$，解释看题目描述。牛的总数最多为 $N-1$ ，可以向同一个牛栏中添加牛。

输出格式

一行一个整数，表示最小的移动次数。

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

5 

提示

谷仓里有 $10$ 个牛栏，编号为 $0$ 到 $9$。输入的第二行表示有 $3$ 头牛喜欢牛栏 $(2 \times 1 + 4) \bmod 10 = 6$，另有 $3$ 头牛喜欢牛栏 $(2 \times 2 + 4) \bmod 10 = 8$。第三行表示有 $2$ 头牛喜欢牛栏 $(0\times 1 + 1) \bmod 10 = 1$。第四行表示有 $1$ 头牛喜欢牛栏 $(1 \times 1 + 7) \bmod 10 = 8$（所以总共有 $4$ 头牛喜欢这个牛栏）。

除了牛栏 $5$ 之外，其他所有牛栏最后都会被占用。