<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

265. Wizards
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The magical school of nature exists for thousands years. The wizards of the school are mastered in controlling animate nature. But it is still extremely difficult for them to manipulate matter itself. The best mages of the school were trying to learn the ways of manipulating the world around them for a long time. They started with the space distortion. Ancient books mentioned three basic space distortion spells: Translation, Scaling and Rotation. But all the experiments failed because it was extremely hard to predict the way the spell would affect the space. Nowadays the experiments arose again and you are to write the program which would help wizards in predicting of the results of some complex distortion spells. Complex spell consists of N consecutive basic distortion spells. And you are to predict its effect on M control vertices. For your convenience wizards measure the space in some 3-dimensional Cartesian system.
While casting Translation spell wizard specifies Translation vector and all the vertices are moved by the given x, y and z values.
While casting Scaling spell wizard specifies three Scaling parameters which show the Scaling factor for each of three coordinates (each x, y, and z coordinate of every vertex is multiplied by the corresponding Scaling factor).
While casting Rotation spell wizard specifies a point and Rotation angle and all the vertices are rotated in a clockwise direction about the ray from the origin through the specified point. The angle parameter specifies the angle of Rotation in degrees.

Input
The first line of the input file contains integer number N (1 <= N <= 1000). The next N lines describe complex spell. Each line contains one basic spell description in order they are applied. The first letter of each line specifies basic spell type. `T' stands for Translation spell, `S' stands for Scaling spell and `R' stands for Rotation spell. For Translation spell Translation vector is specified on the same line (three numbers: x, y, and z). For Scaling spell three Scaling factors are specified on the same line (three numbers: x, y, and z, each not greater than 1 by absolute value). For Rotation spell the point and the angle are specified on the same line (x, y, z and a, x^2+y^2+z^2>0). After that vertices description follows. First an integer number of vertices M is specified (1 <= M <= 100000). Then descriptions of M vertices follow. Each vertex description consists of 3 numbers - Cartesian coordinates of the vertex.
All the numbers in input are real and do not exceed 1000 by their absolute value.

Output
For each vertex in the input output its coordinates after the entire spell takes effect.

Sample test(s)

Input
Test #1
3
T 1.0 -2.4 0.7
S 0.2 4.0 2.0
R 0.0 0.0 1.0 2.0
3
0.0 0.0 1.0
0.0 1.0 0.0
1.0 0.0 0.0

Test #2
3
S 1.0 2.0 3.0
R 1.0 0.0 0.0 90.0
R 0.0 1.0 0.0 90.0
3
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0

Output
Test #1
0.53 -9.59 3.40
0.40 -5.59 1.40
0.73 -9.58 1.40

Test #2
0.00 0.00 -1.00
2.00 0.00 0.00
0.00 -3.00 0.00
Author:	Igor A. Kulkin
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004

<|response|>
## 1. Abridged Problem Statement

We are given `N` 3D transformations applied in order:

- `T x y z`: translate every point by vector `(x, y, z)`.
- `S x y z`: scale coordinates independently by factors `(x, y, z)`.
- `R x y z a`: rotate clockwise by `a` degrees around the ray from the origin through point `(x, y, z)`.

After these transformations, we are given `M` vertices. For each vertex, output its final coordinates.

Constraints:

- `1 <= N <= 1000`
- `1 <= M <= 100000`

A direct simulation of every transformation on every point would be too slow: `O(NM)`.

---

## 2. Key Observations

### Observation 1: Every operation is affine

Translation, scaling, and rotation in 3D can all be represented as affine transformations.

An affine transformation has the form:

```text
p' = A * p + b
```

where `A` is a `3 x 3` matrix and `b` is a translation vector.

### Observation 2: Use homogeneous coordinates

To combine all transformations uniformly, represent a point `(x, y, z)` as:

```text
[x]
[y]
[z]
[1]
```

Then every transformation becomes a `4 x 4` matrix.

For example:

```text
p' = M * p
```

where `M` is a `4 x 4` matrix.

