有一条由细胞组成的无限线。该行的某些单元格中有 $$$n$$$ 框。第 $$$i$$$ 个盒子位于单元格 $$$a_i$$$ 中,重量为 $$$w_i$$$。所有 $$$a_i$$$ 都是不同的,而且 $$$a_{i - 1} < a_i$$$ 对于所有有效的 $$$i$$$ 都成立。
您想要将一些盒子放在一起。将 $$$[l, r]$$$ 段中带有索引的框放在一起意味着您将移动其中一些框,使其位置形成某个段 $$$[x, x + (r - l)]$$$。
在一个步骤中,如果任何方框未被另一个方框占据,您可以将其移动到相邻单元格(即您可以选择 $$$i$$$ 并将 $$$a_i$$$ 更改为 $$$1$$$,所有位置应保持不同)。您花费 $$$w_i$$$ 单位的能量将盒子 $$$i$$$ 移动一个单元格。您可以按任意顺序移动任何框任意次数。
有时某些框的权重会发生变化,因此您有两种类型的查询:
1. $$$id$$$ $$$nw$$$ — 盒子 $$$id$$$ 的重量 $$$w_{id}$$$ 变为 $$$nw$$$。
2. $$$l$$$ $$$r$$$ — 您应该计算将索引为 $$$[l, r]$$$ 的盒子放在一起所需的最小总能量。由于答案可能相当大,因此打印除以 $$$1000\,000\,007 = 10^9 + 7$$$ 后得到的余数。请注意,在查询过程中这些框不会移动,您只需计算答案即可。
请注意,您应该最小化答案,而不是其模 $$$10^9 + 7$$$ 的余数。因此,如果您有两个可能的答案 $$$2 \cdot 10^9 + 13$$$ 和 $$$2 \cdot 10^9 + 14$$$,您应该选择第一个并打印 $$$10^9 + 6$$$,即使第二个答案的其余部分是 $$$0$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — 框的数量和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 框的位置。所有 $$$a_i$$$ 都是不同的,$$$a_{i - 1} < a_i$$$ 适用于所有有效的 $$$i$$$。
第三行包含 $$$n$$$ 整数 $$$w_1, w_2, \dots w_n$$$ ($$$1 \le w_i \le 10^9$$$) — 盒子的初始权重。
接下来的 $$$q$$$ 行描述查询,每行一个查询。
每个查询都在一行中描述,包含两个整数 $$$x$$$ 和 $$$y$$$。如果 $$$x < 0$$$,则此查询属于第一种类型,其中 $$$id = -x$$$, $$$nw = y$$$ ($$$1 \le id \le n$$$, $$$1 \le nw \le 10^9$$$)。如果 $$$x > 0$$$,则查询属于第二种类型,其中 $$$l = x$$$ 且 $$$r = y$$$ ($$$1 \le l_j \le r_j \le n$$$)。 $$$x$$$ 不能等于 $$$0$$$。
输出
对于第二种类型的每个查询,将答案打印在单独的行上。由于答案可能很大,请打印它除以 $$$1000\,000\,007 = 10^9 + 7$$$ 得到的余数。
示例
输入 #1
5 8 1 2 6 7 10 1 1 1 1 2 1 1 1 5 1 3 3 5 -3 5 -1 10 1 4 2 5
输出 #1
0 10 3 4 18 7
注意
让我们看一下示例的查询:
1. $$$1\ 1$$$ — 只有一个盒子,所以我们不需要移动任何东西。
2. $$$1\ 5$$$ — 我们可以移动框来分割 $$$[4, 8]$$$: $$$1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10$$$。
3. $$$1\ 3$$$ — 我们可以移动框来分段 $$$[1, 3]$$$。
4. $$$3\ 5$$$ — 我们可以移动框来分段$$$[7, 9]$$$。
5. $$$-3\ 5$$$ — $$$w_3$$$ 从 $$$1$$$ 更改为 $$$5$$$。
6. $$$-1\ 10$$$ — $$$w_1$$$ 从 $$$1$$$ 更改为 $$$10$$$。权重现在等于 $$$w = [10, 1, 5, 1, 2]$$$。
7. $$$1\ 4$$$ — 我们可以移动框来分段$$$[1, 4]$$$。
8. $$$2\ 5$$$ — 我们可以移动框来分段 $$$[5, 8]$$$。