LU decomposition of a band matrix

You are given an $N \times N$ matrix $A$. An LU decomposition splits $A$ into a product $A = LU$, where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix.

• A lower triangular matrix has $L_{ij} = 0$ whenever $i < j$.
• An upper triangular matrix has $U_{ij} = 0$ whenever $i > j$.

This problem only deals with band matrices whose band has width 1. In other words, $A$ carries values on the main diagonal and on the two diagonals next to it, and every other entry is 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}$

Find $L$ and $U$ such that every diagonal entry of $L$ is 1. When such a pair exists, it is unique.

The first line contains the size $N$ of the square matrix ($1 \le N \le 1000$). Each of the next $N$ lines contains the $N$ entries of one row of $A$, in order.

Every entry is an integer with absolute value at most 1000, and every position with $|i - j| \ge 2$ holds 0. For inputs whose decomposition exists, every entry of $L$ and $U$ has absolute value at most $10^6$.

If the decomposition exists and no diagonal entry of $U$ is 0, print $L$ on $N$ lines and then $U$ on the next $N$ lines. Each line holds the $N$ entries of that row, separated by one space.

Round the exact value of each entry at the fourth decimal place and print three decimals. Round halves away from zero, so $0.0625$ becomes 0.063 and $-0.0625$ becomes -0.063. When the rounded value is zero, print 0.000 without a sign.

If the decomposition is impossible, or some diagonal entry of $U$ is 0, print -1 on the first line and nothing else.