Empty Stalls

Farmer John's new barn is a ring of $N$ stalls ($2 \le N \le 3 \times 10^6$) numbered $0$ through $N-1$, and stall $N-1$ sits next to stall $0$.

At the end of each day the cows come back to the barn one at a time, and every cow has one stall she wants. If that stall is already taken, she looks at the stalls in increasing order of number, starting from the one she wants, and claims the first empty stall she meets. Once she passes stall $N-1$ she keeps looking from stall $0$.

Given the preferred stall of every cow, find the smallest number among the stalls that are still empty after all the cows are back. The answer does not depend on the order in which the cows return.

To keep the input from growing too large, the preferred stalls are given in compressed form on $K$ lines ($1 \le K \le 10^4$). Each line has the form X Y A B.

One such line describes the stalls wanted by $X \times Y$ cows. With $f(i) = (A \times i + B) \bmod N$, there are $X$ cows that want each of the stalls $f(1), f(2), \dots, f(Y)$. Both $A$ and $B$ are between $0$ and $10^9$.

• Line 1: two space-separated integers $N$ and $K$.
• Lines 2 through $1+K$: each line contains the integers $X$, $Y$, $A$, $B$ described above. Together these lines describe at most $N-1$ cows. Several lines may add cows to the same stall.

• Line 1: print the smallest number of a stall that stays empty.

The barn in the sample has 10 stalls numbered $0$ through $9$. The line 3 2 2 4 means 3 cows want stall $(2 \times 1 + 4) \bmod 10 = 6$ and 3 cows want stall $(2 \times 2 + 4) \bmod 10 = 8$. The line 2 1 0 1 means 2 cows want stall $(0 \times 1 + 1) \bmod 10 = 1$, and the line 1 1 1 7 means 1 cow wants stall $(1 \times 1 + 7) \bmod 10 = 8$, so 4 cows want stall 8 in total. All 9 cows fit, and stall 5 is the only one left empty.