Autumn is a particular season, because it’s the season when all leaves fall down. Sometimes, the leaves fall in places that are not convenient, such as the ants garden. Andy the ant was playing one day at his garden when Autumn season started. All leaves started to fall down on Andy’s garden, Andy ran to his house and when the leaves stopped falling he went out. He realized that there were not only leaves but sticks on his garden. It is proved that an ant can carry at most ten times his weight, but a stick is much more than that, so Andy decided to clean the leaves and leave the sticks. This, of course, is a problem, because Andy can only jump over K sticks. Andy is very lazy, so he wants the better way to remove all leaves of his garden, but he doesn’t know how to figure out that, so he ask for your help in order to know that path. Andy always start at point (0,0) (his house), and he doesn’t need to come back to his house, so the last leaf is the last point on his path, but he has visit at least one time each leaf. For simplicity, leaves will be indexed from 1 to N, and Andy’s house will be assumed as point 0. Please note that Andy, like all ants, can’t break his walk line, so he can’t go around any stick, he can only jump over them.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case starts with 3 integers, N, M and K, these are the number of leaves, the number of sticks and the total number of sticks that Andy can jump on his path. N lines will follow, each one with 2 integers, Xi and Yi, separated by spaces, indicating the position of the leaf i in Andy’s garden. Then M lines will follow, each one with 4 integers, X1i, Y1i, X2i and Y2i, separated by spaces, indicating the position of the start and ending point of stick i on Andy’s garden.

Output

For each input case you must print the string "Scenario #i: " where i represents the test case you are analyzing (starting from 1), followed by the minimum distance that Andy have to walk in order to clean the leaves of his garden. Then one line with Andy’s path, if there are more than one path that has the minimal distance, print the first one when ordered lexicographically. If there exist no path then you should print "-1".

Sample

Input:
2
6 3 1
1 6
2 2
5 1
5 5
5 9
10 2
2 5 4 3
3 7 8 7
6 0 8 3
4 3 2
-2 -2
2 2
5 -1
6 6
0 3 1 0
-2 -5 5 2
0 5 7 0

Output:
Scenario #1: 26.044
0 2 3 6 4 1 5
Scenario #2: -1

Constraints - Subtask 1 (10%)

• 1 ≤ T, N, K ≤ 4
• M = 0
• -1000 ≤ Xi, Yi ≤ 1000
• -1000 ≤ X1i, Y1i, X2i, Y2i ≤ 1000

Constraints - Subtask 2 (15%)

• 1 ≤ T, N, K ≤ 10
• M = 0
• -1000 ≤ Xi, Yi ≤ 1000
• -1000 ≤ X1i, Y1i, X2i, Y2i ≤ 1000

Constraints - Subtask 3 (25%)

• 1 ≤ T, N, M, K ≤ 4
• -1000 ≤ Xi, Yi ≤ 1000
• -1000 ≤ X1i, Y1i, X2i, Y2i ≤ 1000

Constraints - Subtask 4 (50%)

• 1 ≤ T, N, M, K ≤ 10
• -1000 ≤ Xi, Yi ≤ 1000
• -1000 ≤ X1i, Y1i, X2i, Y2i ≤ 1000