You're about to put on an exciting show at your local circus — a parkour
demonstration! **N** platforms with adjustable heights have been set up in a
row, and are numbered from 1 to **N** in order from left to right. The initial
height of platform _i_ is **Hi** metres.

When the show starts, **M** parkourists will take the stage. The _i_th
parkourist will start at platform **Ai**, with the goal of reaching a
different platform **Bi**. If **Bi** > **Ai**, they'll repeatedly jump to the
next platform to their right until they reach **Bi**. If **Bi** < **Ai**,
they'll instead repeatedly jump to the next platform to their left until they
reach **Bi**. All of the parkourists will complete their routes simultaneously
(but don't worry, they've been trained well to not impede one another).

Not all parkourists are equally talented, and there are limits on how far up
or down they can jump between successive platforms. The _i_th parkourist's
maximum upwards and downwards jump heights are **Ui** and **Di**,
respectively. This means that they're only able to move directly from platform
_x_ to some adjacent platform _y_ if **Hx** \- **Di** ≤ **Hy** ≤ **Hx** \+
**Ui**, where **Hx** and **Hy** are the current heights of platforms _x_ and
_y_, respectively.

With the show about to begin, a disastrous flaw has just occurred to you — it
may not be possible for all of the parkourists to actually complete their
routes with the existing arrangement of platforms! If so, you will need to
quickly adjust some of the platforms' heights first. The height of each
platform may be adjusted upwards or downwards at a rate of 1 metre per second,
to any non-negative real-valued height of your choice, and multiple platforms
may be adjusted simultaneously. As such, if the initial height of platform _i_
is **Hi** and its final height is **Pi**, then the total time required to make
your chosen height adjustments will be `max{`|**Hi** \- **Pi**|`}` over
_i_=1..**N**.

Determine the minimum amount of time required to set up the platforms such
that all **M** parkourists will then be able to complete their required
routes. Note that you may not perform further height adjustments once the show
starts. The platform heights must all remain constant while all **M**
parkourists complete their routes.

In order to reduce the size of the input data, you're given **H1** and **H2**.
**H3..N** may then be generated as follows using given constants **W**, **X**,
**Y**, and **Z** (please watch out for integer overflow during this process):

**Hi** = (**W** * **Hi-2** \+ **X** * **Hi-1** \+ **Y**) % **Z** (for _i_=3..**N**)

### Input

Input begins with an integer **T**, the number of shows. For each show, there
is first a line containing the space-separated integers **N** and **M**. The
next line contains the space-separated integers **H1**, **H2**, **W**, **X**,
**Y**, and **Z**. Then, **M** lines follow. The _i_th of these lines contains
the space-separated integers **Ai**, **Bi**, **Ui**, and **Di**.

### Output

For the _i_th show, print a line containing "Case #_i_: " followed by 1 real
number, the minimum amount of time required to set up the platforms (in
seconds). Absolute and relative errors of up to 10-6 will be ignored.

### Constraints

1 ≤ **T** ≤ 85
2 ≤ **N** ≤ 200,000
1 ≤ **M** ≤ 20
0 ≤ **Hi** < **Z**
0 ≤ **W**, **X**, **Y** < **Z**
1 ≤ **Z** ≤ 1,000,000
1 ≤ **Ai**, **Bi** ≤ **N**
0 ≤ **Ui**, **Di** ≤ 1,000,000
**Ai**, ≠ **Bi**

### Explanation of Sample

In the first case, **H** = [0, 10]. You can increase the first platform's
height by 3.5 and decrease the second's by 3.5 in 3.5 seconds, yielding **P**
= [3.5, 6.5]. The single parkourist will then be able to successfully complete
their route from platform 1 to platform 2 by jumping upwards by a height of at
most 3.

In the second case, **H** = [50, 59, 55, 51, 47]. One optimal possibility is
**P** = [54.0, 54.5, 53.5, 52.5, 51.5].

In the third case, **H** = [46, 38, 38, 22, 8].

In the fourth case, **H** = [53, 25, 24, 81, 77, 40, 29, 21].