Background

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: https://www.cspro.org/。

Problem Description

For a point $(x, y)$ on the Cartesian coordinate plane, Xiao P defines the following two operations:

1. Scale by a factor of $k$: the $x$-coordinate becomes $kx$, and the $y$-coordinate becomes $ky$.
2. Rotate by $\theta$: rotate the point $(x, y)$ counterclockwise around the origin $(0, 0)$ by $\theta$ radians ($0 \le \theta < 2\pi$). It is easy to see that after rotation, the new $x$-coordinate is $x \cos \theta - y \sin \theta$, and the new $y$-coordinate is $x \sin \theta + y \cos \theta$.

After fixing an operation sequence $(t_1, t_2, \cdots, t_n)$ containing $n$ operations, Xiao P defines the following queries:

• i j x y: the new coordinates of $(x, y)$ after applying operations $t_i, \cdots, t_j$ ($1 \le i \le j \le n$).

Given the operation sequence, compute the results of $m$ queries.

Input Format

Read input from standard input.

The input consists of $n + m + 1$ lines.

The first line contains two positive integers $n$ and $m$ separated by spaces, representing the number of operations and the number of queries.

The next $n$ lines describe the $n$ operations in order. Each line contains an integer (the operation type) and a real number ($k$ or $\theta$) separated by spaces, in the form 1 k (scale by a factor of $k$) or 2 θ (rotate by $\theta$).

The next $m$ lines describe the $m$ queries in order. Each line contains four integers $i$, $j$, $x$, and $y$ separated by spaces, with meanings as described above.

Output Format

Write output to standard output.

Output $m$ lines. Each line contains two real numbers separated by spaces, representing the answer to the corresponding query.

10 5
2 0.59
2 4.956
1 0.997
1 1.364
1 1.242
1 0.82
2 2.824
1 0.716
2 0.178
2 4.094
1 6 -953188 -946637
1 9 969538 848081
4 7 -114758 522223
1 9 -535079 601597
8 8 159430 -511187

-1858706.758 -83259.993
-1261428.46 201113.678
-75099.123 -738950.159
-119179.897 -789457.532
114151.88 -366009.892

Hint

Sample Explanation

The 5th query only applies operation 8 to the input coordinates: scale by a factor of $0.716$.

$x$-coordinate: $159430 \times 0.716 = 114151.88$.

$y$-coordinate: $-511187 \times 0.716 = -366009.892$.

Because the exact computation method may differ, the program output may have a small difference from the true value. The sample output keeps only three decimal places.

Subtasks

• $80\%$ of the testdata satisfies: $n, m \le 1000$.
• All testdata satisfies:
  • $n, m \le 10^5$.
  • All input coordinates are integers with absolute value not exceeding $10^6$.
  • For each single scaling operation, the factor $k \in [0.5, 2]$.
  • For any operation interval $t_i, \cdots, t_j$ ($1 \le i \le j \le n$), the product of scaling factors $k$ is within $[0.001, 1000]$.

Scoring

If the absolute error between your floating-point output and the reference answer is at most $0.1$, you get full score for that test point; otherwise you get $0$.

Notes

• C/C++: It is recommended to use double to store floating-point numbers, and use scanf("%lf", &x); for input and printf("%f", x); for output. You may also use cin and cout. After #include <math.h>, you can use the trig functions cos() and sin().
• Python: You can directly use print(x) to output a floating-point number x. After from math import cos, sin, you can use the corresponding trig functions.
• Java: It is recommended to use double to store floating-point numbers. You can use System.out.print(x); for output. You can call trig functions with Math.cos() and Math.sin().

Translated by ChatGPT 5