#6546. 简单的数列题

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: x_faraway_x

题目描述

给定两个长度为 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) :无特殊限制。