Background

Bessie brings her cow sisters to dance.

They have already planned the dance steps, but to make the performance look better, they need to know the average position of some leading cows at certain times, so the show can be more perfect.

Unfortunately, Bessie has too many sisters: up to $8\times 10^4$ cows may dance at the same time. She does not have a convenient and fast way to compute these average positions, so she asks you for help.

Problem Description

Bessie and her sisters have lined up. The coordinates of the $i$-th cow are $(x_i,y_i)$, where $x_i$ is the $x$-coordinate and $y_i$ is the $y$-coordinate.

Their dance formation can be transformed in the following ways:

1. Translation: for cows $x$ to $y$, $x_i\to x_i+a$, $y_i\to y_i+b$.
2. Rotation: cows $x$ to $y$ rotate clockwise by $g°$ around the center $(a,b)$.
3. Scaling (spread out): cows $x$ to $y$ scale by a factor of $\dfrac{p}{q}$ with center $(a,b)$. That is, let the cow’s coordinate before scaling be $A$, after scaling be $B$, and let $(a,b)$ be $G$. Then $\overrightarrow{GB}=\dfrac{p}{q}\overrightarrow{GA}$.

Bessie wants to know: for cows $x$ to $y$, their average position is $\left(\frac{\sum\limits^y_{i=x}x_i}{y-x+1},\frac{\sum\limits^y_{i=x}y_i}{y-x+1}\right)$.

The dance is about to start, so she can only give you $\texttt{1s}$.

Input Format

The first line contains two integers $n,m$.

The next $n$ lines each contain two integers $x_i,y_i$, representing the coordinates of the $i(1\le i\le n)$-th point.

The next $m$ lines each start with an integer $opt$.

If $opt=1$, then four integers $x,y,a,b$ follow, meaning one translation operation.

If $opt=2$, then five integers $x,y,a,b,g$ follow, meaning one rotation operation.

If $opt=3$, then six integers $x,y,a,b,p,q$ follow, meaning one scaling (spread out) operation.

If $opt=4$, then two integers $x,y$ follow, meaning a query of the average position of cows with indices $x \sim y$.

Output Format

Output the answer for each query, one per line. An error within $10^{-4}$ is allowed.

3 7
1 1
1 3
3 1
1 1 2 1 -2
4 1 3
2 1 3 2 0 270
4 1 2
3 1 2 2 2 2 1
4 1 3
4 3 3

2.3333333333 0.3333333333
2.0000000000 0.0000000000
1.6666666667 -1.0000000000
1.0000000000 1.0000000000

Hint

[Sample Explanation]

$0$ is the initial state. $1$ is the result after performing the sample operation 1 1 2 1 -2. $2$ is the result after performing the sample operation 2 1 3 2 0 270. $3$ is the result after performing the sample operation 3 1 2 2 2 2 1.

[Constraints and Conventions]

It is guaranteed that during computations, the absolute value of all numbers is less than or equal to $10^{15}$.

For $100\%$ of the testdata, $1\le n,m\le3\times10^5$, $1\le x\le y\le n$, $-32768\le a,b<32768$, $0< \dfrac{p}{q}\le 233333$, $0\le g\le359$, and the initial coordinate constraints are the same as for $a,b$.

Note:

• Please pay attention to constant-factor optimization.
• The input and output size is large; using scanf and printf is recommended.

Translated by ChatGPT 5