Background

Foreword: Although SCR has already been merged into JROI, as the person in charge of JROI, I still want to thank the SCR problem team for their selfless dedication, out of respect for the setters. We will not make major changes to the background story of the problem; we will only add a small amount of connecting text.

---

The beginner hotpot is boiling, so of course it is time to play a game.

Little L is a middle school student who likes playing Identity V. On this day, he had just self-studied the basic operations of vectors. While playing, he looked at the mechanism walls he drew with different lengths and directions (he was playing Mad Eyes), and came up with a wonderful idea.

Problem Description

Little L has $n$ vectors $\overrightarrow{a_1},\overrightarrow{a_2}\ldots\overrightarrow{a_n}$, and he wants you to help him answer the following two questions.

• For a given $l,r$, compute

$$\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}$$

• For a given $l,r$, compute

$$\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}$$

As time goes by, these vectors will also keep changing. Little L hopes that after changes happen, you can still give the answers.

Input Format

The first line contains two integers $n,m$, representing the number of vectors and the number of operations.

The next $n$ lines each contain two integers $x,y$. The $i$-th line represents the vector $\overrightarrow{a_i}$.

The next $m$ lines each start with an integer $opt$ indicating the operation type, followed by several integers describing the operation. There are five types of operations as follows.

1. Input three integers $i,x,y(1\leq i\leq n)$, add $(x,y)$ to $\overrightarrow{a_i}$.
2. Input three integers $i,x,y(1\leq i\leq n)$, subtract $(x,y)$ from $\overrightarrow{a_i}$.
3. Input two integers $i,t(1\leq i\leq n)$, modify $\overrightarrow{a_i}$ to $t\overrightarrow{a_i}$.
4. Input two integers $l,r(1\leq l<r\leq n)$, compute $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}$.
5. Input two integers $l,r(1\leq l<r\leq n)$, compute $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}$.

Output Format

For every operation of type 4 and type 5, output one line containing one integer, the answer to this operation.

3 5
1 1
4 5
1 4
1 1 3 6
2 3 3 0
4 2 3
3 2 3
5 1 3

12
84

Hint

Explanation for Sample 1

After the first two operations, the three vectors are $(4,7),(4,5),(-2,4)$. Then the query result is $4\times(-2)+5\times4=12$.

After the next operation, the three vectors are $(4,7),(12,15),(-2,4)$. The query result is $(4\times15-7\times12)+[4\times4-7\times(-2)]+[12\times4-15\times(-2)]=-24+30+78=84$.

---

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $20\%$ ): $n,m\leq 100$.
• Subtask 2 ( $30\%$ ): there is no operation type 5.
• Subtask 3 ( $50\%$ ): no special requirements.

For $100\%$ of the data, $2\leq n\leq 10^5$, $1\leq m\leq 10^5$, and it is guaranteed that for the vector $\overrightarrow{a_i}$ at any time, $-1000\leq x_i,y_i\leq 1000$.

---

About Vector Operations

For vectors $\overrightarrow{a},\overrightarrow{b}$ and a constant $\lambda$, suppose the coordinate representations of $\overrightarrow{a},\overrightarrow{b}$ are $(x_a,y_a),(x_b,y_b)$:

• $\overrightarrow{a}+\overrightarrow{b}=(x_a+x_b,y_a+y_b)$
• $\overrightarrow{a}-\overrightarrow{b}=(x_a-x_b,y_a-y_b)$
• $\lambda\overrightarrow{a}=(\lambda x_a,\lambda y_a)$
• $\overrightarrow{a}\cdot\overrightarrow{b}=x_ax_b+y_ay_b$
• $\overrightarrow{a}\oplus\overrightarrow{b}=x_ay_b-x_by_a$

Translated by ChatGPT 5