우주비행사 정민

우주비행사 정민이가 여행하는 세계에는 서로 다른 차원이 2개 있다. 각 차원은 가로와 세로 길이가 모두 짝수인 격자이며, 각 칸에 블랙홀이 있을 수 있다. 블랙홀이 있는 칸에 있는 것은 모두 빨려 들어가 다시는 빠져나올 수 없다.

어느 날 정민이는 "괜찮아 안 죽어~"라고 외치며 우주선 밖으로 나갔다가 표류하게 되었다. 정민이는 지금 $N_1 \times M_1$ 크기 차원의 $(0,0)$에 있다. 우주선은 또 다른 차원인 $N_2 \times M_2$ 크기 차원의 $(N_2-1, M_2-1)$에 멈춰 있다. 정민이는 1초에 한 번씩 상하좌우로 한 칸 이동하거나 차원 이동 게이트를 가동할 수 있다. 블랙홀은 기류를 따라 매초 새로 생성된다. 새 블랙홀은 그 초의 정민이 행동이 끝난 뒤에 생성된다.

기류는 행 번호가 짝수이면 열 번호가 증가하는 방향으로, 홀수이면 감소하는 방향으로 흐른다. 가로로 더 이상 나아갈 수 없으면 행 번호가 한 칸 증가하는 방향으로 이동한다. $(N-1, 0)$에 도달하면 $(0,0)$으로 이동해 같은 방식으로 순환한다. 예를 들어 $N=4$, $M=4$일 때 순환 방식은 아래 그림과 같다.

$4 \times 4$ 크기 차원에 $(2,2)$의 블랙홀이 하나 있다고 하자. 1초 후 기류를 따라 $(2,3)$에 새 블랙홀이 생성된다. 6초 후에는 $(0,0)$에 새 블랙홀이 생성되고, 15초 후에는 모든 칸에 블랙홀이 생긴다. 이미 블랙홀이 있는 칸에는 새 블랙홀이 생성되지 않는다.

정민이는 차원 이동 게이트를 통해 두 차원을 넘나들 수 있다. 차원 이동 게이트는 두 차원에 각각 있으며, $A \times B$ 칸을 차지한다. 두 게이트의 크기는 같지만 위치는 다를 수 있다. 게이트 내부에서 게이트를 가동하면 3초에 걸쳐 차원을 이동하며, 다른 차원의 같은 게이트 내부 좌표에 도착한다. 가동 전에는 게이트 안을 자유롭게 움직일 수 있지만, 가동 후에는 도착할 때까지 움직일 수 없다. 게이트를 가동한 순간부터 차원 이동이 끝날 때까지 정민이는 차원 사이의 통로에 있으므로, 블랙홀이 게이트를 덮더라도 영향을 받지 않는다.

정민이가 블랙홀에 휩쓸리지 않고 우주선에 도착하는 최단 시간을 구하라. 정민이가 우주선에 도착한 시각에 블랙홀이 우주선 위치에 도달하면, 정민이는 우주선과 함께 블랙홀에 휩쓸린다.

첫 번째 줄에 블랙홀의 개수 $K$, 정민이가 있는 차원의 세로 길이 $N_1$, 가로 길이 $M_1$, 우주선이 있는 차원의 세로 길이 $N_2$, 가로 길이 $M_2$가 주어진다. ($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$는 짝수)

두 번째 줄에 차원 이동 게이트의 세로 길이 $A$와 가로 길이 $B$가 주어진다. ($1 \leq A \leq \min(N_1, N_2)$; $1 \leq B \leq \min(M_1, M_2)$)

세 번째 줄에 정민이가 있는 차원의 게이트 내부 좌표 $(0,0)$이 놓인 위치 $R_1$, $C_1$이 주어진다. ($0 \leq R_1 \leq N_1-A$; $0 \leq C_1 \leq M_1-B$)

네 번째 줄에 우주선이 있는 차원의 게이트 내부 좌표 $(0,0)$이 놓인 위치 $R_2$, $C_2$가 주어진다. ($0 \leq R_2 \leq N_2-A$; $0 \leq C_2 \leq M_2-B$)

다섯 번째 줄부터 $K$개의 줄에 걸쳐 블랙홀 정보가 한 줄에 하나씩 주어진다. 각 줄에는 블랙홀이 있는 차원 번호 $d$, 좌표 $d_r$, $d_c$가 공백으로 구분되어 주어진다. $d$는 정민이가 있는 차원이면 1, 우주선이 있는 차원이면 2이다. $d_r$, $d_c$는 차원 크기를 벗어나지 않는다.

모든 입력은 정수이다.

우주선 도착까지의 최단 시간을 정수로 첫 번째 줄에 출력한다. 블랙홀에 휩쓸리지 않고 우주선에 도달할 수 없다면 hing...을 출력한다.