Chuồng Trống

Nông dân John vận hành một chuồng bò hình tròn với $N$ ô chuồng được đánh số từ $0$ đến $N-1$, trong đó ô $N-1$ nằm kề ô $0$. Mỗi ngày, khi những con bò trở về chuồng, mỗi con đều có một ô chuồng yêu thích. Nếu ô chuồng yêu thích đã bị chiếm, con bò sẽ di chuyển theo chiều tăng dần của số hiệu ô (quay vòng từ ô $N-1$ về ô $0$) cho đến khi tìm được ô trống.

Dãy ô chuồng yêu thích của các con bò được mô tả qua $K$ nhóm. Mỗi nhóm gồm bốn số $X$, $Y$, $A$, $B$ mô tả $X·Y$ con bò: có $X$ con bò yêu thích mỗi ô trong dãy $f(1),f(2),\dots ,f(Y)$, trong đó $f(i)=(A·i+B)modN$.

Các con bò lần lượt tìm chuồng theo thứ tự: nhóm 1 trước, rồi nhóm 2, v.v. Trong mỗi nhóm, bò yêu thích $f(1)$ vào trước (tất cả $X$ con), rồi đến bò yêu thích $f(2)$, v.v.

Tổng số bò luôn nhỏ hơn $N$, nên sau khi tất cả bò đã vào chuồng, sẽ luôn còn ít nhất một ô trống. Hãy tìm chỉ số nhỏ nhất của ô chuồng còn trống sau khi tất cả bò đã vào chuồng.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $K$.
• $K$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $X$, $Y$, $A$, $B$.

Dữ liệu ra

• Một số nguyên duy nhất: chỉ số nhỏ nhất của ô chuồng còn trống.

Ràng buộc

• $2\le N\le 3000000$
• $1\le K$
• $0\le A,B\le {10}^9$
• Tổng số bò (tổng các $X·Y$) $\le N-1$

Ví dụ