著名的博学家尼古拉·哥白尼于 15 世纪在托伦出生并成长。近期，考古学家发现了他的笔记本，从中得知他偏爱使用 $2$ 的幂来记录较大的数字。特别是，当他计算两个 $2$ 的幂之和时：

$$2^a + 2^b$$

哥白尼会先计算出和，然后将此和向上取整到最接近的 $2$ 的幂。具体而言，他会将 $2^a + 2^b$ 的计算结果视为 $2^{\max(a, b)+1}$。对于更长的表达式，例如：

$$2^{b_1} + 2^{b_2} + \ldots + 2^{b_k}$$

他会首先通过添加括号，将其转化为一个运算顺序完全确定的表达式。例如，表达式 $2^5 + 2^4 + 2^4 + 2^4 + 2^5$ 可以被括号化为 $\left(\left(2^5 + 2^4\right) + \left(2^4 + \left(2^4 + 2^5\right)\right)\right)$。随后，他会依照前述规则计算这个括号表达式的值。值得注意的是，表达式的最终结果可能会因为括号添加方式的不同而有所差异。例如，以下是计算 $2^5 + 2^4 + 2^4 + 2^4 + 2^5$ 的两种可能方式及其结果：

$$ \begin{aligned} & \left(\left(\left(2^5 + 2^4\right) + 2^4\right) + \left(2^4 + 2^5\right)\right) = \left(\left(2^6 + 2^4\right) + 2^6\right) = \left(2^7 + 2^6\right) = 2^8 \\ & \left(\left(2^5 + \left(2^4 + 2^4\right)\right) + \left(2^4 + 2^5\right)\right) = \left(\left(2^5 + 2^5\right) + 2^6\right) = \left(2^6 + 2^6\right) = 2^7 \end{aligned} $$

哥白尼笔记本的首页仅包含一个形如 $2^{a_1} + 2^{a_2} + \ldots + 2^{a_n}$ 的表达式，该表达式被称为主表达式。文中的后续查询均涉及此主表达式的某个片段，其形式为 $2^{a_\ell} + 2^{a_{\ell+1}} + \ldots + 2^{a_r}$，其中 $1 \leq \ell \leq r \leq n$。

您尚不完全清楚这些片段的具体含义，但猜测对于每个片段，都需要计算按照上述规则求值时所能得到的最小可能结果。请注意，每个片段的求值过程均相互独立。

输入格式 (Input)

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 300000)$，分别表示主表达式的长度（项数）和查询的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^6)$，其中第 $i$ 个整数 $a_i$ 代表主表达式中第 $i$ 项 $2$ 的幂的指数。

接下来的 $q$ 行，每行描述一个查询。每行包含两个整数 $\ell$ 和 $r$ $(1 \leq \ell \leq r \leq n)$，表示主表达式的一个片段，该片段由主表达式中第 $\ell$ 个至第 $r$ 个 $2$ 的幂构成。

输出格式 (Output)

输出 $q$ 行。对于每个查询，输出其对应片段在所有可能的括号添加方式下，按照上述规则计算所能得到的最小结果。结果仅输出对应的 $2$ 的幂的指数。

Example

Input

8 4
2 4 2 5 4 4 4 5
4 8
1 4
2 5
1 7

Output

7
7
7
8

子任务与评分 (Scoring)