Luis is becoming mad because his family hid all the Christmas gift in the family’s apartment, as his family is wealthy, they own a giant skyscraper that has many floors. By using the elevators, he wants to find all the gifts.

Luis’ parents went out and this is the perfect opportunity he has to sneak and view the Christmas gifts before Christmas eve! Luis earned a map of the building and marked the places where he can find the gifts. An elevator of the building can only go up and go down, now, you can assume that the elevators will always be on any floor and will be able to take it, however, the elevator takes one unit of time to bring Luis to any floor Ai, Luis should never leave the building at any moment using the elevators.

When Luis gets to any floor, he will start seeking the gift from the position (0, 0), after seeing all the room he will return to the elevator and keep his way. his searching ends when he finds all the gifts. Luis can ignore places that aren’t marked, so for example, if he knows that in a floor Fi there is no gifts, he can continue his way through the elevators. You can assume some things about Luis’ skyscraper building.

• He lives on the first floor of the skyscraper (floor 0, position 0, 0).
• Luis must be in each floor in the position (0, 0) in order to use an elevator.
• There will no gifts in his floor, because his parents try to hide it from him.
• He will never leave the building at any moment using elevators.
• Every floor of the skyscraper is perfectly the same one from another and can be represented as a NxN matrix.
• The elevators will be always available and can go up or down, never both. (You can assume that the elevators will be always moving).
• The coordinates of the gift are unique, that is, you can safely assume that no gift will overlap another one.
• Luis can only walk in a floor from point (a, b) through point (c, d) going into vertical and horizontal directions, that is, for each unit of time, he can move north, east, west or south.
• The transition from one elevator to another takes one unit of time, the time inside the elevator is immediate.

Finally, knowing the number of floors, the number of elevators and their values, the number of gifts and the position of each gift, and then the size NxN of every floor in the apartment, determine the minimum time that Luis can delay checking all his gifts and returning to the point 0, 0 on the last gift's floor after he sees the last one.

It is guaranteed that a solution will always exist.

Input

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

Four integers will begin every test case: M, E, K and N, denoting, respectively, the number of floors, the number of elevators, the number of gifts and the size for every floor in the skyscraper.

Then, E lines will follow, meaning that the i-th elevator goes ”up” Ei floors. (If the number is negative, then it goes down Ei floors.

After that, K lines will follow, each one of them with three integers denoting that the i-th gift is on floor f at the position (r, c).

Output

For each input case you must print the string "Scenario #i: " where i represent the case you’re analyzing (starting from 1), followed by the minimum units of time that takes Luis to check all the gifts.

Sample

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

Output:
Scenario #1: 3
Scenario #2: 2
Scenario #3: 4
Scenario #4: 3
Scenario #5: 17

Explanation of the last case

Luis starts in floor 0, takes an elevator to floor 2, lets call the three gift on the second floor (A, B, C) with A = {1, 3}, B = {4, 1}, C = {3, 4}, he can pick the gifts in several ways; A, B, C; B, C, A; C, A, B; C, B, A; A, C, B; B, A, C; However, the minimal combination is B, A, C and return to the origin (0, 0) that is 16 steps used plus the unit of time in the elevator, total = 17.

• 1 ≤ T ≤ 10

Subtask 1 - 5%

• 2 ≤ M ≤ 100
• 1 ≤ E ≤ 1
• 1 ≤ K ≤ 1
• 1 ≤ N ≤ 1 You can assume that the gift will be at the origin point (0, 0).

Subtask 2 - 5%

• 2 ≤ M ≤ 1,000
• 1 ≤ E ≤ 10
• 1 ≤ K ≤ 10
• 1 ≤ N ≤ 1 You can assume that the gift will be at the origin point (0, 0).

Subtask 3 - 10%

• 2 ≤ M ≤ 100
• 1 ≤ E ≤ 10
• 1 ≤ K ≤ 1
• 2 ≤ N ≤ 100

Subtask 4 - 10%

• 2 ≤ M ≤ 1,000
• 1 ≤ E ≤ 100
• 1 ≤ K ≤ 1
• 2 ≤ N ≤ 1,000

Subtask 5 - 20%

• 2 ≤ M ≤ 1,000
• 1 ≤ E ≤ 20
• 1 ≤ K ≤ 10
• 2 ≤ N ≤ 100 It is guaranteed that all the gift will be on different floors.

Subtask 6 - 20%

• 1 ≤ M ≤ 1,000
• 1 ≤ E ≤ 100
• 1 ≤ K ≤ 10
• 1 ≤ N ≤ 1,000

Subtask 7 - 30%

• 1 ≤ M ≤ 1,000
• 1 ≤ E ≤ 100
• 1 ≤ K ≤ 10
• 1 ≤ N ≤ 1,000,000