방향이 가장 닮은 벡터 쌍

벡터에는 방향이 있고, 두 벡터 사이에는 사잇각이 하나 정해진다. 3차원 벡터의 집합이 주어질 때, 그중 사잇각이 가장 작은 두 벡터를 찾는 프로그램을 작성하시오.

입력은 여러 개의 데이터 집합으로 이루어진다. 한 데이터 집합은 3차원 벡터의 집합 하나를 정하는데, 일부 벡터는 입력에 그대로 적혀 있고 나머지는 아래 절차로 만든다.

각 데이터 집합의 형식은 다음과 같다.

m n S W
x1 y1 z1
x2 y2 z2
.
.
.
xm ym zm

첫 줄에 네 정수 $m$, $n$, $S$, $W$가 주어진다.

$m$은 세 성분이 입력에 직접 적힌 벡터의 개수다. 둘째 줄부터 $m$개의 줄에 그 벡터의 세 성분이 주어지며, 그중 $i$번째 줄은 벡터 $v_i = (x_i, y_i, z_i)$를 뜻한다. 모든 성분은 $100$ 이하의 양의 정수다.

$n$은 다음 절차로 만드는 벡터의 개수다.

int g = S;
for (int i = m + 1; i <= m + n; i++) {
  x[i] = (g / 7)     % 100 + 1;
  y[i] = (g / 700)   % 100 + 1;
  z[i] = (g / 70000) % 100 + 1;
  if (g % 2 == 0) { g = (g / 2); }
  else            { g = (g / 2) ^ W; }
}

$i = m + 1, \dots, m + n$에 대해 집합의 $i$번째 벡터 $v_i$의 세 성분은 이 절차가 정한 $x[i]$, $y[i]$, $z[i]$다.

$S$와 $W$는 데이터 집합의 첫 줄에 주어진 값이고, $1 \le S \le 10^9$, $1 \le W \le 10^9$이다.

벡터의 총 개수는 $2 \le m + n \le 12 \times 10^4$를 만족한다. 한 데이터 집합 안에서 똑같은 벡터가 두 번 이상 주어질 수도 있다.

$0$ 네 개가 적힌 줄은 입력의 끝을 뜻한다. 입력에 들어 있는 모든 데이터 집합의 $m + n$을 더한 값은 $16 \times 10^5$을 넘지 않는다.

각 데이터 집합마다, 주어진 집합에서 사잇각이 $0$이 아니면서 가장 작은 두 벡터를 한 줄에 출력한다. 방향이 서로 다른 벡터가 적어도 두 개 있다.

벡터는 세 성분으로 나타낸다. 두 벡터 $v_a$와 $v_b$의 쌍은 다음 형식으로 출력한다.

xa ya za xb yb zb

두 벡터 $(x_a, y_a, z_a)$와 $(x_b, y_b, z_b)$는 사전순으로 비교한다. 즉 $x_a < x_b$이거나, $x_a = x_b$이고 $y_a < y_b$이거나, $x_a = x_b$, $y_a = y_b$이고 $z_a < z_b$이면 $v_a < v_b$다. 쌍을 출력할 때는 이 순서로 더 작은 벡터를 먼저 쓴다.

사잇각이 가장 작은 쌍이 둘 이상이면, 쌍끼리 사전순으로 비교해 가장 작은 쌍을 출력한다. 쌍 $(v_i, v_j)$가 쌍 $(v_k, v_l)$보다 작다는 것은 $v_i < v_k$이거나, $v_i = v_k$이고 $v_j < v_l$인 경우를 뜻한다.