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:
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.
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.
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 xi, yi and zi describing a move. If xi = 1, this line describes a move of type 1, where yi denotes the segment number and zi denotes the increase in the length. If xi = 2, this describes a move of type 2, where yi denotes the segment number, and zi denotes the angle in degrees. (1 ≤ xi ≤ 2, 1 ≤ yi ≤ n, 1 ≤ zi ≤ 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.
1 1 3
2 3 90
2 5 48
1 4 1
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.