30055번 - 우주비행사 정민

문제

우주비행사 정민이가 여행하고 있는 세계에는 서로 다른 차원이 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...을 출력한다.

제한

힌트