记忆游戏

题目描述

Alice和Bob正在玩一个记忆游戏，存在一个长度为 $n$ 的区间，最开始，区间中所有数都是 $0$。现在，Alice和Bob会对他们进行 $m$ 次操作，每次操作可能是如下2种操作之一：

1. 操作1：选择一段区间 $[L, R]$，并给出 $t$ 和 $x$，若 $t = 1$，则给这段区间中所有的奇数加上 $x$；若 $t = 0$，则给区间中所有的偶数加上 $x$。 操作的指令如下:

1 L R t x

2. 操作2：查询一段区间中所有数的和。 操作的指令如下:

2 L R

你需要写一个程序，处理并完成上述操作。

Tips：操作1中给所有的奇数或者偶数加上一个数，这里的奇偶指的是区间中每个位置的数值是奇数还是偶数，而不是指的是位置(下标)。例如：原来的序列为 $1 \ 2 \ 3 \ 4 \ 5$，我选择给 $[1,5]$ 之间所有的奇数加 $1$，则你应该给 $1,3,5$ 这三个数进行操作，操作后序列变成 $2 \ 2 \ 4 \ 4 \ 6$。

输入格式

第一行输入两个整数 $n,m$，表示序列长度以及操作次数。 接下来 $m$ 行，每行包含一个指令，指令如上述格式。

数据范围

对于 $40\%$ 的数据，满足 $1 \le n, m \le 10^3$。

对于 $70\%$ 的数据，满足 $1 \le n, m \le 10^4$。

对于 $100\%$ 的数据，满足 $1 \le n, m \le 5 \times 10^5$。

对于所有数据保证：

$1 \le x \le 10^9$。

$1 \le L \le R \le n$

$t \in \{0,1\}$

$op \in \{1,2\}$

输出格式

对于每个操作2, 输出答案。

样例 #1

样例输入 #1

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

样例输出 #1

100
45

提示

最开始，序列为：

0 0 0 0 0

在第一次操作后，序列变成：

0 15 15 15 15

第二次操作后，序列变成：

40 15 15 15 15

第三次查询区间 $[1,5]$，答案为 $40 + 15 \times 4 = 100$。

第四次查询区间 $[2,4]$，答案为 $3 \times 15 = 45$。