下克上の天邪鬼

题号：NC222906
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

更好的阅读体验：

链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。

$\textsf{题目背景}$

天邪鬼是一种性格扭曲的妖怪。而作为幻想乡的不稳定分子的鬼人正邪，一天到晚脑子里总想着和其他人相反的事情。她天天想着把幻想乡整个翻转过来。

作为看热闹不嫌事大的天邪鬼，正邪非常喜欢看别的妖怪「下克上」。也就是更为弱小（实力上或者是地位上）的妖怪，战胜比他更强的妖怪。正邪拥有让任何事物都翻转过来程度的能力，因此下克上往往都是她主导的。

正邪选出了幻想乡的若干个妖精，希望在其中制造出「下克上」。一次「下克上」的精彩程度，就是两只妖精的能力之和。但是正邪的能力有限，如果两只妖怪实力相差悬殊，那就不大可能达成下克上了。又因为幻想乡的妖精实在是太多了，正邪计算不出怎么策划这场「下克上」。

于是正邪找到了你，希望你根据她的询问，分别找出一对妖精，使得「下克上」的程度最精彩。

$\textsf{题目描述}$

正邪选中了幻想乡的 $\mathit n$ 个妖精作为她的考虑对象，并按照次序排成了一列。妖精从左往右编号为 $1,2,\cdots n$ 。每个妖精的实力可以用一个正整数 $a_i$ 表示。

正邪一共会发起 $\mathit m$ 次询问，每次给出两个区间 $[l_1,r_1],[l_2,r_2]$ 。你需要选择一对妖精 $\mathrm (i,j)$ ，满足妖精 $\mathit i$ 在区间 $[l_1,r_1]$ 内，并且妖精 j 在区间 $[l_2,r_2]$ 内。正邪会试图让妖精 $\mathit j$ 击败妖精 $\mathit i$ 。为了防止实力悬殊，它们还满足：

$\left\lfloor \dfrac{a_i}{2} \right \rfloor \le a_j < a_i$

正邪希望你找到 $a_i + a_j$ 的最大值。特别地，如果不存在合法数对，你只要输出 $\mathrm 0$ 就行了。

输入描述:

第一行两个整数，。含义如题面所示。

第二行  个整数  ，表示序列  。

接下来  行，每行四个整数， ，表示一组询问。

输出描述:

共  行，每行输出一个整数，表示最大的  ，或者不存在任何合法数对时输出的  。

示例1

输入

复制

6 3
8 6 2 3 5 6
2 5 1 3
1 1 3 6
3 5 1 2

输出

复制

7
14
0

说明

对于询问  ，有两对妖精   和 满足下克上的条件。但因为 ，因此精彩度最大为   。
对于询问  ，有两对妖精  和  满足下克上的条件。但因为  ，因此精彩度最大为  。
对于询问  ，不存在任何符合条件的妖精对。因此直接输出  。

示例2

输入

复制

10 10
106 42 110 126 7 52 68 70 73 118 
10 10 5 5
9 10 4 4
1 5 4 6
4 9 9 9
4 5 1 3
1 6 1 8
3 5 5 9
4 4 1 3
5 5 4 8
2 4 6 7

输出

复制

说明

这里本应该有个绝妙的说明，但是这里空白太小了写不下。

备注:

对于  的数据：，，。
性质 A：。
    
性质 B：除  外，所有数据在合法范围内等概率随机生成。

对于 所有数据， 。