젠틀봇 | cho.sh

문제

Rainforest Inc.가 영국 북부 월섬스토에 대형 자동화 창고를 연다.

창고 안의 작업 로봇은 3차원으로 움직인다. 로봇은 한 시각에 제자리에 머무르거나 여섯 축 방향 가운데 하나로 1미터를 간다. 그래서 막는 것이 없다면 $(x_1, y_1, z_1)$ 에서 $(x_2, y_2, z_2)$ 까지 가는 데 $|x_2 - x_1| + |y_2 - y_1| + |z_2 - z_1|$ 번 움직여야 한다.

로봇은 하나같이 예의가 바르다. 마주 오던 두 로봇이 만나면 말없이 이야기를 마치고 한쪽이 옆으로 비켜 다른 쪽을 지나보낸다.

로봇은 항상 정수 좌표에 선다. 두 로봇이 같은 좌표에 서 있으면 안 되고, 한 시각에 두 로봇이 위치를 맞바꿔도 안 된다. 한 시각의 이동은 모두 동시에 일어난다.

창고 시험 가동에는 로봇 두 대만 넣는다. 관제기는 정해진 절차 하나로 두 로봇의 일정을 짜며, 그 절차는 출력 단락에 적어 두었다. 프로그램은 이 일정을 그대로 재현해야 한다.

입력

첫째 줄에 공백으로 구분된 정수 여섯 개 $x_0\ y_0\ z_0\ x_1\ y_1\ z_1$ 이 주어진다. 앞의 세 개는 1번 로봇의 출발 위치 $(x_0, y_0, z_0)$ , 뒤의 세 개는 도착 위치 $(x_1, y_1, z_1)$ 이다. 둘째 줄에는 2번 로봇의 값 여섯 개가 같은 형식으로 주어진다. 모든 좌표는 $-1000 \le x, y, z \le 1000$ 을 만족한다.

두 로봇의 출발 위치는 서로 다르고 도착 위치도 서로 다르다. 한 로봇의 출발 위치와 도착 위치는 같을 수 있다.

출력

관제기가 짠 일정을 출력한다. 0부터 세어 $T$ 번째 줄에는 시각 $T$ 에서 1번 로봇의 위치와 2번 로봇의 위치를 공백으로 구분한 정수 여섯 개로 출력한다. 첫 줄은 두 출발 위치이고 마지막 줄은 두 도착 위치이며, 이웃한 두 줄 사이에서 로봇은 많아야 1미터를 움직인다.

관제기는 한 번에 로봇 한 대만 걷게 하고 나머지 한 대는 그대로 세워 둔다. 먼저 두 가지를 정의한다.

$p$ 에서 $q$ 로 가는 직선 경로는 $p$ 에서 시작해 x 좌표를 한 칸씩 바꿔 $q$ 의 x 좌표와 같게 만들고, 이어서 y 좌표를, 그다음 z 좌표를 같은 방식으로 바꿔 $q$ 에서 끝나는 위치 목록이다.

막힌 위치 $m$ 을 피해 $p$ 에서 $q$ 로 가는 안전 경로는 다음과 같이 정한다. 여기서 $m$ 은 $p$ 와도 다르고 $q$ 와도 다르다. $p$ 에서 $q$ 로 가는 직선 경로에 $m$ 이 없으면 그 경로가 안전 경로다. $m$ 이 있으면 여섯 방향 $(1, 0, 0)$ , $(-1, 0, 0)$ , $(0, 1, 0)$ , $(0, -1, 0)$ , $(0, 0, 1)$ , $(0, 0, -1)$ 을 이 순서로 살펴 $p + s$ 에서 $q + s$ 로 가는 직선 경로에 $m$ 이 없는 첫 번째 $s$ 를 고른다. 그런 $s$ 는 항상 있다. 이때 안전 경로는 $p$ , $p + s$ 에서 $q + s$ 로 가는 직선 경로의 모든 위치, $q$ 를 차례로 이어 붙인 목록이다.

1번 로봇의 출발 위치와 도착 위치를 $a_0$ , $a_1$ 이라 하고 2번 로봇의 것을 $b_0$ , $b_1$ 이라 하자. 관제기는 아래에서 조건이 맞는 첫 번째 규칙을 쓴다.

$a_1 \ne b_0$ 이면 1번 로봇이 $b_0$ 을 피해 $a_0$ 에서 $a_1$ 까지 안전 경로를 걷고, 그다음 2번 로봇이 $a_1$ 을 피해 $b_0$ 에서 $b_1$ 까지 안전 경로를 걷는다.
그렇지 않고 $b_1 \ne a_0$ 이면 2번 로봇이 $a_0$ 을 피해 $b_0$ 에서 $b_1$ 까지 안전 경로를 걷고, 그다음 1번 로봇이 $b_1$ 을 피해 $a_0$ 에서 $a_1$ 까지 안전 경로를 걷는다.
둘 다 아니면 2번 로봇이 먼저 $c = b_0 + s$ 로 한 칸 비켜선다. 여기서 $s$ 는 위 목록에서 $b_0 + s \ne a_0$ 을 만족하는 첫 번째 방향이다. 이어서 1번 로봇이 $c$ 를 피해 $a_0$ 에서 $a_1$ 까지 안전 경로를 걷고, 마지막으로 2번 로봇이 $a_1$ 을 피해 $c$ 에서 $b_1$ 까지 안전 경로를 걷는다.

로봇이 경로를 걷는 동안에는 경로의 첫 위치를 뺀 나머지 위치마다 한 줄씩 출력하고, 걷지 않는 로봇은 그 줄에 자기 위치를 그대로 적는다. 위치가 하나뿐인 경로는 한 줄도 출력하지 않는다.