Astronaut Jeongmin

Astronaut Jeongmin is traveling in a world with two distinct dimensions. Each dimension is a grid whose width and height are both even, and each cell may contain a black hole. Anything in a cell with a black hole is sucked in and can never come out.

One day Jeongmin shouted "It's fine, I won't die~" and stepped outside the spaceship, then drifted away. Jeongmin is currently at $(0,0)$ in the $N_1 \times M_1$ dimension. The spaceship is parked at $(N_2-1, M_2-1)$ in the other dimension, which is $N_2 \times M_2$. Each second, Jeongmin can move one cell up, down, left, or right, or activate a dimension-travel gate. Black holes are generated every second according to the airflow. A new black hole appears only after Jeongmin's action for that second is finished.

The airflow moves toward larger column indices when the row index is even, and toward smaller column indices when the row index is odd. When it cannot move further horizontally, it moves down one row. From $(N-1, 0)$ it wraps to $(0,0)$ and cycles the same way. For example, with $N=4$ and $M=4$, the cycle goes as shown below.

In a $4 \times 4$ dimension with one black hole at $(2,2)$, a new black hole appears at $(2,3)$ after 1 second, following the airflow. After 6 seconds a new black hole appears at $(0,0)$, and after 15 seconds every cell has a black hole. No new black hole is created on a cell that already has one.

Jeongmin can cross between the two dimensions through dimension-travel gates. A gate exists in each dimension and occupies $A \times B$ cells. The two gates have the same size, but their positions may differ. Activating a gate from inside the gate area starts a 3-second dimension transfer, and Jeongmin arrives at the same internal gate coordinate in the other dimension. Before activation, Jeongmin can move freely inside the gate area. After activation, Jeongmin cannot move until arrival. From the moment the gate is activated until the transfer completes, Jeongmin is in the passage between dimensions, so black holes do not affect Jeongmin, even if they cover the gate.

Find the minimum time for Jeongmin to reach the spaceship without being swept into a black hole. If a black hole reaches the spaceship's cell at the moment Jeongmin arrives there, Jeongmin is swept into it together with the spaceship.

The first line contains the number of black holes $K$, the height $N_1$ and width $M_1$ of Jeongmin's dimension, and the height $N_2$ and width $M_2$ of the spaceship's dimension. ($0 \leq K \leq 100$; $2 \leq N_1, M_1, N_2, M_2 \leq 200$; $N_1, M_1, N_2, M_2$ are even)

The second line contains the height $A$ and width $B$ of the dimension-travel gate. ($1 \leq A \leq \min(N_1, N_2)$; $1 \leq B \leq \min(M_1, M_2)$)

The third line contains the coordinates $R_1$ and $C_1$, which are the position of the gate's internal origin $(0,0)$ in Jeongmin's dimension. ($0 \leq R_1 \leq N_1-A$; $0 \leq C_1 \leq M_1-B$)

The fourth line contains the coordinates $R_2$ and $C_2$, which are the position of the gate's internal origin $(0,0)$ in the spaceship's dimension. ($0 \leq R_2 \leq N_2-A$; $0 \leq C_2 \leq M_2-B$)

The next $K$ lines each give one black hole. Each line contains the dimension number $d$, the row $d_r$, and the column $d_c$, separated by spaces. $d$ is 1 if the black hole is in Jeongmin's dimension and 2 if it is in the spaceship's dimension. $d_r$ and $d_c$ are always within the dimension's bounds.

All input values are integers.

Print the minimum time, as an integer, for the spaceship to be reached. If the spaceship cannot be reached without being swept into a black hole, print hing....