#6546. 简单的数列题

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

题目描述

给定两个长度为 nn 的数列 aabb,有 mm 个操作,操作分为三类:

  • 11 ll rr ww :将数列 aa 中区间 [l,r][l,r] 内所有数加上 ww ;
  • 22 xx yy :交换 bxb_xbyb_y ;
  • 33 ll rr : 求 maxlir{aibi}\text{max}_{ l\le i\le r}\{a_i\cdot b_i\} .

输入格式

输入第一行包含两个整数 n,mn,m .
接下来一行包含 nn 个整数 aia_i .
接下来一行包含 nn 个整数 bib_i .
接下来 mm 行,每行包含一个操作,具体见描述。 保证 1lrn,1x,yn1\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

数据范围与提示

对于所有的数据, 1n,m105, 1ai107, 1bi105, 1wi1001\le n,m\le 10^5,\ 1\le a_i\le 10^7,\ 1\le b_i\le 10^5,\ 1\le w_i\le 100 .

Subtask 1 (20 pts) :1n,m21031\le n,m\le 2\cdot 10^3

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