### 问题描述 农夫小齐新建了一个巨大的圆形牛棚，共有 $N$ 个牛栏 $(2 \leq N \leq 3,000,000)$，编号为 $0 \ldots N-1$，其中牛栏 $N-1$ 与牛栏 $0$ 相邻。 每天结束时，小齐的奶牛们一个接着一个地回到牛棚，每头奶牛都有一个她们喜欢的牛栏。然而，如果一头奶牛喜欢的牛栏已经被其他奶牛占据，她会顺序扫描从该牛栏开始的所有牛栏，直到找到第一个空闲的牛栏，并占领它。如果扫描越过了牛栏 $N-1$，她将从牛栏 $0$ 继续扫描。 给定每头奶牛的喜欢的牛栏，请确定所有奶牛回到牛棚后保持空闲的最小牛栏编号。注意，问题的答案不依赖于奶牛返回牛棚的顺序。 为避免读取大量输入的问题，此问题的输入采用紧凑的格式，使用 $K$ 行，每行的格式如下： $X$ $Y$ $A$ $B$ 其中每行表示 $XY$ 头奶牛，其中 $X$ 头奶牛喜欢牛栏 $f(1) \ldots f(Y)$，其中 $f(i) = (Ai + B) \mod N$。其中 $A$ 和 $B$ 的值在 $0 \ldots 1,000,000,000$ 的范围内。 请不要忘记所有问题的标准内存限制为 $64MB$。 ### 输入格式 第 $1$ 行：两个用空格分隔的整数 $N$ 和 $K$。 第 $2 \ldots 1+K$ 行：每行包含四个整数 $X\ Y\ A\ B$，如上所述。这些行中指定的所有奶牛的总数将不超过 $N-1$。这些行中可能会指定多个奶牛占领相同的牛栏。 ### 输出格式 所有未被占据的牛栏的最小编号。 ### 样例输入 ``` 10 3 3 2 2 4 2 1 0 1 1 1 1 7 ``` ### 样例输出 ``` 17 ``` ### 评测数据规模 $2 \leq N \leq 3,000,000$，$1 \leq K \leq 10,000$，$0 \leq X, Y, A, B \leq 1,000,000,000$。