Longest Increasing Subsequence in a matrix - Hard

Description

Given a non empty M x N matrix with numbers. Starting from row 0 to row M-1.

You can pick at most one number from each row.

Find the max length of longest increasing sequence. 

Input

First line contains a number M

Second lines contains a number N

The rest M lines contains 3 numbers , for ith line:

$Matrix_{i0}$ , A , B , C.

Which means the first element of the row $Matrix_{i0}$ , for the rest of elements ( $ 1 \le j <n$ )

Matrix[i][j] = (Matrix[i][j - 1] * A + B) % C

Output

Output a number indicates the answer

Sample Input

4
6
2 4 9 7
1 3 2 8
4 8 5 33
10 8 7 22

Sample Output

4

Hint 1

Original matrix would look like

[2, 3, 0, 2, 3, 0]
[1, 5, 1, 5, 1, 5]
[4, 4, 4, 4, 4, 4]
[10, 21, 21, 21, 21, 21]

Constraints

$ 1 \le M , N \le 1000 $

$ 1 \le Matrix_{i0} , A , B , C \le 10^{4} $