Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
High-Dimensional Vector Correspondence
 Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 365 Accepted: 22 Special Judge

Description

Let < p1, p2,..., pn > and < q1, q2,..., qn > 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 Hpi = qi 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.8716303926032060.402113583440769 -0.8453217934683770.735234663492202 0.469295604408862

Sample Output

2
-0.569248928113214700 0.822165225390831260
0.822165225390831590 0.569248928113214810 

Source

[Submit]   [Go Back]   [Status]   [Discuss]