The Earth is gripped by an energy crisis. There's simply not enough to go
around! Desperate to unlock additional sources of energy, James has decided to
direct his attention downwards. Perhaps enough fossils can be found
underground and harvested for just a bit more fuel?

James has surveyed a linear stretch of ground, and has fortunately discovered
**N** fossils beneath the surface! From a cross-sectional view, the _i_th
fossil is at position **Pi** metres along the stretch of ground, at a depth of
**Di** metres below the surface. No two fossils are in exactly the same spot
(at both the same position and depth).

The next question is, of course, how the fossils might be unearthed most
efficiently. James plans to dig one or more vertical mine shafts in order to
access all **N** fossils. A mine shaft is defined by a position _p_ and a
depth _d_. Such a mine shaft can be represented as a vertical line segment at
position _p_ metres along the stretch of ground, running from the surface to a
point _d_ metres below the surface. James can dig such a shaft at a cost of
**S** \+ _d_ dollars, where **S** is a constant. Once it has been dug, it's
possible to reach fossils from the shaft by descending to the correct depth
and then digging horizontally through the earth at no additional cost, up to a
distance of at most **M** metres away from the shaft, where **M** is another
constant. In other words, each fossil _i_ is accessible from the shaft if
**Di** ≤ _d_ and |**Pi** \- _p_| ≤ **M**. Note that a mine shaft is permitted
to pass directly through a fossil (such that _p_ = **Pi** for some _i_).

Help James determine the minimum total cost of mine shafts which he must dig,
such that each of the **N** fossils will end up being accessible from at least
one of the shafts.

In order to reduce the size of the input data, the sequences **P1..N** and
**D1..N** will be derived from a series of temporary sequences **A1..(2*K)**,
the _i_th of of which has a length of **Li**. **P1..N** can be constructed by
concatenating together **A1..K**, while **D1..N** can be constructed by
concatenating together **A(K+1)..(2*K)**. It's guaranteed that the sum of
**L1..K** is equal to **N**, as is the sum of **L(K+1)..(2*K)**. For each
sequence **Ai**, you're given **Ai,1**, and **Ai,2..Li** may then be generated
as follows using given constants **Xi**, **Yi**, and **Zi** (please watch out
for integer overflow during this process):

**Ai,j** = ((**Xi** * **Ai,j-1** \+ **Yi**) % **Zi**) + 1 (for _j_ = 2..**Li**)

### Input

Input begins with an integer **T**, the number of sets of fossils. For each
set of fossils, there is first a line containing the space-separated integers
**N**, **S**, **M**, and **K**. Then, 2 * **K** lines follow. The _i_th of
these contains the space-separated integers **Li**, **Ai,1**, **Xi**, **Yi**,
and **Zi**.

### Output

For the _i_th set of fossils, output a line containing "Case #_i_: " followed
by the minimum total cost of mine shafts which James must dig (in dollars).

### Constraints

1 ≤ **T** ≤ 40
1 ≤ **N** ≤ 1,000,000
0 ≤ **S**, **M** ≤ 1,000,000,000
1 ≤ **K** ≤ 10
1 ≤ **Pi**, **Di**, **Ai,j** ≤ 1,000,000,000
1 ≤ **Li** ≤ **N**
0 ≤ **Xi**, **Yi** < **Zi** ≤ 1,000,000,000

### Explanation of Sample

In the first case, **P** = [5, 25] and **D** = [3, 4]. James should dig a
single mine shaft with _p_ = 15 and _d_ = 4 (at a cost of 5 + 4 = 9 dollars),
from which both fossils are barely accessible.

In the second case, **P** = [5, 26] and **D** = [3, 4]. James now requires two
mine shafts (for example one with _p_ = 5 and _d_ = 3 and another with _p_ =
26 and _d_ = 4), at a total cost of (5 + 3) + (5 + 4) = 17 dollars.

In the third case, **P** = [27, 11, 19, 15, 67] and **D** = [41, 34, 67, 40,
53].

In the fourth case, **P** = [555, 776, 673, 654, 339, 832, 887, 370, 555,
3794, 334, 180, 2491, 2018, 2805, 2 427, 1986, 3138, 1149, 495] and **D** =
[20814, 20463, 40527, 38076, 18468, 10958, 25830, 23128, 28505, 10884, 32935,
116 66, 8264, 771, 1207, 8930, 1299, 8521, 7277, 7440].