LatticeLand

LeaperLad는 용암 호수 위에 떠 있는 원반 위, LatticeLand에서 눈을 뜬다. 그는 다른 원반 하나 위에 놓인 자신의 HeloPak을 발견한다. 그것만 손에 넣으면 이 함정에서 탈출할 수 있다는 것을 그는 알고 있다.

원반들은 직사각형 격자의 모든 격자점마다 하나씩 놓여 있다. 원반 사이 간격이 멀어서, 정지 상태에서 출발하면 LeaperLad는 바로 옆(상하좌우로 인접한) 원반으로만 뛸 수 있다. 하지만 일단 움직이기 시작하면 속도를 높일 수 있다.

밟는 원반마다 그는 다음 중 정확히 하나만 할 수 있다.

• 수평 방향 속도를 $1$만큼 늘리거나 줄인다.
• 수직 방향 속도를 $1$만큼 늘리거나 줄인다.
• 현재 속도를 그대로 유지한다.

한 원반에서는 한 축의 속도만 바꿀 수 있으며, 같은 원반에서 두 축을 동시에 바꿀 수는 없다. 그런 다음 그는 현재 속도 벡터만큼 다음 원반으로 뛴다. 따라서 정지 상태에서 한 직선으로 나아가면 $1$칸, $2$칸, $3$칸, $2$칸, $1$칸, … 과 같이 이동할 수 있다.

각 원반에서는 한 축의 속도만 바꿀 수 있으므로, 정지 상태에서 곧바로 대각선으로 뛸 수는 없다. 먼저 한 축으로 속도를 붙인 뒤에야 다른 축으로도 속도를 더할 수 있다.

일부 원반 쌍은 불의 벽으로 이어져 있으며, 그는 이 벽에 절대 닿아서는 안 된다. 벽에 얼마든지 가까이 다가갈 수는 있지만, 벽에 닿거나 도약 경로가 벽을 스치기만 해도 치명적이다. 또한 격자 밖으로 떨어져서도 안 된다.

LeaperLad는 HeloPak이 놓인 원반에 도달해 그 위에서 완전히 멈추려고 한다. 이때 필요한 최소 이동 횟수는 얼마인가?

입력의 각 줄은 서로 독립적인 하나의 상황을 공백으로 구분된 정수들의 나열로 나타낸다.

처음 두 정수는 격자의 너비 $w$와 높이 $h$이며, $1 \le w \le 64$, $1 \le h \le 64$이다. 이어지는 두 정수는 LeaperLad가 깨어나는 원반의 좌표이고, 그다음 두 정수는 HeloPak이 놓인 원반의 좌표이다. 다음 정수 $f$는 불의 벽의 개수로 $0 \le f \le 6$이다. 그 뒤에는 $f$개의 벽이 이어지며, 각 벽은 두 끝점의 좌표를 나타내는 정수 네 개로 주어진다.

모든 좌표 $(x, y)$는 $0 \le x \le w - 1$, $0 \le y \le h - 1$을 만족한다. 모든 벽의 길이는 최소 $1$ 이상이다. LeaperLad와 HeloPak은 같은 원반에서 시작하지 않으며, 둘 다 불의 벽 위에 놓인 원반에서 시작하지 않는다. LeaperLad가 HeloPak에 도달할 수 있는 방법은 항상 존재한다.

상황은 최대 $50$개이다.

각 상황마다, LeaperLad가 HeloPak이 놓인 원반에 도달해 그 위에서 멈추는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.

위치는 그대로이고 속도만 바뀌는 이동도 한 번의 이동으로 센다. 예를 들어 같은 원반 위에 머문 채 속도를 $1$에서 $0$으로 줄이는 것도 한 번의 이동이며, 목적지 원반 위에서 완전히 멈추는 것 자체가 하나의 이동이다.