Video Reviews - 2

Easy problem, just binary search the answer. Oh wait...

You

The studio "Lodka Gaming" is engaged in advertising of their new game ".C.O.N.T.E.S.T: Unexpected Behaviour". The studio's marketer is planning to communicate with $n$ videobloggers one by one (in the predetermined order, starting from the 1-st and ending with the $n$-th), offering them to record a video review on the game. All people are different and videobloggers are as well, therefore the $i$-th videoblogger will record a review in two cases: either he is interested in this game, or there are already at least $a\_i$ video reviews on this game.

The studio wants to have at least $m$ video reviews in the Internet. The game designer of "Lodka Gaming" understands these video reviews possibly would not appear by themselves, so he wants to convince some video bloggers that they are actually interested in this game. Which minimal number of videobloggers are needed to be convinced?

The first line contains two integers $n$ and $m$ ($1 \le n \le 5 \cdot 10^7, 1 \le m \le n$) --- the number of videobloggers and the required number of video reviews.

As $n$ can be too large, the $a\_i$ values will be generated by linear congruential random number generators.

The second line contains two integers $a\_1$ and $k$ ($0 \le a\_i \le 5 \cdot 10^7, 0 \le k \le 10^5$).

Each of the following $k$ lines contains 4 integers $c\_j$, $x\_j$, $y\_j$ and $z\_j$ ($1 \le c\_j < 5 \cdot 10^7, 1 \le z\_j \le 5 \cdot 10^7, 1 \le x\_j < z\_j, 0 \le y\_j < z\_j$). $z\_j$ are prime numbers. All $a\_i$, except the first one, will be generated using these numbers. The first $c\_1$ of them will be generated using the formula $a\_i = (x\_1 \cdot a\_{i-1} + y\_1) \mod z\_1$, the next $c\_2$ --- using the formula $a\_i = (x\_2 \cdot a\_{i-1} + y\_2) \mod z\_2$, and so on. It is guaranteed that the sum of all $c\_j$ is $n-1$.

Output a single integer --- the minimal number of videobloggers who have to be convinced to record a video review on the game in order to achieve at least $m$ total video reviews in the Internet.

In the first sample, $a = \[2, 1, 3, 3, 4, 2, 3]$.

In the second sample, $a = \[2, 1, 3, 3, 4, 3, 2]$.