题目描述

约翰的谷仓中有 $N$ 个房间，编号 $0\sim N-1$，这些房间排布成环状,编号 $0$ 的和编号 $N-1$ 的相邻。

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

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

为避免输入内容过多。本题的输入数据采用一种简洁的方式：一共 $K$ 行，每行格式如下：

$X\ Y\ A\ B$

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

注意，只有 $64\text{MB}$ 的空间。

输入格式

第一行两个整数 $N,K$。

第 $2\sim 1+K$ 行，每行包含四个整数 $X,Y,A,B$。

输出格式

一行一个整数，表示答案。

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

5 

样例说明 1

谷仓里有 $10$ 个房间，编号为 $0\sim 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$。

数据规模与约定

对于 $100\%$ 的数据，$2\leq N\leq 3\times 10^6$，$1\leq K\leq 10^4$，$0\leq A,B\leq 10^9$。

题目来源

Gold