Chef and Cake

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Chef once decided to prepare some nice dishes on his birthday. There are N items kept on his shelf linearly from position 1 to N. Taste of the ith item is denoted by a integer A_{i}.
He wants to make Q dishes. A dish will be made using some ingredients in the continuous range A_{L}, A_{L + 1}, , , A_{R} (1base indexing). Quality of the dish will be determined by the ingredient with minimum taste.
Chef wants help of his assistant Rupsa to find out sum and product of qualities of the dishes. As product of the qualities of the dishes could be very large, print it modulo 10^{9} + 7. Also, you are given an integer K and you are assured that for each dish, the size of continuous range of the ingredients (i.e. R  L + 1) will always lie between K and 2 * K, both inclusive.
Method of generation of Array A You are given nonnegative integer parameters a, b, c, d, e, f, r, s, t, m, A[1]
for x = 2 to N:
if(t^x mod s <= r) // Here t^x signifies "t to the power of x"
A[x] = (a*A[x1]^2 + b*A[x1] + c) mod m
else
A[x] = (d*A[x1]^2 + e*A[x1] + f) mod m
Method of generation of range of ingredients for Q dishes You are given nonnegative integer parameters L1, La, Lc, Lm, D1, Da, Dc, Dm
for i = 1 to Q:
L1 = (La * L1 + Lc) mod Lm;
D1 = (Da * D1 + Dc) mod Dm;
L = L1 + 1;
R = min(L + K  1 + D1, N);
Input
 The first line contains three integers N, K and Q.
 The second line contains the integers a, b, c, d, e, f, r, s, t, m, and A[1].
 Then third line contains the integers L1, La, Lc, Lm, D1, Da, Dc, and Dm
Output
Output two space separated integers: The sum of qualities of the dishes.
 The product of qualities of the dishes modulo 10^{9}+7.
Constraints
 1 ≤ N, Q ≤ 10^{7}
 1 ≤ K ≤ N
 0 ≤ a, b, c, d, e, f, r, s, t, m, A[1] ≤ 10^{9}+7
 1 ≤ Lm ≤ N  K + 1
 1 ≤ Dm ≤ K + 1
 1 ≤ La, Lc ≤ Lm
 1 ≤ Da, Dc ≤ Dm
 1 ≤ L1 ≤ N
 1 ≤ D1 ≤ K
Sub tasks
 Subtask #1: 1 ≤ N, Q ≤ 1000 (10 points)
 Subtask #2: 1 ≤ Q ≤ 10^{4} (20 points)
 Subtask #3: original constraints (70 points)
Example
Input: 4 2 1 1 1 1 1 1 1 1 1 1 100 1 1 1 1 3 1 1 1 2 Output: 13 13
Explanation
 The array A comes out to be {1, 3, 13, 83} and the first dish has L = 3 and R = 4. The minimum in this range is 13, thus the sum and product both are 13 and hence the answer.
Note
Multiplier for C# and Java have been reduced to 1.5 instead of 2.Author:  abhra73 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/CHEFCK 
Tags  abhra73, easymedium, may15, rangequeries, slidingrange 
Date Added:  11032015 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions