Under construction

Still being built. Things may change

Rotation Transformation

Time limit2sMemory limit1024 MB

Summary
Given a 3x3 rotation matrix, find the rotation angle in degrees and the unit axis vector that produce it.
Level

Medium6 of 10

Topics
Geometry, Matrix, Math
Solved
No attempts yet

Problem


Julia loves simple motions very much, especially in three-dimensional space. Recently she found a matrix that corresponds to a rotation around an axis through the origin. The rotation is defined by a unit vector v=(vxvyvz)v = \begin{pmatrix} v_x \\ v_y \\ v_z \end{pmatrix} and a rotation angle α\alpha.

Look at the origin from the end of vv. If the rotation is counter-clockwise, then α\alpha is positive. Otherwise, α\alpha is negative.

The rotation matrix moves a point (xyz)\begin{pmatrix} x \\ y \\ z \end{pmatrix} to (x′y′z′)\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} as follows.

(x′y′z′)=(A11A12A13A21A22A23A31A32A33)(xyz).\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix}.

Julia does not know the values of vv and α\alpha. She asks you to recover them so she can continue her simple motion.

Input

You are given the matrix AA. It is guaranteed that there is a rotation matrix A′A' with ∣Aij′−Aij∣<10−13|A'_{ij} - A_{ij}| < 10^{-13} for all ii and jj.

Output

On the first line, print the angle α\alpha in degrees. On the second line, print the coordinates of the unit vector vv. It is guaranteed that 1≤∣α∣≤1791 \le |\alpha| \le 179. Print every number as precisely as you can. Your answer is accepted if the difference between each AijA_{ij} and the matrix built from your angle and unit vector does not exceed 10−610^{-6}.

Examples1

  1. Example 1

    Input
    0 -1 0
    1 0 0
    0 0 1
    
    Expected output
    90
    0 0 1