Problem O: Linear Algebra Done What

Problem O: Linear Algebra Done What

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 12  Solved: 4
[Submit][Status][Web Board]

Description

Every student in SUSTech should learn linear algebra. But what can we do with linear algebra? Let's see.


A \(n*n\) square matrix \(A\) can be written as \(A = \left[ \begin{matrix}   a_{11} & a_{12} & \cdots & a_{1n}\\   a_{21} & a_{22} & \cdots & a_{2n} \\   \vdots & \vdots & \ddots & \vdots \\   a_{n1} & a_{n2} & \cdots & a_{nn}  \end{matrix}  \right]\). The transpose of \(A\) is \(A^T = \left[ \begin{matrix}   a_{11} & a_{21} & \cdots & a_{n1}\\   a_{12} & a_{22} & \cdots & a_{n2} \\   \vdots & \vdots & \ddots & \vdots \\   a_{1n} & a_{2n} & \cdots & a_{nn}  \end{matrix}  \right]\).


The matrix \(A\) is semi positive definite if for any column vector(can be regarded as a \(n*1\) matrix) \(x \in R^n\), \(x^T Ax \geq 0\). Define the F-norm of \(A\) by \(\|A\|_F^2=\sum_{i=1}^n \sum_{j=1}^n a_{ij}^2\).


Now we have a \(n*n\) square matrix \(A\) which can be decomposed into the form \(A=Q \Lambda Q^T\), where \(\Lambda = \left[ \begin{matrix} \lambda_1 \\ & \lambda_2 \\ & & \ddots \\ & & & \lambda_n \end{matrix} \right]\) is a diagonal matrix and \(QQ^T = I = \left[ \begin{matrix} 1 \\ & 1 \\ & & \ddots \\ & & & 1 \end{matrix} \right]\). We need you to find a \(n*n\) square semi positive definite matrix \(X\), such that the value of \(\|A-X\|_F\) is minimized.

Input

The first line is the number of the test cases \(T(1\leq T \leq 3)\).

For each test case, the beginning is an integer \(n(1\leq n \leq 300)\) denoting the size of the matrix \(A\).

Then, a \(n*n\) square real matrix \(Q(-100 \leq q_{ij} \leq 100, 1\leq i,j\leq n)\).

Last, \(n\) integers \(\lambda_1, \cdots, \lambda_n(-100 \leq \lambda_i \leq 100, 1\leq i \leq n)\).

It is guranteed that \(A=Q \Lambda Q^T\) and \(QQ^T = I\).


Output

A \(n*n\) square semi positive definite real matrix \(X\). You should keep exactly three decimal place for each real number.


Sample Input

1
2
1 0
0 1
2 2

Sample Output

2.000 0.000
0.000 2.000

HINT

[Submit][Status]