Mr. Fox sure loves his rocks! In fact, when he's not in a hurry, he often
looks at the rocks lying around near him to decide where to wander in his
forest.

Mr. Fox lives in a forest with **N** clearings, numbered from 0 to **N**-1,
with **P** one-way trails initially running amongst them. The **i**th trail
runs from clearing **Ai** to a different clearing **Bi**, and is littered with
**Ri** rocks. No two clearings are connected by multiple trails running in the
same direction, though they could be connected by 2 trails running in opposite
directions. Additionally, an interesting property of this forest is that a
trail from clearing **a** to clearing **b** may only exist if 0 ≤
floor(**b**/4) - floor(**a**/4) ≤ 1.

To entertain himself over a period of **D** days, Mr. Fox will cause one event
to occur on each day. The **i**th event may be one of 3 types, determined by
the value of **Ei**:

1. Given 3 integers **Xi**, **Yi**, and **Zi**, Mr. Fox will create a new trail from clearing **Xi** to a different clearing **Yi**, and drop **Zi** rocks onto it. It's guaranteed that no trail from **Xi** to **Yi** will exist at the start of the **i**th day, and that 0 ≤ floor(**Yi**/4) - floor(**Xi**/4) ≤ 1 will hold.

2. Given 2 distinct integers **Xi** and **Yi**, Mr. Fox will completely destroy the trail from clearing **Xi** to clearing **Yi** (which is guaranteed to exist at the start of the **i**th day). Note that, once such a trail is destroyed, a new trail from **Xi** to **Yi** may be created in the future.

3. Given 2 distinct integers **Xi** and **Yi**, Mr. Fox will take a "random stroll" starting at clearing **Xi**, and would like to determine the probability that he'll visit clearing **Yi** at least once during it.

A "random stroll" consists of repeating the following process potentially
infinitely: If Mr. Fox is currently in some clearing **c**, and there are no
outgoing trails from **c**, then the stroll ends immediately. Otherwise, he'll
consider all of the rocks on all of the outgoing trails from **c**, choose one
of these rocks uniformly at random, follow the trail on which that rock lies
to its destination clearing (without removing any rocks), and repeat the
process from his new clearing.

For each event of type 3, output the requested probability.

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the space-separated integers **N**,
**P**, and **D**.

Then, **P** lines follow, the **i**th of which contains the space-separated
integers **Ai**, **Bi**, and **Ri**.

Then, **D** lines follow, the **i**th of which contains the space-separated
integers **Ei**, **Xi**, and **Yi**. If **Ei** = 1, this line additionally
contains the integer **Zi**.

### Output

For the **i**th test case, print a line containing "Case #**i**: " followed by
the computed probabilities for each stroll that Mr. Fox takes. These
probabilities should be space-separated, and rounded to 6 decimal places.

Absolute errors of up to 2 * 10-6 will be ignored.

### Constraints

1 ≤ **T** ≤ 20
1 ≤ **N** ≤ 50,000
0 ≤ **P** ≤ 100,000
1 ≤ **D** ≤ 20,000
0 ≤ **Ai**, **Bi**, **Xi**, **Yi** < **N**
1 ≤ **Ei** ≤ 3
1 ≤ **Ri**, **Zi** ≤ 5

### Explanation of Sample

In the first test case, Mr. Fox does multiple strolls from clearing 0 while
looking out for clearing 3. His first stroll has probability 1 as he must
always end up at clearing 3. His second stroll has probability 1/2 as there's
a 50% chance he gets stuck in clearing 4. His third stroll has probability 2/3
as he now only goes to clearing 4 1/3 of the time. His fourth stroll has
probability 1/3 as he gets stuck in clearing 4 1/3 of the time, and in
clearing 1 1/3 of the time.