P-꺾은선

좌표평면에서 두 좌표가 모두 정수인 점을 p-점이라고 한다. p-선분은 좌표축 중 하나와 평행하고 두 끝점이 서로 다른 p-점인 닫힌 선분이다. $k$개의 p-선분으로 이루어지고 이웃한 두 선분이 항상 서로 수직인 꺾은선을 차수 $k$의 p-꺾은선이라고 한다.

여러 개의 p-선분과 서로 다른 두 p-점 $A$, $B$가 주어진다. $A$와 $B$를 잇고 주어진 어떤 p-선분과도 공통점을 갖지 않는 p-꺾은선의 최소 차수를 구하거나, 그러한 p-꺾은선이 존재하지 않음을 판정하여라.

p-꺾은선의 꼭짓점은 임의의 p-점이 될 수 있으며, 입력에 등장하는 좌표로 제한되지 않는다. p-선분의 끝점에서 만나는 것도 공통점으로 간주하므로, p-꺾은선은 모든 p-선분에서 완전히 떨어져 있어야 한다.

첫째 줄에 p-점 $A$의 좌표를 나타내는 두 정수 $x$, $y$ ($0 \le x, y \le 10^9$)가 주어진다. 둘째 줄에 같은 형식으로 p-점 $B$의 좌표가 주어진다. 셋째 줄에 p-선분의 개수 $n$ ($1 \le n \le 50$)이 주어진다. 이어지는 $n$개의 줄에는 각각 한 p-선분의 두 끝점 좌표를 나타내는 네 정수 $x_1\ y_1\ x_2\ y_2$가 주어진다. 각 p-선분은 좌표축과 평행하며 두 끝점은 서로 다르다.

$A$와 $B$를 잇고 주어진 어떤 p-선분과도 공통점을 갖지 않는 p-꺾은선의 최소 차수를 한 줄에 출력한다. 그러한 p-꺾은선이 존재하지 않으면 대신 BRAK을 출력한다.