Development of Small Flying Robots

You are developing small flying robots in your laboratory.

The laboratory is a box-shaped building with K levels, each numbered 1 through K from bottom to top. The floors of all levels are square-shaped with their edges precisely aligned east-west and north-south. Each floor is divided into R × R cells. We denote the cell on the z-th level in the x-th column from the west and the y-th row from the south as (x, y, z). (Here, x and y are one-based.) For each x, y, and z (z > 1), the cell (x, y, z) is located immediately above the cell (x, y, z − 1).

There are N robots flying in the laboratory, each numbered from 1 through N. Initially, the i-th robot is located at the cell (x_i, y_i, z_i).

By your effort so far, you successfully implemented the feature to move each flying robot to any place that you planned. As the next step, you want to implement a new feature that gathers all the robots in some single cell with the lowest energy consumption, based on their current locations and the surrounding environment.

Floors of the level two and above have several holes. Holes are rectangular and their edges align with edges of the cells on the floors. There are M holes in the laboratory building, each numbered 1 through M. The j-th hole can be described by five integers u_1j, v_1j, u_2j, v_2j, and w_j. The j-th hole extends over the cells (x, y, w_j) where u_1j ≤ x ≤ u_2j and v_1j ≤ y ≤ v_2j.

Possible movements of robots and energy consumption involved are as follows.

You can move a robot from one cell to an adjacent cell, toward one of north, south, east, or west. The robot consumes its energy by 1 for this move.
If there is a hole to go through immediately above, you can move the robot upward by a single level. The robot consumes its energy by 100 for this move.

The robots never fall down even if there is a hole below. Note that you can move two or more robots to the same cell.

Now, you want to gather all the flying robots at a single cell in the K-th level where there is no hole on the floor, with the least energy consumption. Compute and output the minimum total energy required by the robots.

Input

The input consists of at most 32 datasets, each in the following format. Every value in the input is an integer.

N
M K R
x₁ y₁ z₁
...
x_N y_N z_N
u₁₁ v₁₁ u₂₁ v₂₁ w₁
...
u_1M v_1M u_2M v_2M w_M

N is the number of robots in the laboratory (1 ≤ N ≤ 100). M is the number of holes (1 ≤ M ≤ 50), K is the number of levels (2 ≤ K ≤ 10), and R is the number of cells in one row and also one column on a single floor (3 ≤ R ≤ 1,000,000).

For each i, integers x_i, y_i, and z_i represent the cell that the i-th robot initially located at (1 ≤ x_i ≤ R, 1 ≤ y_i ≤ R, 1 ≤ z_i ≤ K). Further, for each j, integers u_1j, v_1j, u_2j, v_2j, and w_j describe the position and the extent of the j-th hole (1 ≤ u_1j ≤ u_2j ≤ R, 1 ≤ v_1j ≤ v_2j ≤ R, 2 ≤ w_j ≤ K).

The following are guaranteed.

In each level higher than or equal to two, there exists at least one hole.
In each level, there exists at least one cell not belonging to any holes.
No two holes overlap. That is, each cell belongs to at most one hole.

Two or more robots can initially be located at the same cell. Also note that two neighboring cells may belong to different holes.

The end of the input is indicated by a line with a single zero.

Output

For each dataset, print the minimum total energy consumption in a single line.

Sample Input

2
1 2 8
1 1 1
8 8 1
3 3 3 3 2
3
3 2 3
1 1 2
1 1 2
1 1 2
1 1 1 1 2
1 2 1 2 2
2 1 2 1 2
2
2 3 100
100 50 1
1 50 3
100 1 100 100 3
1 1 1 100 2
5
6 7 60
11 11 1
11 51 1
51 11 1
51 51 1
31 31 1
11 11 51 51 2
11 11 51 51 3
11 11 51 51 4
11 11 51 51 5
18 1 54 42 6
1 43 59 60 7
5
6 4 9
5 5 3
1 1 1
1 9 1
9 1 1
9 9 1
3 3 7 7 4
4 4 6 6 2
1 1 2 2 3
1 8 2 9 3
8 1 9 2 3
8 8 9 9 3
5
10 5 50
3 40 1
29 13 2
39 28 1
50 50 1
25 30 5
3 5 10 10 2
11 11 14 14 2
15 15 20 23 2
40 40 41 50 2
1 49 3 50 2
30 30 50 50 3
1 1 10 10 4
1 30 1 50 5
20 30 20 50 5
40 30 40 50 5
15
2 2 1000000
514898 704203 1
743530 769450 1
202298 424059 1
803485 898125 1
271735 512227 1
442644 980009 1
444735 799591 1
474132 623298 1
67459 184056 1
467347 302466 1
477265 160425 2
425470 102631 2
547058 210758 2
52246 779950 2
291896 907904 2
480318 350180 768473 486661 2
776214 135749 872708 799857 2
0

Output for the Sample Input

Source: https://onlinejudge.u-aizu.ac.jp/problems/1607