Description

小 L 有 $n$ 个向量 $\overrightarrow{a_1},\overrightarrow{a_2}\ldots\overrightarrow{a_n}$，他希望你能够帮他回答下面两个问题。

• 对于给定的 $l,r$，求出

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

• 对于给定的 $l,r$，求出

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

随着时间的推移，这些向量也会不断发生变化，小 L 希望你在发生变化后仍然能给出答案。

Input Format

第一行两个整数 $n,m$，分别代表向量个数和操作次数。

接下来 $n$ 行，每行两个整数 $x,y$，第 $i$ 行表示向量 $\overrightarrow{a_i}$。

接下来 $m$ 行，每行首先有一个整数 $opt$ 表示操作序号，之后有若干个整数表示一次操作。一共有下面五种操作。

1. 输入三个整数 $i,x,y(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 加上 $(x,y)$。
2. 输入三个整数 $i,x,y(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 减去 $(x,y)$。
3. 输入两个整数 $i,t(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 修改为 $t\overrightarrow{a_i}$。
4. 输入两个整数 $l,r(1\leq l<r\leq n)$，求 $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}$。
5. 输入两个整数 $l,r(1\leq l<r\leq n)$，求 $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}$。

Output Format

对于所有的第四和第五种操作，一行有一个整数，为这次操作的答案。

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

样例 1 解释

前两次操作后三个向量分别为 $(4,7),(4,5),(-2,4)$，之后询问结果为 $4 \times(-2)+5\times4=12$。

下一次操作后三个向量分别为 $(4,7),(12,15),(-2,4)$，询问结果为 $(4\times15-7\times12)+[4\times4-7\times(-2)]+[12\times4-15\times(-2)]=-24+30+78=84$

---

数据规模与约定

本题采用捆绑测试。

• Subtask 1 ( $20\%$ )：$n,m\leq 100$。
• Subtask 2 ( $30\%$ )：没有操作五。
• Subtask 3 ( $50\%$ )：无特殊要求。

对于 $100\%$ 的数据，$2\leq n\leq 10^5$，$1\leq m\leq 10^5$，保证对于任意时刻的向量 $\overrightarrow{a_i}$，满足 $-1000\leq x_i,y_i\leq 1000$。

---

关于向量运算

对于向量 $\overrightarrow{a},\overrightarrow{b}$ 和常数 $\lambda$，假定 $\overrightarrow{a},\overrightarrow{b}$ 的坐标表示分别为 $(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$