「THUPC2018」弗雷兹的玩具商店 / Toyshop - Problem

物是人非事事休，欲语泪先流。

弗雷兹在 C 市有一个玩具店，店里有 $n$ 种玩具，编号依次为 $1,2,\dots, n$，编号为 $i$ 的玩具的单价为 $c_i$ 元，一个该玩具提供的愉悦度为 $v_i$ 。

突然有一天，C市来了 $m$ 个小朋友。据可靠消息，这些小朋友会在一些时刻一起来店里买东西，其中第 $i$ 个小朋友每次都会带 $i$ 元（ $1\leq i\leq m$ ）。

由于某些玩具特别优秀，所以每次小朋友们都会在特定的编号范围内挑选玩具。

除此之外，由于小朋友们在一年前的清华校赛中就愉悦得无法自拔，所以弗雷兹放弃了对他们的治疗，于是小朋友们就可以无限制地购买玩具了。也就是说，对于任意玩具，每个小朋友在每次的购买件数都可以是任意的非负整数。

时代飞速发展，玩具的受欢迎程度和价格也会随着时代的发展而改变。

为了方便你处理这些信息，Yazid 进行了整理，发现这些日子里，弗雷兹的玩具商店里共发生了 $Q$ 个事件。

对于每个事件，都有 $3$ 个基本参数 $op,l,r$ 。其中 $op$ 为 $1$ 至 $3$ 之间的整数，代表了事件的类别：

对于 $op=1$ 的事件，Yazid 还会给你一个额外参数 $d$ ，表示这是一个价格调整事件：将编号在区间 $[l,r]$ 内的玩具的单价 $c$ 全部增加 $d$ 元。为了防止单价超过 $m$ 元导致玩具永远无法被小朋友们购买，弗雷兹会将所有超过 $m$ 的单价减去 $m$。（保证 $d$ 为不超过 $m$ 的正数）
对于 $op=2$ 的事件，Yazid还会给你一个额外参数 $b$ ，表示这是一个愉悦修正事件：将编号在区间 $[l,r]$ 内的玩具的愉悦度 $v$ 全部增加 $b$ 。（需要注意这里的 $b$ 可能是负数）
对于 $op=3$ 的事件，表示购买事件：所有的 $m$ 个小朋友来到弗雷兹的玩具商店，在编号范围在 $[l,r]$ 内的玩具中进行随意地购买。

现在，对于每一次的购买事件，你想知道：

第 $1$ 行 $2$ 个正整数 $n,m$，分别表示玩具数量、以及小朋友的数量。
第 $2$ 行 $n$ 个正整数 $c_1,\dots,c_n$，依次描述各玩具的单价。
第 $3$ 行 $n$ 个正整数 $v_1,\dots,v_n$，依次描述各玩具的愉悦度。
第 $4$ 行 $1$ 个非负整数 $Q$，表示事件的数量。
接下来 $Q$ 行依次描述所有事件，每行描述一个事件。每行的开头是 $3$ 个整数 $op,l,r$，意义见题目描述。
- 如果 $op=1$，接下来跟随 $1$ 个该事件的额外参数（整数） $d$，意义见题目描述。
- 如果 $op=2$，接下来跟随 $1$ 个该事件的额外参数（整数） $b$，意义见题目描述。
- 如果 $op=3$，接下来无任何额外参数。
- 保证 $1\leq l\leq r\leq n$。

对于每一行，如果包含多个数，则用单个空格将它们隔开。

input

4 10
1 6 10 2
100 2333 666 300
7
3 1 4
3 1 3
1 2 4 1
3 1 4
2 2 3 -1000
2 2 3 -600
3 2 4

output

对于第 $1$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,$ $300,$ $400,$ $600,$ $700,$ $2333,$ $2433,$ $2633,$ $2733,$ $2933$。

对于第 $2$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,$ $200,$ $300,$ $400,$ $500,$ $2333,$ $2433,$ $2533,$ $2633,$ $2733$。

对于第 $3$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$666,$ $1332,$ $1998,$ $2664,$ $3330,$ $3996,$ $4662,$ $5328,$ $5994,$ $6660$。

对于第 $4$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$0,$ $0,$ $300,$ $300,$ $300,$ $600,$ $733,$ $733,$ $900,$ $1033$。

根据这些信息，你将很容易计算出答案。

保证 $1\le n\leq 200,000$，$1\le m\leq 60$，$0\le Q\leq 30,000$。

保证 $1\leq c_i,d\leq m$。

保证 $0\leq v_i\leq 10^7$，$\left| b\right|\leq 10^3$。

这个提示本不该有，但善良的出题人还是想提醒你：所有小朋友所能获得的最大愉悦度之和有可能超过 $32$ 位有符号整数的范围。

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

HelloWorld信息学奥赛题库