题目描述

Deni 想要变得更加独立，于是去当了一名公务员。她起初拥有一张空表格：

• 表格共有 10^5 行；
• 共有 N 列；
• 所有单元格初始值均为 0；
• 行号和列号都从 1 开始。

一整天里，她会收到三类请求：

第一类请求

给定：

• 行号 row
• 起始列 from
• 结束列 to
• 两个额外整数 st 和 d

其中 st 和 d 分别表示一个等差数列的首项和公差。

你需要把这个等差数列的前 (to - from + 1) 项，依次加到该行从 from 到 to 的各个单元格中。

第二类请求

给定：

• 行号 row
• 起始列 from
• 结束列 to

要求求出该行从 from 到 to 的当前元素和。

第三类请求

给定两个行号：row1 和 row2。

Deni 需要把第 row1 行的整个内容复制到第 row2 行。

请编写程序 queries，处理所有请求。

说明：首项为 st、公差为 d 的等差数列指 {a1, a2, a3, ...}，其中 a1 = st，且对 k ≥ 2 有 ak = a(k-1) + d。

输入格式

第一行输入两个正整数 N 和 Q，分别表示列数和请求数。

接下来 Q 行，每行是一条请求，格式如下：

• 若首个数字为 1，则该请求为第一类，后面跟五个数：row from to st d
• 若首个数字为 2，则该请求为第二类，后面跟三个数：row from to
• 若首个数字为 3，则该请求为第三类，后面跟两个数：row1 row2

输出格式

对于每个第二类请求，输出一行一个整数，表示所求区间和。

限制

• 最大允许内存为 16 MB
• 1 ≤ N ≤ 10^5
• 表格行数固定为 10^5
• 等差数列首项和公差均为区间 [-10^5, 10^5] 中的整数
• 1 ≤ Q ≤ 10^5
• 对所有包含 from 和 to 的请求，均满足 1 ≤ from ≤ to ≤ N

子任务

只有通过某个子任务中的全部测试，才能获得该子任务的分数。

样例输入

10 15
1 1 1 5 1 2
2 1 1 1
2 1 5 5
2 1 1 10
2 2 1 10
3 1 2
2 2 1 10
1 2 6 10 1 2
2 2 1 10
2 1 1 10
2 2 5 6
1 1 1 10 -1 -2
2 2 1 10
2 1 1 5
2 1 6 10

样例输出

1
9
25
0
25
50
25
10
50
0
-75

样例说明

原题说明如下：

• 在第一条请求执行后，第一行变为：

1 3 5 7 9 0 0 0 0 0

• 在复制操作（第 6 条请求）后，第二行被复制为相同内容；再对第二行做一次修改后，第二行变为：

1 3 5 7 9 1 3 5 7 9

• 注意第一行并不会因此改变。

• 在第 12 条请求执行后，前两行变为：

0 0 0 0 0 -11 -13 -15 -17 -19
1 3 5 7 9 1 3 5 7 9