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