Daunting device

At an excavation site on the Caribbean island of Saint Basil you found an old device together with a set of instructions that reads like a puzzle. Your local guide Vibenas says that solving the puzzle makes the device point to the place where the pirate Lyerpes hid a treasure.

The device holds a tape of $L$ cells indexed from $0$ to $L-1$. Each cell carries one color, and a command sent to the device changes that color. Colors are written as integers, and every cell starts with the same color.

The instructions list $N$ steps to perform before the device shows the way. Each step is given by four integers $P$, $X$, $A$ and $B$. To perform a step, first count the cells whose current color is $P$. Call that count $S$, then compute the two values

$M_1 = (A + S^2) \bmod L$

$M_2 = (A + (S + B)^2) \bmod L$

Finally, change every cell in the closed interval $[\min(M_1, M_2), \max(M_1, M_2)]$ to color $X$.

After all $N$ steps, pick a color that appears the greatest number of times on the tape and report how many cells carry it. That number is the same even when several colors tie for the greatest count.

The first line contains three integers $L$, $C$ and $N$ ($1 \le L, C, N \le 10^5$), which are the number of cells on the tape, the number of available colors, and the number of steps. Colors are the distinct integers from $1$ to $C$, and every cell starts with color $1$.

Each of the next $N$ lines describes one step with four integers $P$, $X$, $A$ and $B$ ($1 \le P, X \le C$, $0 \le A, B \le 10^8$). $P$ is the color whose cell count decides the range of the step, $X$ is the color the cells in the range must have after the step is performed, and $A$ and $B$ are used to compute the bounds of the range as described above. The steps are performed in the given order.

Print one line with the number of cells that have a color appearing the greatest number of times on the tape after all steps have been performed.