CF618E.Robot Arm

Roger is a robot. He has an arm that is a series of n segments connected to each other. The endpoints of the i-th segment are initially located at points (i - 1, 0) and (i, 0). The endpoint at (i - 1, 0) is colored red and the endpoint at (i, 0) is colored blue for all segments. Thus, the blue endpoint of the i-th segment is touching the red endpoint of the (i + 1)-th segment for all valid i.

Roger can move his arm in two different ways:

1. He can choose some segment and some value. This is denoted as choosing the segment number i and picking some positive l. This change happens as follows: the red endpoint of segment number i and segments from 1 to i - 1 are all fixed in place. Imagine a ray from the red endpoint to the blue endpoint. The blue endpoint and segments i + 1 through n are translated l units in the direction of this ray.

   

   In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B gets translated.

2. He can choose a segment and rotate it. This is denoted as choosing the segment number i, and an angle a. The red endpoint of the i-th segment will stay fixed in place. The blue endpoint of that segment and segments i + 1 to n will rotate clockwise by an angle of a degrees around the red endpoint.

   

   In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B get rotated around point A.

Roger will move his arm m times. These transformations are a bit complicated, and Roger easily loses track of where the blue endpoint of the last segment is. Help him compute the coordinates of the blue endpoint of the last segment after applying each operation. Note that these operations are cumulative, and Roger's arm may intersect itself arbitrarily during the moves.

罗杰是一个机器人。他的手臂由一系列 $n$ 个依次连接的线段构成。第 $i$ 条线段的两个端点初始位于点 $(i-1,\,0)$ 和 $(i,\,0)$。对所有线段，位于 $(i-1,\,0)$ 的端点被涂成红色，位于 $(i,\,0)$ 的端点被涂成蓝色。因此，对所有合法的 $i$，第 $i$ 条线段的蓝色端点恰好与第 $i+1$ 条线段的红色端点重合。

罗杰可以通过以下两种方式移动他的手臂：

1. 他可以选择某一条线段及一个数值。这记为选择线段编号 $i$ 并选取某个正数 $l$。该变换按如下方式进行：第 $i$ 条线段的红色端点以及第 $1$ 至 $i-1$ 条线段的所有端点均保持位置不变。设想一条从红色端点指向蓝色端点的射线；第 $i$ 条线段的蓝色端点以及第 $i+1$ 至 $n$ 条线段整体沿该射线方向平移 $l$ 个单位长度。

   

   在该图中，标有 $A$ 的红色点及其之前的线段保持不动，而标有 $B$ 的蓝色点及其之后的线段发生平移。

2. 他可以选择某一条线段并绕其旋转。这记为选择线段编号 $i$ 及一个角度 $a$。第 $i$ 条线段的红色端点将保持固定不动；该线段的蓝色端点以及第 $i+1$ 至 $n$ 条线段整体绕该红色端点顺时针旋转 $a$ 度。

   

   在该图中，标有 $A$ 的红色点及其之前的线段保持不动，而标有 $B$ 的蓝色点及其之后的线段绕点 $A$ 旋转。

罗杰将对其手臂执行 $m$ 次上述操作。这些变换较为复杂，罗杰很容易丢失最后一段线段的蓝色端点当前所在位置。请帮助他计算每次操作后最后一段线段的蓝色端点的坐标。注意：这些操作是累积进行的，且在移动过程中，罗杰的手臂可能任意自相交。

The first line of the input will contain two integers n and m (1 ≤ n, m ≤ 300 000) — the number of segments and the number of operations to perform.

Each of the next m lines contains three integers x__i, y__i and z__i describing a move. If x__i = 1, this line describes a move of type 1, where y__i denotes the segment number and z__i denotes the increase in the length. If x__i = 2, this describes a move of type 2, where y__i denotes the segment number, and z__i denotes the angle in degrees. (1 ≤ x__i ≤ 2, 1 ≤ y__i ≤ n, 1 ≤ z__i ≤ 359)

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300\,000$），分别表示线段的数量和需要执行的操作数量。

接下来的 $m$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $z_i$，描述一次操作。若 $x_i = 1$，则该行为类型 1 的操作，其中 $y_i$ 表示线段编号，$z_i$ 表示长度的增量；若 $x_i = 2$，则该行为类型 2 的操作，其中 $y_i$ 表示线段编号，$z_i$ 表示角度（单位：度）。（$1 \leq x_i \leq 2$，$1 \leq y_i \leq n$，$1 \leq z_i \leq 359$）

Print m lines. The i-th line should contain two real values, denoting the coordinates of the blue endpoint of the last segment after applying operations 1, ..., i. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if for all coordinates.

输出 m 行。第 i 行应包含两个实数值，表示在执行操作 1, ..., i 后，最后一段蓝色端点的坐标。若你的答案的绝对误差或相对误差均不超过 10 - 4，则视为正确。

具体而言，假设你对某个坐标的答案为 a，而裁判的标准答案为 b。对于所有坐标，只要满足 ，评测程序即认为你的答案正确。

The following pictures shows the state of the arm after each operation. The coordinates of point F are printed after applying each operation. For simplicity, we only show the blue endpoints of a segment (with the exception for the red endpoint of the first segment). For instance, the point labeled B is the blue endpoint for segment 1 and also the red endpoint for segment 2.

Initial state:

Extend segment 1 by 3.

Rotate segment 3 by 90 degrees clockwise.

Rotate segment 5 by 48 degrees clockwise.

Extend segment 4 by 1.

以下图片展示了每次操作后机械臂的状态。每次执行操作后，都会打印出点 $F$ 的坐标。为简化起见，我们仅显示每条线段的蓝色端点（第一条线段的红色端点除外）。例如，标记为 $B$ 的点是第 1 条线段的蓝色端点，同时也是第 2 条线段的红色端点。

初始状态：

将第 1 条线段延长 3 个单位。

将第 3 条线段顺时针旋转 90 度。

将第 5 条线段顺时针旋转 48 度。

将第 4 条线段延长 1 个单位。