F. X Marks the Pot
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bart the Bee loves the nectar from a specific flowerpot, but he does not remember the way from the hive to the flowerpot. So, he has created a master map. This map consists of $$$n$$$ instructions that, when followed in order, will take Bart to his favorite flowerpot. Each instruction can be in one of 2 types:

1. Turn $$$x$$$ degrees counterclockwise.

2. Go $$$y$$$ units forward.

We can model the landscape as a 2D coordinate system with the positive x-axis representing east and the positive y-axis representing north. The hive is located at the origin, $$$(0,0)$$$, and when Bart follows the map, he always starts at the hive facing due north.

To keep his master map safe, Bart has also created $$$q$$$ exact copies of the master map. However, Harry the Hornet broke into the nest, stole the master map, and tried to burn the map copies. Fortunately, only the edges of the map copies were burned, leaving the centers intact. Specifically, for each $$$i$$$ $$$(1\leq i\leq q)$$$, the $$$i$$$th map now only has the instructions from $$$l_i$$$ to $$$r_i$$$, inclusive $$$(1\leq l\leq r\leq n)$$$.

Without the master map, Bart still wants to use the burned maps to reach his favorite flowerpot. So, for each burned map, output the Euclidean distance from Bart's position after following the burned map to the position of his favorite flowerpot (with a maximum relative or absolute error of $$$10^{-4}$$$).

Note that when Bart follows a burned map, he follows it as if it were a normal map, starting from the hive facing due north.

Note: If using Java, consider using BufferedReader + PrintWriter (i.e. Fast I/O methods) to solve.

Input

The first line contains $$$n$$$ and $$$q$$$ $$$(1\leq n,q\leq 2\cdot10^5)$$$ — the number of instructions in the map, and the number of map copies.

The next $$$n$$$ lines start with an integer $$$k_i$$$ $$$(k_i\in[1,2])$$$ — the type of the $$$i$$$th instruction.

If $$$k_i=1$$$, the next integer on the same line will be an integer $$$x_i$$$ $$$(1\leq x_i\leq360)$$$ — the number of degrees to rotate counterclockwise.

If $$$k_i=2$$$, the next integer on the same line will be an integer $$$y_i$$$ $$$(1\leq y_i\leq10^6)$$$ — the number of units to walk forward.

The next $$$q$$$ lines contain 2 integers, $$$l_i$$$ and $$$r_i$$$ $$$(1\leq l\leq r\leq n)$$$ — the left and right endpoints of the unburned section of the $$$i$$$th map.

Output

For each of the $$$q$$$ map copies, print out the Euclidean distance from Bart's position after following the burned map to the position of his favorite flowerpot (with a maximum relative or absolute error of $$$10^{-4}$$$).

Example
Input
6 5
2 2
1 90
2 1
1 270
2 3
2 1
1 6
3 6
4 4
4 6
2 5
Output
0.0000000000
7.0710678119
6.0827625303
7.8102496759
3.0000000000
Note

The above diagram shows Bart's master map. A red arrow indicates a forward move and a black arrow indicates a rotation. He goes 2 units forward from $$$(0,0)$$$ to $$$(0,2)$$$, turns left, goes 1 unit forward to $$$(-1,2)$$$, turns right, goes 3 units forward to $$$(-1,5)$$$, then goes 1 unit forward to $$$(-1,6)$$$, the position of Bart's favorite flowerpot.

The above diagram shows the 2nd map copy. Here, Bart only follows instructions 3 through 6, inclusive. Now, his movements are represented through blue forward moves and black rotations. He moves 1 unit forward from $$$(0,0)$$$ to $$$(0,1)$$$, turns right, moves 3 units forward to $$$(3,1)$$$, then moves 1 unit forward to $$$(4,1)$$$.

Bart ends up at $$$(4,1)$$$, but the flowerpot is at $$$(-1,6)$$$. This means that Bart is $$$5\sqrt{2}\approx 7.0710678119$$$ units away from the flowerpot. (This distance is denoted in orange)