#4717. 改装

内存限制:512 MiB 时间限制:100 Sec

题目描述

(reequip.pas/c/cpp/in/out)
【题目背景】
小Q最近喜欢上了一款游戏,名为《舰队connection》,在游戏中,小Q指挥强大的舰队南征北战,从而成为了一名
dalao。在游戏中,不仅船只能力很重要,搭配合适的装备更是如虎添翼。小Q潜心研究配装三十年,终于——把装
备凑齐了。
【题意描述】
小Q有n艘船,m件装备。为了简单起见,我们假定每艘船都只能携带一件装备,且可以携带任何一件装备。每艘船
和每件装备都有自己的能力值。船携带装备时,能力值为两者相乘。另外,小q还有可能对船或装备进行改修(强化
)。改修成功会让能力提升,失败则会让能力降低。由于最佳配置已经用了无数次了毫无挑战性,因此,小Q并不打
算直接使用最佳配置,而是使用相对弱一些的第k佳配置。具体来说,每次选择船只时,由于关卡限制,小Q需要在
编号为L到R的船只中选择一艘,并在编号为a和b之间的装备选择一架,组成出击用的船只。于是,小Q总共有(R-L+
1)*(b-a+1)种选择,小Q希望知道,所有这些选择中,第k大的能力值是多少。例如:
船只:5 3 7
装备:4 2 1 8 16
对于L=1,R=3,a=1,b=5,k=10的询问,将所有可能的能力值排序,分别为7*16=102,5*16=80,7*8=56,3*16=48,5*
8=40,7*4=28,3*8=24,5*4=20,7*2=14,3*4=12,5*2=10,7*1=7,3*2=6,5*1=5,3*1=3,其中第10大的是12。
对于L=2,R=3,a=2,b=4,k=5的询问,将所有可能的能力值排序,分别为7*8=56,3*8=24,7*2=16,7*1=7,3*2=6,3
*1=3,其中第5大的是6。假定小Q改修了第二艘船使其能力值成功增加至4,并改修了第5件装备但由于失败使得它
的能力值减小为9。现在,对于L=1,R=2,A=4,B=5,K=3的询问,所有可能的能力值分别为5*9=45,5*8=40,4*9=36,
4*8=32,其中第3大的是36。现在,你要编写一个程序回答这些问题。提示:由于游戏的特殊性,装备比船多得不
知道到哪里去了,另外,作为一个人类,小Q才不会在一秒钟之内问几百万个问题让你回答,他只会问几百个,而
且给你好几秒钟的时间回答。

输入格式

第一行两个数n,m,空格分隔,表示小Q的船的数量和装备的数量。
第二行n个数,空格分隔,表示小Q的船的能力值(按编号)。
第三行m个数,空格分隔,表示小Q的装备的能力值(按编号)。
第四行一个数q,表示小q的操作数量。
接下来q行,每行描述一个操作,操作要么为一个改修事件,要么为一个询问。
对于改修事件,该行4个数0,type,pos,val,type为0或1,0表示把pos号船改修成val的能力值
1表示把pos号装备改修成val的能力值。
对于询问操作,该行6个数1,L,R,a,b,k,空格分隔,表示一个询问。
n<=250,m<=100000,q<=100000,其中询问操作不会超过200。
对于100%的数据,1<=L<=R<=n,1<=a<=b<=m,1<=k<=(R-L+1)*(b-a+1)
任何时候船能力值为不超过2000的正整数,装备能力值为不超过1000000的正整数。

输出格式

对于每个询问操作,输出一行,包含一个数,表示询问的答案。

样例

样例输入


			
3 5
5 3 7
4 2 1 8 16
5
1 1 3 1 5 10
1 2 3 2 4 5
0 0 2 4
0 1 5 9
1 1 2 4 5 3

样例输出


			
12
6
36

数据范围与提示