### Observation 3: Compose all transformations first

If transformations are applied in this order:

```text
A1, A2, A3, ..., AN
```

then the final matrix is:

```text
Final = AN * ... * A3 * A2 * A1
```

The newest transformation is multiplied on the left.

So while reading transformations, if `cur` is the current transformation matrix:

```text
Final = cur * Final
```

Then each point is transformed once.

### Observation 4: Rotation uses Rodrigues' formula

Rotation is around an arbitrary axis from the origin through `(x, y, z)`.

First normalize the axis:

```text
len = sqrt(x^2 + y^2 + z^2)

ux = x / len
uy = y / len
uz = z / len
```

Let:

```text
c = cos(angle)
s = sin(angle)
```

Then the rotation matrix is:

```text
[ c+ux²(1-c)      uxuy(1-c)-uzs   uxuz(1-c)+uys ]
[ uyux(1-c)+uzs   c+uy²(1-c)      uyuz(1-c)-uxs ]
[ uzux(1-c)-uys   uzuy(1-c)+uxs   c+uz²(1-c)    ]
```

This is placed in the upper-left `3 x 3` block of the `4 x 4` matrix.

---

## 3. Full Solution Approach

### Step 1: Initialize the final matrix

Start with the identity matrix:

```text
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
```

This represents doing nothing.

---

### Step 2: Build a matrix for each spell

#### Translation

Translation by `(tx, ty, tz)`:

```text
[1 0 0 tx]
[0 1 0 ty]
[0 0 1 tz]
[0 0 0  1]
```

#### Scaling

Scaling by `(sx, sy, sz)`:

```text
[sx 0  0  0]
[0  sy 0  0]
[0  0  sz 0]
[0  0  0  1]
```

#### Rotation

Rotation around axis `(x, y, z)` by angle `a` degrees:

1. Normalize `(x, y, z)`.
2. Convert angle to radians.
3. Apply Rodrigues' formula to fill the upper-left `3 x 3` block.

The last row and column stay as in the identity matrix.

---

### Step 3: Compose transformations

If `Final` stores all previous transformations, and `cur` is the current spell matrix:

```text
Final = cur * Final
```

This order is important because points are treated as column vectors.

---

### Step 4: Apply final matrix to each point

For each point `(x, y, z)`:

```text
x' = Final[0][0] * x + Final[0][1] * y + Final[0][2] * z + Final[0][3]
y' = Final[1][0] * x + Final[1][1] * y + Final[1][2] * z + Final[1][3]
z' = Final[2][0] * x + Final[2][1] * y + Final[2][2] * z + Final[2][3]
```

Print the result with two digits after the decimal point.

---

### Complexity

Matrix size is constant, so each matrix multiplication costs `O(1)`.

Total complexity:

```text
O(N + M)
```

Memory usage:

```text
O(1)
```

apart from input/output buffers.

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);

using Matrix = array<array<double, 4>, 4>;

/*
    Creates a 4x4 identity matrix.

    Identity matrix represents a transformation that does nothing.
*/
Matrix identity_matrix() {
    Matrix mat{};

    for (int i = 0; i < 4; i++) {
        mat[i][i] = 1.0;
    }

    return mat;
}

/*
    Multiplies two 4x4 matrices.

    Returns:
        a * b
*/
Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix res{};

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            double sum = 0.0;

            for (int k = 0; k < 4; k++) {
                sum += a[i][k] * b[k][j];
            }

            res[i][j] = sum;
        }
    }

    return res;
}

