Circular Barn Allocation

Farmer John's barn consists of N stalls arranged in a circle (numbered 0 to N-1 with stall N-1 adjacent to stall 0). At the end of the day, each cow returns to the barn with a preferred stall. If her preferred stall is already occupied, she moves forward (wrapping around from stall N-1 back to 0) until she finds the first unoccupied stall and claims it. It can be shown that the final allocation (which stall each cow ends up with) is independent of the order in which the cows arrive.

The input is given in a concise format. After specifying two numbers N and K on the first line, there follow K lines. Each line contains four integers: X, Y, A and B. This line means that there are Y batches, each batch containing X cows. In batch i (1 ≤ i ≤ Y) the preferred stall number is computed by the formula \[ f(i) = (A\cdot i+B) \mod N. \] Thus, a total of X·Y cows are described. It is guaranteed that the total number of cows is less than N so that at least one stall remains unoccupied. Your task is to determine the smallest index of a stall that remains unoccupied after all the cows have been assigned according to the rule described.

Note: Only 64 MB of memory is allowed.

inputFormat

The first line contains two integers: N and K, where 2 ≤ N ≤ 3,000,000 and 1 ≤ K ≤ 10,000. Then K lines follow. Each of these K lines contains four integers: X, Y, A, and B, where 0 ≤ A, B ≤ 1,000,000,000. Each such line indicates that there are Y batches of cows; in the i^th batch, X cows have a preferred stall given by
f(i) = (A*i + B) mod N (with i ranging from 1 to Y).

You may assume that the total number of cows is strictly less than N.

outputFormat

Output a single integer: the smallest stall index (between 0 and N-1) that remains unoccupied after all cows have been assigned according to the rules.

sample

5 2
1 2 0 0
1 2 0 2

1