Valentine's Day 2015 Contest

Marceline's songs were too powerful! The trapped princesses are breaking free of their cages and seem to be under a demonic trance. They chase Marceline through the Ice Kingdom, intent on wreaking havoc. These fanboys and fangirls seem to have a Fatal attraction to Marceline, so she soars away like an Eagle in order to escape the Ice Kingdom.

Unfortunately, she first has to navigate through the Ice King's ice labyrinth (made of cement). The labyrinth is a series of rooms shaped like rectangular prisms with floating obstacles in them. The levitating obstacles include ice shards, debris, and penguins. They are represented as cubes, identified by ~X~, ~Y~, and ~Z~, which specify the location of the edges of an obstacle. Each test case represents one such room.

The room has width ~W~, length ~L~, and height ~H~. There are ~N~ (~0 \le N \le 50\,000~) obstacles in the room. The exit to any labyrinth room is a ~3 \times 1 \times 3~ door where the top-right "cube" of the door is when ~W~, ~L~, and ~H~ (therefore, Marceline can exit from ~X = W-2 \dots W~, ~Y = L~, ~Z = H-2 \dots H~). The "cubes" in the "grid" are numbered from ~1 \dots W, L, H~. That is, ~W_i~, ~L_i~, and ~H_i~ (integers) each represent an edge and the three together represent an imaginary cube, and so they specify a cube, not a point.

For each move, Marceline can move one square up, down, left, right, backward or forward. She can't move diagonally (diagonals are bad luck to vampires that are featured in programming problems). Output the number of moves Marceline needs to make in order to reach the exit. She can only exit if she is directly in one of the "door cubes". She enters a room at ~X = 1~, ~Y = 1~, ~Z = 1~.

It is guaranteed that the distance she has to travel is not zero because no one in their right mind (this includes the Ice King, who might not be all there but is still sane) would build a room that is just a Cartesian plane. Marceline will always be able to exit a room (otherwise it wouldn't really be an exit, would it?).

Input Specification

The first line will contain 3 space-separated integers ~W~, ~L~, and ~H~ ~(3 \le W, L, H \le 100)~.
The second line will contain the single integer ~N~.
The next ~N~ lines will consist of a single-cube-sized obstacle in the space-separated format ~X~, ~Y~, ~Z~.

Output Specification

The least number of moves Marceline has to make in order to be right in front of the door so that she can escape.

Sample Input

4 4 4
8
2 2 2
3 2 2
2 3 2
2 2 3
3 3 2
3 2 3
2 3 3
3 3 3

Sample Output

5

Explanation

There are no relevant obstacles, so Marceline travels three "cubes" forward, one "cube" to the right, and one "cube" up to reach the bottom-left "cube" of the nine "cubes" (arranged in the rectangular prism with dimensions ~3 \times 1 \times 3)~ from which she can exit.