띠 행렬의 LU 분해

$N \times N$ 행렬 $A$가 주어진다. LU 분해는 $A = LU$ 꼴의 곱으로 나누는 것이다. $L$은 하삼각행렬, $U$는 상삼각행렬이다.

• 하삼각행렬은 $i < j$일 때 $L_{ij} = 0$인 행렬이다.
• 상삼각행렬은 $i > j$일 때 $U_{ij} = 0$인 행렬이다.

이 문제에서는 띠의 폭이 1인 띠 행렬만 다룬다. 즉 $A$는 주대각선과 바로 위아래 대각선에만 값이 있고, 나머지 자리는 모두 0이다.

$A = \begin{bmatrix} b_1 & c_1 & 0 & \cdots & 0 \\ a_2 & b_2 & c_2 & \cdots & \vdots \\ 0 & \ddots & \ddots & \ddots & 0 \\ \vdots & \ddots & a_{n-1} & b_{n-1} & c_{n-1} \\ 0 & \cdots & 0 & a_n & b_n \end{bmatrix}$

$L$의 대각 성분이 모두 1이 되도록 하는 $L$과 $U$를 구한다. 이런 $L$과 $U$는 존재하면 하나뿐이다.

첫째 줄에 정사각 행렬의 크기 $N$ ($1 \le N \le 1000$)이 주어진다. 다음 $N$개의 줄에 행렬 $A$의 성분이 한 줄에 $N$개씩 순서대로 주어진다.

모든 성분은 절댓값이 1000 이하인 정수이고, $|i - j| \ge 2$인 자리의 성분은 항상 0이다. 분해가 존재하는 입력에서는 $L$과 $U$의 모든 성분의 절댓값이 $10^6$ 이하임이 보장된다.

분해가 존재하고 $U$의 대각 성분이 모두 0이 아니면, 먼저 $N$개의 줄에 $L$을 출력하고 이어서 $N$개의 줄에 $U$를 출력한다. 각 줄에는 그 행의 성분 $N$개를 공백 하나로 구분해 적는다.

각 성분은 정확한 값을 소수 넷째 자리에서 반올림해 소수 셋째 자리까지 출력한다. 반올림은 0에서 먼 쪽으로 한다. 예를 들어 $0.0625$는 0.063, $-0.0625$는 -0.063이 된다. 반올림한 값이 0이면 부호를 붙이지 않고 0.000으로 출력한다.

분해가 불가능하거나 $U$의 대각 성분 중에 0이 있으면 첫째 줄에 -1만 출력한다.