Chuồng mới của Farmer John gồm một vòng tròn khổng lồ có \(N\) ô chuồng (\(2 \le N \le 3\,000\,000\)), được đánh số từ \(0..N-1\), trong đó ô \(N-1\) nằm kề ô \(0\).

Cuối mỗi ngày, những con bò của FJ lần lượt trở về chuồng, mỗi con có một ô chuồng ưa thích mà nó muốn chiếm. Tuy nhiên, nếu ô chuồng ưa thích của một con bò đã bị con khác chiếm, nó sẽ lần lượt dò về phía trước từ ô này cho đến khi tìm thấy ô trống đầu tiên rồi chiếm ô đó. Nếu dò qua ô \(N-1\), nó tiếp tục dò từ ô \(0\).

Cho ô chuồng ưa thích của mỗi con bò, hãy xác định chỉ số nhỏ nhất của một ô chuồng vẫn còn trống sau khi tất cả bò đã trở về. Lưu ý rằng đáp án không phụ thuộc vào thứ tự những con bò trở về chuồng.

Để tránh phải đọc một lượng dữ liệu vào khổng lồ, dữ liệu vào của bài toán được mô tả dưới dạng rút gọn bằng \(K\) dòng (\(1 \le K \le 10\,000\)), mỗi dòng có dạng:

X Y A B

Một dòng như vậy mô tả ô chuồng ưa thích của tổng cộng \(XY\) con bò: có \(X\) con bò thích mỗi ô trong các ô \(f(1)..f(Y)\), với \(f(i) = (Ai + B) \bmod N\). Các giá trị \(A\) và \(B\) nằm trong khoảng \(0..1\,000\,000\,000\).

Đừng quên giới hạn bộ nhớ tiêu chuẩn 64 MB áp dụng cho tất cả các bài toán.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên cách nhau bởi dấu cách: \(N\) và \(K\).
• Các dòng \(2..1+K\): mỗi dòng chứa các số nguyên \(X\), \(Y\), \(A\), \(B\), được hiểu như trên. Tổng số bò được mô tả bởi tất cả các dòng này không vượt quá \(N-1\). Nhiều dòng có thể thêm bò vào cùng một ô chuồng.

Dữ liệu ra

• Dòng 1 chứa chỉ số nhỏ nhất của một ô chuồng còn trống.

Ví dụ

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

5

Nguồn

USACO 2013 November Contest, Gold — Problem 1: Empty Stalls

Tác giả đề: Brian Dean, 2013.