Although many people have eaten delicious strawberries, few have truly seen wild strawberries grow. They extend long tentacles from their branches, and whenever they encounter a suitable place, they take root and sprout, growing into a new strawberry plant. Therefore, when you encounter a strawberry plant in the forest, it usually means you will find a field of strawberries around it. However, these strawberries cannot always be carefree sprites; birds flying through the woods and herds of deer passing by occasionally love to eat these delicious berries. But their greatest threat comes from the brown bears who love strawberries. They can not only eat an entire field of strawberries but also rudely mess up a strawberry field. Thus, whenever a strawberry field grows larger, the forest sprites divide the field and replant it in open spaces to avoid being messed up by the rude brown bears. However, these kind-hearted sprites do not want to scatter the strawberries too much, as the strawberries would feel lonely. Therefore, they hope to divide the strawberry field according to the number of open spaces, such that each open space contains exactly one strawberry field connected by tentacles, and the minimum weight of strawberry berries in all open spaces is maximized. But the naive sprites do not know how to do this; can you help them?

Your task is to divide a strawberry field into $k$ parts to be moved to $k$ open spaces. This division scheme must satisfy the following conditions:

• The strawberries in each part must be connected directly or indirectly through tentacles to other strawberries in the same part.
• The minimum value of the sum of strawberry weights in each open space corresponding to this division scheme is maximized among all possible division schemes.
• Finally, output your division scheme and the result.

It is worth noting that although, in theory, the tentacles connecting the strawberries should follow certain relationships and form regular patterns, in the rich forest, well-growing strawberries often entangle their tentacles together. In this case, the sprites consider this to be a single tentacle. Therefore, the strawberry field given to you by the sprites may form complex patterns. Even due to the mischief of birds or deer, some strawberries in a strawberry field may not be connected to other strawberries through tentacles. However, this does not affect the final result; you just need to divide a strawberry field into $k$ small strawberry fields that are connected by tentacles.

Input

The first line contains three integers $n$, $m$, and $k$, where $n$ is the number of strawberry plants, $m$ is the number of tentacles extending between strawberries, and $k$ is the number of open spaces.

The next $n$ lines each contain two integers $i$ and $b_i$, representing that the $i$-th strawberry plant has $b_i$ grams of strawberries.

The following $m$ lines each contain two integers $p$ and $q$, representing that there is a tentacle connecting $p$ and $q$.

In addition, at the end of all this data, there is a separate line containing an integer $d$ used for scoring. For information about $d$, please refer to the Scoring section below.

Output

You need to output a total of $k+1$ lines. The first line contains an integer $x$, representing the maximum possible "minimum weight" of your divided strawberry fields. Then, in the following $k$ lines, the first integer of each line is $n_i$, representing the number of strawberry plants in the $i$-th strawberry field divided according to this weight. The following $n_i$ integers in that line are the indices of these strawberries. Note that the strawberries in one line must be connected by tentacles.

Scoring

You need to provide your output for the 10 given input files berry1.in ~ berry10.in and place them in your contestant directory. We will give scores based on the output files you provide. For a specific test case, if the $x$ in the first line of your output file does not match the division scheme below it, or if the output file itself has errors, you will not receive any points for that test case. Errors in the output file can be checked using the berry_check tool we provide. Only when this program outputs Yes can your output be considered acceptable.

Acceptable outputs will be further calculated to obtain your final score. If we denote the maximum minimum weight in your output file as $x$, and our optimal result as $best$, we calculate your score using the following formula:

$$score = 10 \times e^{\left[ -8 \times \left( \frac{d \times (best - x)}{best} \right)^2 \right]}$$

Here, $d$ is the integer input in the last line of the input data mentioned above.

Note

We provide a tool called berry_check as a way to test your output files. The method to use this tool is:

berry_check <input_file_name> <output_file_name>

After you call this file, berry_check will provide the test results based on the input and output files you provided, which include:

• Illegal exit: 0 points for this case.
• not connect: The lines output by your program contain disconnected components.
• duplicate: The same point was output twice.
• extra: The output file contains extra data.
• lack: The total number of points output is incorrect.
• answer not match: The result in the first line of the output does not match the actual result.
• Yes: The output is correct, and the next step of scoring will be performed.

Examples

Input 1

7 9 3 
1 4 
2 4 
3 3 
4 1 
5 5 
6 7 
7 2 
1 2 
1 6 
2 3 
2 5 
2 6 
4 5 
4 6 
6 7 
2000000000

Output 1

7 
2 1 6 
2 2 3 
3 4 5 7