/*
    Removes negative zero when printing.

    Due to floating point errors, values like -0.000000001 can appear.
    With setprecision(2), they would be printed as -0.00.
*/
double fix_zero(double x) {
    if (abs(x) < 0.0005) {
        return 0.0;
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    /*
        Final transformation matrix.

        Initially it is identity because no spell has been applied yet.
    */
    Matrix final_matrix = identity_matrix();

    for (int spell = 0; spell < N; spell++) {
        char type;
        cin >> type;

        /*
            Matrix for the current spell.
        */
        Matrix cur = identity_matrix();

        if (type == 'T') {
            /*
                Translation by vector (tx, ty, tz).

                Homogeneous matrix:

                [1 0 0 tx]
                [0 1 0 ty]
                [0 0 1 tz]
                [0 0 0  1]
            */
            double tx, ty, tz;
            cin >> tx >> ty >> tz;

            cur[0][3] = tx;
            cur[1][3] = ty;
            cur[2][3] = tz;
        }
        else if (type == 'S') {
            /*
                Scaling by factors (sx, sy, sz).

                Homogeneous matrix:

                [sx 0  0  0]
                [0  sy 0  0]
                [0  0  sz 0]
                [0  0  0  1]
            */
            double sx, sy, sz;
            cin >> sx >> sy >> sz;

            cur[0][0] = sx;
            cur[1][1] = sy;
            cur[2][2] = sz;
        }
        else if (type == 'R') {
            /*
                Rotation around the ray from the origin through (x, y, z).

                We normalize the axis and then use Rodrigues' rotation formula.
            */
            double x, y, z, angle_degrees;
            cin >> x >> y >> z >> angle_degrees;

            double len = sqrt(x * x + y * y + z * z);

            double ux = x / len;
            double uy = y / len;
            double uz = z / len;

            double angle = angle_degrees * PI / 180.0;

            double c = cos(angle);
            double s = sin(angle);
            double one_minus_c = 1.0 - c;

            /*
                Rodrigues' rotation matrix.

                This fills only the upper-left 3x3 block.
                The last row and column remain as in the identity matrix.
            */
            cur[0][0] = c + ux * ux * one_minus_c;
            cur[0][1] = ux * uy * one_minus_c - uz * s;
            cur[0][2] = ux * uz * one_minus_c + uy * s;

            cur[1][0] = uy * ux * one_minus_c + uz * s;
            cur[1][1] = c + uy * uy * one_minus_c;
            cur[1][2] = uy * uz * one_minus_c - ux * s;

            cur[2][0] = uz * ux * one_minus_c - uy * s;
            cur[2][1] = uz * uy * one_minus_c + ux * s;
            cur[2][2] = c + uz * uz * one_minus_c;
        }

        /*
            Compose transformations.

            Suppose previous transformations together are represented by F.
            The current transformation is C.

            A point p first becomes F * p, then C is applied:

                p' = C * (F * p) = (C * F) * p

            Therefore:
                final_matrix = cur * final_matrix
        */
        final_matrix = multiply(cur, final_matrix);
    }

    int M;
    cin >> M;

    cout << fixed << setprecision(2);

    for (int i = 0; i < M; i++) {
        double x, y, z;
        cin >> x >> y >> z;

        /*
            Apply final_matrix to homogeneous vector:

                [x]
                [y]
                [z]
                [1]
        */
        double nx =
            final_matrix[0][0] * x +
            final_matrix[0][1] * y +
            final_matrix[0][2] * z +
            final_matrix[0][3];

        double ny =
            final_matrix[1][0] * x +
            final_matrix[1][1] * y +
            final_matrix[1][2] * z +
            final_matrix[1][3];

        double nz =
            final_matrix[2][0] * x +
            final_matrix[2][1] * y +
            final_matrix[2][2] * z +
            final_matrix[2][3];

        nx = fix_zero(nx);
        ny = fix_zero(ny);
        nz = fix_zero(nz);

        cout << nx << ' ' << ny << ' ' << nz << '\n';
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys
import math


def identity_matrix():
    """
    Return a 4x4 identity matrix.

    The identity matrix represents a transformation that does nothing.
    """
    mat = [[0.0] * 4 for _ in range(4)]

    for i in range(4):
        mat[i][i] = 1.0

    return mat


def multiply(a, b):
    """
    Multiply two 4x4 matrices.

    Returns:
        a * b
    """
    res = [[0.0] * 4 for _ in range(4)]

    for i in range(4):
        for j in range(4):
            total = 0.0

            for k in range(4):
                total += a[i][k] * b[k][j]

            res[i][j] = total

    return res


def fix_zero(x):
    """
    Avoid printing -0.00 caused by floating-point round-off errors.
    """
    if abs(x) < 0.0005:
        return 0.0
    return x


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0

    n = int(data[idx])
    idx += 1

    final_matrix = identity_matrix()

    for _ in range(n):
        spell_type = data[idx].decode()
        idx += 1

        cur = identity_matrix()

        if spell_type == 'T':
            """
            Translation by vector (tx, ty, tz).

            Matrix:

            [1 0 0 tx]
            [0 1 0 ty]
            [0 0 1 tz]
            [0 0 0  1]
            """
            tx = float(data[idx])
            ty = float(data[idx + 1])
            tz = float(data[idx + 2])
            idx += 3

            cur[0][3] = tx
            cur[1][3] = ty
            cur[2][3] = tz

        elif spell_type == 'S':
            """
            Scaling by factors (sx, sy, sz).

            Matrix:

            [sx 0  0  0]
            [0  sy 0  0]
            [0  0  sz 0]
            [0  0  0  1]
            """
            sx = float(data[idx])
            sy = float(data[idx + 1])
            sz = float(data[idx + 2])
            idx += 3

            cur[0][0] = sx
            cur[1][1] = sy
            cur[2][2] = sz

        else:
            """
            Rotation around the ray from the origin through (x, y, z).

            We normalize the axis and use Rodrigues' rotation formula.
            """
            x = float(data[idx])
            y = float(data[idx + 1])
            z = float(data[idx + 2])
            angle_degrees = float(data[idx + 3])
            idx += 4

            length = math.sqrt(x * x + y * y + z * z)

            ux = x / length
            uy = y / length
            uz = z / length

            angle = angle_degrees * math.pi / 180.0

            c = math.cos(angle)
            s = math.sin(angle)
            one_minus_c = 1.0 - c

            """
            Fill the upper-left 3x3 block using Rodrigues' formula.
            """
            cur[0][0] = c + ux * ux * one_minus_c
            cur[0][1] = ux * uy * one_minus_c - uz * s
            cur[0][2] = ux * uz * one_minus_c + uy * s

            cur[1][0] = uy * ux * one_minus_c + uz * s
            cur[1][1] = c + uy * uy * one_minus_c
            cur[1][2] = uy * uz * one_minus_c - ux * s

            cur[2][0] = uz * ux * one_minus_c - uy * s
            cur[2][1] = uz * uy * one_minus_c + ux * s
            cur[2][2] = c + uz * uz * one_minus_c

        """
        Compose transformations.

        If previous transformations are represented by F
        and current transformation is C, then:

            new_F = C * F

        because the current transformation is applied after all previous ones.
        """
        final_matrix = multiply(cur, final_matrix)

    m = int(data[idx])
    idx += 1

    output = []

    for _ in range(m):
        x = float(data[idx])
        y = float(data[idx + 1])
        z = float(data[idx + 2])
        idx += 3

        """
        Apply final_matrix to the homogeneous vector [x, y, z, 1]^T.
        """
        nx = (
            final_matrix[0][0] * x +
            final_matrix[0][1] * y +
            final_matrix[0][2] * z +
            final_matrix[0][3]
        )

        ny = (
            final_matrix[1][0] * x +
            final_matrix[1][1] * y +
            final_matrix[1][2] * z +
            final_matrix[1][3]
        )

        nz = (
            final_matrix[2][0] * x +
            final_matrix[2][1] * y +
            final_matrix[2][2] * z +
            final_matrix[2][3]
        )

        nx = fix_zero(nx)
        ny = fix_zero(ny)
        nz = fix_zero(nz)

        output.append(f"{nx:.2f} {ny:.2f} {nz:.2f}")

    sys.stdout.write("\n".join(output))


if __name__ == "__main__":
    main()
```