우주 정거장 벽

Place-Y Technology 사는 곧 새 우주 정거장을 발사할 계획이다. 이 회사의 CEO는 완벽에 집착하는 것으로 알려져 있다. 예를 들어 그는 정거장의 바깥 면을 주기적으로 광택 내고, 그가 "우주 잔해"라고 부르는 것을 모두 치우라고 고집한다. 주된 목적은 사진에서 정거장이 좋아 보이게 하는 것이다. 엔지니어링 팀은 이것이 필요 없다고 CEO를 설득하려 했지만 실패했다. 그래서 팀은 정거장 밖에서 사람이 하는 작업을 최소화하면서 표면을 관리하는 새 기술을 개발했다. 이 관리는 로봇청소기처럼 정거장 표면 위를 움직이는 여러 대의 작은 로봇이 맡는다. 첫 비행 전에 Place-Y는 로봇 운용 중 충돌 위험을 평가해야 한다. 이 문제를 푸는 것이 바로 여러분의 역할이다.

이 문제에서 우주 정거장은 축에 평행한 단위 정육면체들의 집합으로 모델링한다. 정육면체들이 서로 연결되어 있을 필요는 없다. 각 로봇은 시각 $t = 0$에 정거장 단위 정육면체 중 하나의 노출된 면 중앙에서 출발한다. 노출된 면은 다른 정거장 정육면체와 공유하지 않는 면이다. 로봇은 그 면의 모서리와 평행한 네 방향 중 하나를 향한다. 매 시간 단위마다 로봇은 직진하여 다른 정육면체의 면으로 이동한다. 정거장의 모서리를 넘어 90도 꺾일 수 있으며, 항상 정거장과 접촉을 유지한다. 두 정육면체가 모서리를 공유하면 틈이 없으므로 로봇은 그 사이를 지나갈 수 없다.

그림 K.1: 입력 예시 1의 설명도. 점은 두 로봇의 출발점을 나타낸다.

정거장의 모양과 모든 로봇의 출발 위치가 주어졌을 때, 가장 이른 충돌 시각을 구하라. 충돌은 두 대 이상의 로봇이 같은 정육면체 면의 내부에 있는 시각 단위이거나, 두 로봇이 서로 위치를 맞바꾸려 하는 시각 단위에 일어난다. 맞바꾸는 경우는 입력 예시 3을 참고한다.

첫 줄에 두 정수 $n$과 $k$가 주어진다. $n$ ($1 \le n \le 100$)은 정거장 모양을 나타내는 영역의 개수이고, $k$ ($0 \le k \le 100$)는 로봇의 개수이다.

다음 $n$개 줄에는 각각 여섯 개의 정수 $x_1$, $y_1$, $z_1$, $x_2$, $y_2$, $z_2$가 주어진다. 여기서 $0 \le x_1 < x_2 \le 10^6$, $0 \le y_1 < y_2 \le 10^6$, $0 \le z_1 < z_2 \le 10^6$이다. 한 줄은 영역 하나를 나타내며, $x_1 \le x \le x_2$, $y_1 \le y \le y_2$, $z_1 \le z \le z_2$를 만족하는 모든 점 $(x, y, z)$가 정거장에 속한다. 단위 정육면체는 둘 이상의 영역에 포함될 수 있다.

이어서 $k$개 줄에 로봇 하나의 출발 위치가 주어진다. 한 줄에는 좌표 $x$, $y$, $z$와 두 방향 $\overrightarrow{f}$, $\overrightarrow{d}$가 들어 있다. 로봇은 단위 정육면체 $(x, y, z)$-$(x+1, y+1, z+1)$의 면 중 $\overrightarrow{f}$로 정해지는 면에서 출발한다. 처음 이동 방향은 $\overrightarrow{d}$로 정해진다. 두 방향은 x+, x-, y+, y-, z+, z- 중 하나의 문자열로 주어진다. x+는 x축의 양의 방향 $(1, 0, 0)$을 뜻하며, 나머지도 같은 방식이다. $\overrightarrow{f}$의 축 문자와 $\overrightarrow{d}$의 축 문자는 항상 다르다. 출발 정육면체는 정거장에 속하고, 주어진 면은 노출된 면임이 보장된다.

첫 번째 충돌 시각을 출력한다. 충돌이 한 번도 일어나지 않으면 ok를 출력한다.