Maximizing the Minimum Black Terror Distance

G Company has recently built a new R&D headquarters in a mysterious location using cutting‐edge technology. The headquarters is in the shape of a rectangular prism with F floors. Each floor consists of a grid of rooms arranged in M rows and N columns. A room is identified by three positive integers (p, q, r): it is on floor p, row q, and column r.

Employees can use teleportation to move from one room to an adjacent room in any of the six directions:

• If p > 1: teleport to room (p-1, q, r).
• If p < F: teleport to room (p+1, q, r).
• If q > 1: teleport to room (p, q-1, r).
• If q < M: teleport to room (p, q+1, r).
• If r > 1: teleport to room (p, q, r-1).
• If r < N: teleport to room (p, q, r+1).

Inside the headquarters, there are R rooms that serve as restaurants. However, the food in these restaurants spawns a terrifying black monster, and some employees are afraid of it. In particular, Mr. K, your boss, is extremely terrified by the monsters. He defines the black terror distance of any room as the minimum number of teleportations needed from that room to reach a restaurant. In other words, if a room requires at least d teleports to reach any restaurant, its black terror distance is d (in LaTeX: \(d\)).

When moving inside the building, Mr. K wants to choose a path from a given start room to a destination room such that the minimum black terror distance among all rooms along the path is as large as possible. Your task is to help him determine this maximum possible value.

Note: It is guaranteed that a path exists between the start and destination rooms.

inputFormat

The first line contains four integers: F, M, N, and R — the number of floors, the number of rows per floor, the number of columns per floor, and the number of restaurants, respectively.

The next R lines each contain three integers p, q, and r, indicating that the room at floor p, row q, column r is a restaurant.

The following line contains three integers representing the start room coordinates: p_s, q_s, r_s.

The last line contains three integers representing the destination room coordinates: p_t, q_t, r_t.

outputFormat

Output a single integer — the maximum possible value of the minimum black terror distance among all rooms along a path from the start to the destination room.

sample

1 3 3 1
1 2 2
1 1 1
1 3 3

1