题目描述

给定两个长度为 $n$ 的数列 $a$ 和 $b$，有 $m$ 个操作，操作分为三类：

• $1~l~r~w$ ：将数列 $a$ 中区间 $[l,r]$ 内所有数加上 $w$ ;
• $2~x~y$ ：交换 $b_x$ 和 $b_y$ ;
• $3~l~r$ ：求 $\displaystyle \max_{i=l}^r \{a_i\cdot b_i\}$ .

输入格式

输入第一行包含两个整数 $n,m$ .
接下来一行包含 $n$ 个整数 $a_i$ .
接下来一行包含 $n$ 个整数 $b_i$ .
接下来 $m$ 行，每行包含一个操作，具体见描述。 保证 $1\le l\le r\le n, 1\le x,y \le n$ .

输出格式

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

样例

5 3
1 2 4 5 9
5 2 3 2 1
1 2 3 3
2 3 4
3 2 5

15

数据范围与提示

对于所有的数据， $1\le n,m\le 10^5,\ 0\le a_i\le 10^7,\ 0\le b_i\le 10^5,\ 0\le w_i\le 100$ .

Subtask 1 (20 pts) ：$1\le n,m\le 2\cdot 10^3$；

Subtask 2 (80 pts) ：无特殊限制。