Make It Zero 3

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Problem description.
Aleksandra is the most popular girl in the city. Each boy can only dream about dating her. Other girls want to be like her.
Aleksandra is going to find herself a boyfriend. Of course such a beauty needs someone special. That's why she is going to announce a quiz. Even you can try your chances at this. Apart from boys, the girl also loves math. That's why this quiz is going to be mathematical.
Has you heard this story before? In fact, Aleksandra gave the problem Make It Zero 2 in CodeChef Febrary Challenge. Unfortunately, no boy can solve that problem optimally in all cases. Therefore, Aleksandra refactors the problem and asks for the optimal solutions to all boys in the city.
She has one number P and one array with N elements each. Let A_{i} be the i^{th} element of the array. She likes 0, that's why she is going to get rid of all non zero numbers in the array. In each turn she may choose 3 integers:
 1 ≤ s ≤ t ≤ N
 0 ≤ k ≤ 10000
 A_{i} = (k + A_{i}) modulo P
Input
The first line contains one interger T indicates the number of testcases.
The first line of each testcase contains two spaceseparated integers N and P, denoting the size of the array and the parameter P.
The size of the array may be very large. We represent it by concatenating (in order) many subarrays. The next line contains one interger M, denoting number of subarrays. The next M lines each contains 4 integers F_{i}, C_{i}, D_{i} and L_{i}. All subarrays are generated as follows:
 Denote B_{i,j} as the j^{th} element of the i^{th} subarray.
 B_{i,1} = F_{i}
 For each 1 < j ≤ L_{i}, B_{i,j} = (B_{i,j1} * C_{i} + D_{i}) module P
You can assume that N = L_{1} + L_{2} + ... + L_{M}.
Output
For each testcase, print one line containing one integer C, denoting the minimal number of the moves for erasing all non zero numbers from the array.Constraints
 1 ≤ T ≤ 100
 1 ≤ M ≤ 100
 1 ≤ P ≤ 10
 0 ≤ F_{i}, C_{i}, D_{i} < P
 1 ≤ L_{i} ≤ 10^{15}
Example
Input: 3 3 1 1 0 0 0 3 4 10 4 3 0 0 1 5 0 0 1 5 0 0 1 3 0 0 1 6 6 1 0 1 1 6 Output: 0 2 5
Explanation
Example case 1: All numbers are zero.
Example case 2: Initially, A = {3, 5, 5, 3}. In the first turn, we choose s=2, t=3, and k=8, after which A = {3, 3, 3, 3}. Then all numbers will become zero after the second turn.
Example case 3: Initially, A = {0, 1, 2, 3, 4, 5}. One optimal solution is to change nonzero numbers to zero one by one.
Author:  ACRush 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/LMATRIX3 
Tags  ACRush, april14 
Date Added:  3032014 
Time Limit:  0.53535 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions