SPP2 - Recursive Sequence (Version X)

Sequence (ai) of natural numbers is defined as follows:

ai = bi (for i <= m)
ai = c1ai-1 + c2ai-2 + ... + ctai-t (for i > t)

where bj and cj are given natural numbers. Your task is to compute an and output it modulo 109+7.

The above is the description of the original problem SEQ. However, to be a problem in a regional contest, the description will be slightly modified to make the problem a little bit complicated: for almost all integers i > m, ai follows the formula given above, but there are q exceptions n1, n2, ..., nq:

ani = di1ani-1 + di2ani-2 + ... + ditiani-ti (for 1 <= i <= q)

Input

For each test case, the first line contains three integers n (m < n <= 109), m (1 <= m <= 100), q (0 <= q <= 100). The second line contains m integers b1, b2, ..., bm. The following line contains several integers, first comes t (t ≤ 100), then t integers c1, c2, ..., ct. The following q lines describe q special cases of the recurrent formula, each containing several integers, namely ni, ti (ti ≤ 100, ti < ni), di1, di2, ..., diti, as mentioned earlier. It is satisfied that all ni are distinct. All integers are non-negative. Unless specified, all integers are not greater than 109. Input is terminated by EOF. You might assume that all given data is correct. That is to say, all the required numbers can be fixed uniquely by the given input data.

Output

For each test case output the answer in a single line. Refer to the example for more format details.

Example

Input:
7 5 0
1 1 2 3 5
2 1 1
10 5 1
1 1 2 3 5
2 1 1
10 2 1 2

Output:
Case 1: 13
Case 2: 76

Added by:Fudan University Problem Setters
Date:2012-11-21
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regional Contest, Chengdu 2012

hide comments
2014-05-30 19:36:11 Min_25
@Francky
I assume that:
a_i = c_1 a_{i-1} + c_2 a_{i-2} + ... + c_t a_{i-t} (for i > max{m, t})

I think t > m is O.K. because missing data can be made up for by exceptions.
--ans(Francky)--> Many thanks, I'll try it when I'll find some time (hard task ;-) Congrats for all your great submissions.

Last edit: 2014-05-30 20:37:48
2013-09-12 10:09:12 Francky
Description says:
Sequence (ai) of natural numbers is defined as follows:

ai = bi (for i <= m)
ai = c1ai-1 + c2ai-2 + ... + ctai-t (for i > t)
===
I'm in trouble : if t>m, some data's missing, if t<m, there's double definition. Why don't set m==t in the problem ? I very like the idea of inserting exceptions. But I really don't understand why m!=t. Please, could you explain a little. Thanks in advance.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.