에어로빅 (Large)

에어로빅 수업이 시작된다. 강사는 학생들에게 팔을 마음껏 휘둘러도 서로 부딪히지 않도록 매트 위에 자리를 잡으라고 말한다. 학생들이 한참을 서성이기만 하자 강사는 자리를 대신 정해 주는 프로그램을 만들어 달라고 부탁했다.

매트는 가로 $W$, 세로 $L$인 직사각형이다. $i$번 학생은 자기가 서는 지점을 중심으로 반지름이 $r_i$인 원을 혼자 써야 한다. 여기서 $r_i$는 그 학생의 팔이 닿는 거리다. 두 원은 맞닿아도 되지만 겹치면 안 되므로 $i$번 학생과 $j$번 학생의 중심 사이 거리는 $r_i + r_j$ 이상이어야 한다. 중심은 반드시 매트 위에 있어야 한다. 즉 $0 \le x_i \le W$이고 $0 \le y_i \le L$이다. 팔은 매트 밖으로 나가도 된다.

매트는 넉넉하다. 매트의 넓이는 모든 원의 넓이 합의 5배 이상이어서 $5\pi(r_1^2 + \cdots + r_N^2) \le W \cdot L$이 성립한다. 따라서 조건을 만족하는 배치는 항상 존재한다.

조건을 만족하는 배치는 여러 가지이므로 이 문제는 출력 항목에 적힌 규칙이 만드는 배치 하나만 정답으로 받는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 학생 수 $N$, 매트의 가로 $W$, 매트의 세로 $L$이 공백으로 구분되어 주어진다. 둘째 줄에 $N$개의 정수 $r_1, \ldots, r_N$이 주어진다. $r_i$는 $i$번 학생의 팔이 닿는 거리다.

제한은 다음과 같다.

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $1 \le W, L \le 10^9$
• $1 \le r_i \le 10^5$
• $5\pi(r_1^2 + \cdots + r_N^2) \le W \cdot L$
• 모든 테스트 케이스의 $N$을 더한 값은 6000 이하다.

각 테스트 케이스마다 한 줄에 Case #n: 을 출력하고, 이어서 정수 $2N$개를 공백 하나로 구분해 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, 출력하는 정수는 입력에 주어진 순서대로 $x_1$, $y_1$, $x_2$, $y_2$, 즉 $i$번 학생이 서는 지점 $(x_i, y_i)$의 좌표다.

배치는 다음 규칙으로 정한다.

먼저 학생을 반지름이 큰 순서로 정렬한다. 반지름이 같으면 입력에서 먼저 나온 학생이 앞에 온다. 이 순서를 배치 순서라고 한다.

$W \ge L$이면 학생을 세로줄로 묶는다. 한 줄에 속한 학생은 $x$가 같고 $y$가 커지는 순서로 선다. 이 경우 줄의 길이 한계는 $S = L$이고, 줄 안에서 움직이는 좌표 $f$는 $y$, 줄과 줄 사이에서 움직이는 좌표 $g$는 $x$다. $W < L$이면 두 축을 바꿔 가로줄로 묶는다. 한 줄에 속한 학생은 $y$가 같고 $x$가 커지는 순서로 서며, $S = W$, $f = x$, $g = y$다.

배치 순서대로 학생을 한 명씩 현재 줄에 넣는다.

• 첫 줄의 $g$는 0이다.
• 줄의 첫 학생은 $f = 0$에 선다.
• 그 외의 학생 $i$는 바로 앞에 놓인 학생 $p$를 기준으로 판단한다. $p$의 반지름이 $r_p$, 좌표가 $f_p$일 때 $f_p + r_p + r_i \le S$이면 학생 $i$는 같은 줄의 $f = f_p + r_p + r_i$에 선다.
• 그렇지 않으면 학생 $i$가 새 줄을 연다. 닫히는 줄의 첫 학생 반지름을 $R$이라 하면 새 줄의 $g$는 (닫히는 줄의 $g$) $+ R + r_i$이고, 학생 $i$는 그 줄의 $f = 0$에 선다.

이 규칙이 만드는 좌표는 모두 정수이며, 문제의 제한 아래에서 항상 매트 안에 들어간다.