题目描述

小 F 猛然醒来，才觉是黄粱一梦。现实上他还在赛场上，他打开题面阅读起来：

给定两个长度为 $n$ 序列 $a,b$ 。

对于一段区间 $l,r$ 的权值为 $\sum_{i=l}^ra_ib_i$ 。

你需要进行 $m$ 次操作：

1. $a$ 全局加。
2. 查询一个区间，求它所有子区间（可以为空，此时权值为 $0$ ）权值的最大值。

此刻你就是小 F，请你完成此题代码。

输入格式

第一行两个整数 $n,m$ 。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$ 。

第三行 $n$ 个整数，第 $i$ 个整数为 $b_i$ 。

注意 $b$ 的取值为 $1$ 或 $-1$ 。

之后 $m$ 行，每行一个操作：

• $1\ x$ ： $a$ 序列所有数加上 $x$ 。
• $2\ l\ r$ ：查询区间 $[l,r]$ 。

输出格式

对于每个询问，输出一个数表示答案。

输入输出样例 #1

输入 #1

7 7
1 2 3 4 5 6 7
-1 1 -1 1 -1 1 -1
2 3 5
1 -4
2 1 3
2 5 7
2 7 7
1 5
2 1 7

输出 #1

4
3
2
0
7

对于所有测试点，

• $1\le n,m\le 5\times 10^5$ ， $-10^6\le a_i,x\le 10^6$ ， $b_i=\pm 1$ 。

子任务 1（10分）： $1\le n,m\le 10^3$ 。

子任务 2（15分）： $1\le n\le 10^4$ ， $1\le m\le 5\times 10^5$ 。

子任务 3（35分）： $1\le n,m\le 10^5$ 。

子任务 4（40分）： $1\le n,m\le 5\times 10^5$ 。