1002. 会自动求和的序列

题目描述

有两个长度为 $n$ 的序列 $a$ 和 $b$。

接下来依次经过 $m$ 天。每天开始时，对于所有 $1\le i\le n$，先执行 $a_i\leftarrow a_i+b_i$，然后执行当天的一次操作。

操作共有以下两种：

1 l r x：对于所有 $l\le i\le r$，执行 $b_i\leftarrow b_i+x$。

2 l r：求当前区间和 $\sum_{i=l}^{r}a_i$ 对 $2^{64}$ 取模后的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的组数。

对于每组测试用例，第一行包含两个整数 $n,m$，分别表示序列长度和天数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，表示两个序列的初始值。

接下来 $m$ 行，每行包含一次操作，格式为 1 l r x 或 2 l r。

对于 OJ 中唯一一组正式测试数据，保证：

$T=10^4$；

$2\le n\le 5\times 10^5$；

$1\le m\le 5\times 10^5$；

$1\le a_i,b_i\le 10^9$；

$1\le l<r\le n$；

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

$\sum n=10^6$；

$\sum m=10^6$。

输出格式

对于每次第二类操作，输出一行一个整数，表示询问结果对 $2^{64}$ 取模后的值。

结果应表示为 $0$ 到 $2^{64}-1$ 之间的十进制整数。

样例输入

1
4 4
1 2
2 1
1 1
2 2
2 1 4
1 1 2 1
2 1 3
2 2 4

样例输出

12
18
23

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1002