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

a_i = b_i (for i <= m)
a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ta_i-t (for i > t)

where b_j and c_j are given natural numbers. Your task is to compute a_n and output it modulo 10⁹+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, a_i follows the formula given above, but there are q exceptions n₁, n₂, ..., n_q:

Input

For each test case, the first line contains three integers n (m < n <= 10⁹), m (1 <= m <= 100), q (0 <= q <= 100). The second line contains m integers b₁, b₂, ..., b_m. The following line contains several integers, first comes t (t ≤ 100), then t integers c₁, c₂, ..., c_t. The following q lines describe q special cases of the recurrent formula, each containing several integers, namely n_i, t_i (t_i ≤ 100, t_i < n_i), d_i1, d_i2, ..., d_iti, as mentioned earlier. It is satisfied that all n_i are distinct. All integers are non-negative. Unless specified, all integers are not greater than 10⁹. 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