Pierre Peintre is slaving away over a new abstract painting entitled _Rain
Over New York_. This will be a simple yet powerful piece, omitting incidental
details such as busy city dwellers shielding themselves with umbrellas, and
instead focusing on the fundamental atmosphere of a rainy metropolitan day. It
will be painted on a canvas which is subdivided into a grid of 1cm x 1cm
cells, with **N** rows and **M** columns. Each cell in this grid will be
filled in with a solid color, either black, white, grey, or blue.

The lower portion of _Rain Over New York_ will depict the skyline of New York
City. In each column _i_, the bottom-most **Hi** cells will be painted grey to
represent an austere skyscraper.

Somewhere above the buildings, Pierre will place a single, innocent raincloud.
In particular, the cloud can be any rectangle of white cells on the canvas, as
long as none of them are supposed to be grey.

Below the cloud, there must be a gentle rainfall, of course. Every cell which
has a white cell somewhere directly above it and a grey cell somewhere
directly below it, and which isn't supposed to be white or grey itself, should
be painted blue. Note that there may be no such cells, if the cloud is
immediately above the skyline.

All of the remaining cells in the painting will be painted black, providing a
serene nighttime backdrop for the scene.

Pierre knows that every painting he can produce like this will sell for an
enormous sum of money, but only if it's unique. As such, he'll paint as many
different paintings as he can by varying the position and dimensions of the
raincloud depicted in them. Two paintings are considered distinct if at least
one cell on the canvas is a different color in one painting than it is in the
other.

As an example, below is an illustration of 1 of the 246 possible paintings for
the fourth sample case:

![]({{PHOTO_ID:374610330166776}})

Thanks to the incredible sum of money which Pierre is sure to make from these
works, he'll be able to purchase all of the paint that he'll need. He always
buys his paint in cans of a fixed size, each of which contains just enough to
cover a surface of 1,000,000,007 cm2, and for each color, he'll buy just
enough such cans in order to be able to complete all possible distinct
variations of his painting, once each. Always one to plan ahead, Pierre would
like to figure out exactly how much paint of each color he'll have left over
when he's done.

The sequence **H1..M** can be constructed by concatenating **K** temporary
sequences of values **S1..K**, the _i_th of which has a length of **Li**. It's
guaranteed that the sum of these sequences' lengths is equal to **M**. For
each sequence **Si**, you're given **Si,1**, and **Si,2..Li** may then be
calculated as follows, using given constants **Ai** and **Bi**:

**Si,j** = ((**Ai** * **Si,j-1** \+ **Bi**) % (**N** \- 1)) + 1

### Input

Input begins with an integer **T**, the number of different base skylines
Pierre wants to use. For each skyline, there is first a line containing the
three space-separated integers, **N**, **M**, and **K**. Then **K** lines
follow, the _i_th of which contains the four space-separated integers **Li**,
**Si,1**, **Ai**, and **Bi**.

### Output

For the _i_th skyline, print a line containing "Case #**i**: " followed by
four space-separated integers, the total amount of black, white, grey, and
blue paint which Pierre will have left over, respectively (in cm2), after
completing all possible variations of his painting.

### Constraints

1 ≤ **T** ≤ 100
2 ≤ **N** ≤ 1,000,000,000
1 ≤ **M** ≤ 200,000
1 ≤ **K** ≤ 100
1 ≤ **Li** ≤ M
1 ≤ **Hi**, **Si,j** ≤ **N** \- 1
0 ≤ **Ai**, **Bi** < **N** \- 1

### Explanation of Sample

In the first case, there's only one possible painting, with the top cell
painted white, and the remaining two cells painted grey. Pierre will buy 1 can
each of white and grey paint, and have 1,000,000,006 and 1,000,000,005 cm2
left over of those colors, respectively.

In the second case, there are 6 possible paintings: three with the cloud
covering one cell, two with the cloud covering two cells, and one with the
cloud covering three cells. Therefore, Pierre will use 10 cm2 of white paint
in total.

The fourth case corresponds to the picture shown above.