时间限制： 3.0 秒

空间限制： 512 MB

题目描述

Charlie 和 David 想要比赛谁的记忆能力和心算能力更出色，所以他们设计了这样一个游戏：

1. 双方都在脑海中想象一列 $n$ 个整数，初始所有数字都为 $0$。
2. 游戏中两人轮流对这些数进行修改，修改允许对一段连续的区间统一加某个值，比如从第 $2$ 个数到第 $10$ 个数都加上 $20$。
3. 同时他们用计算机进行随机提问，问题是某一段连续的区间内数字的总和是多少。看谁能回答对尽量多的问题。

然而，Charlie 和 David 的记忆能力和心算能力都出类拔萃，游戏进行了很久也没有决出胜负，因此他们决定加大难度，允许根据值的奇偶性进行不同的操作，比如从第 $2$ 个数到第 $10$ 个数中所有的奇数都减去 $20$，而所有的偶数加上 $3$。加大难度之后，Charlie 发现自己逐渐处于劣势，他决定求助于你来帮他编写一个程序回答问题。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n,m$，分别代表数列长度和操作数目。

接下来 $m$ 行，每行有若干数字，描述一个修改或一次查询。每行的第一个数字 $f_i$ 描述了操作的类型：

1. 若 $f_i=0$，表示这是一次修改操作，接下来包含四个整数 $s_i,t_i,o_i,y_i~(1\leq s_i ≤ t_i ≤ n,~o_i\in\{0,1\},~|y_i|≤ 10^9)$，表示要修改的区间是第 $s_i$ 个数到第 $t_i$ 个数；$o_i$ 代表要处理这个区间中的奇数还是偶数，其中 $o_i=1$ 代表处理奇数，$o_i=0$ 代表处理偶数；$y_i$ 代表统一加的数值。例如 0 2 10 1 -20 代表 “从第 $2$ 个数到第 $10$ 个数中把所有的奇数都减去 $20$”。
2. 若 $f_i=1$，表示这是一次查询操作，接下来包含两个整数 $s_i,t_i~(1\leq s_i \leq t_i \leq n)$，表示要查询的问题是第 $s_i$ 个数到第 $t_i$ 个数的数字和。例如 1 2 10 代表“查询从第 $2$ 个数到第 $10$ 个数中所有数的和”。

输出格式

输出到标准输出。

对于每个查询操作输出一行一个整数，代表对应查询的答案。

5 4
0 2 5 0 15
0 1 3 0 40
1 1 5
1 2 4

100
45

样例 1 解释

样例第一行代表数组长度为 $5$，共有 $4$ 次操作。 一开始数组为：$[0~0~0~0~0]$。

第一次操作表示对 $[2,5]$ 的偶数加 $15$，修改后，数列为 $[0~15~15~15~15]$；

第二次操作表述对 $[1,3]$ 的偶数加 $40$，目前数组仅有第一个为偶数，所以修改后数列为 $[40~15~15~15~15]$。

第三次操作查询 $[1,5]$ 的和，值为 $100$。

第四次操作查询 $[2,4]$ 的和，值为 $45$。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题输入量较大，请采用效率较高的读入方式。

此外，本评测链接不保证任意时刻的绝对值最大子段和的范围不超过 $10^{18}$。因此你可能需要使用高精度整型数：

• 在 C++ 语言中，你可以使用 G++ 的 __int128 和 unsigned __int128 类型。
• 在 Java 语言中，你可以使用 BigInteger 类。
• 在 Python 语言中，默认的 int 类型即可满足精度要求。