3707 -- High-Dimensional Vector Correspondence

Language:

High-Dimensional Vector Correspondence

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 371		Accepted: 23		Special Judge

Description

Let < p₁, p₂,..., p_n > and < q₁, q₂,..., q_n > be two sequences of vectors in the m-dimensional Euclidean space. Is that possible to transform the former using a series of reflections and/or rotations so that it becomes the latter?

Input

The input consists of a single data set given in the format (n, m ≤ 512)

where

for all 1≤i≤n. All numbers except m and n are floating-point. Blank characters are irrevelant.

Output

It is known that both reflections and rotations are linear transformations, which are represented by squarematrices. In particular, in the m-dimensional Euclidean space, they are represented by m × m matrices. Furthermore, composition of linear transformations is represented by the product of the corresponding matrices. Therefore, if the desire sequence of reflections and rotations exists, you are to output a matrix H in the format

such that Hp_i = q_i for all 1≤i≤n; otherwise, you only have to output an asterisk ("*"). Blank characters are irrevelant.

Sample Input

2 2
-0.923896909208131 -0.150594719880319
-3.269301773087776E-002 0.871630392603206
0.402113583440769 -0.845321793468377
0.735234663492202 0.469295604408862

Sample Output

2
-0.569248928113214700 0.822165225390831260 
0.822165225390831590 0.569248928113214810

Source

POJ Founder Monthly Contest – 2008.12.28, frkstyc