题目描述

小 A 立志成为一名炒股高手。经过长时间的学习，他自信已掌握了丰富的理论知识，并精心挑选出了一支股票，决定在接下来的 $n$ 个交易日内进行实战操作。

股票之神向小 A 投来了注视，他帮你预知了接下来 $n$ 个交易日中这只股票的股价。由于股票之神擅长数学，所有价格均以自然对数的形式给出。也就是说，在第 $i$ 天（$1 \leq i \leq n$），会得到一个正整数 $a_i$，表示当天该股票的价格为 $e^{a_i}$ 元。需要注意的是，在本题中，小 A 可以购买非整数份的股票。

由于手头资金有限，小 A 决定公开向他人借款，称为"鸡债"。为了方便管理和收益核算，他规定每位出借人均提供固定的 $e^k$ 元借款。

在这 $n$ 天内，共有 $m$ 位出借人愿意向小 A 提供鸡债。

对于第 $i$ 位出借人，他会在第 $s_i$ 天开盘前向小 A 提供 $e^k$ 元，在第 $t_i$ 天收盘后要求结算收益。在这段时间内，小 A 可自由使用这笔资金进行任意次数的买入与卖出操作。

你的任务是：对于每一笔鸡债，计算小 A 在最优操作下所能获得的最终总资产（即本金加收益）的自然对数值 $k$，并输出该整数。 换句话说，若小 A 最终通过操作将手中 $e^k$ 元变为 $e^w$ 元，则你应输出该整数 $w$。

输入格式

第一行包含两个正整数 $n$（$1 \leq n \leq 10^5$） 和 $m$（$1 \leq m \leq 10^5$），分别表示交易日的数量以及鸡债的数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^4$），其中第 $i$ 天的股票价格为$e^{a_i}$。

第三行包含一个正整数 $k$（$1 \leq k \leq 10^9$），表示每份鸡债提供的借款金额为$e^k$。

接下来 $m$ 行，每行包含两个整数 $s_i$ 和 $t_i$（$1 \leq s_i \leq t_i \leq n$），表示第 $i$ 份鸡债的借款开始日和收益结算日。

输出格式

输出共 $m$ 行，每行一个正整数 $w_i$，表示第 $i$ 份鸡债的本金加收益总额为 $e^{w_i}$ 元。

6 2
3 2 4 5 3 6
2
2 4
3 6

5
6

提示

在样例中，一共有 $6$ 个交易日，$2$ 份鸡债。

每天的股价为 $e^3, e^2, e^4, e^5, e^3, e^6$ 。

鸡债的本金均为 $e^2$ 。

第 $1$ 份鸡债：第 $2$ 天借出，在第 $4$ 天归还。

第 $2$ 份鸡债：第 $3$ 天借出，在第 $6$ 天归还。

对于第 $1$ 份鸡债：三天的股价为 $[e^2, e^4, e^5]$ ，最优方案为第 $2$ 天买入，第 $4$ 天卖出。最终资产为 $e^2 \div e^2 \times e^5 = e^5$ 。

输出答案为 $5$ 。

对于第 $2$ 份鸡债：四天的股价为 $[e^4, e^5, e^3, e^6]$ ，最优方案为第 $3$ 天买入，第 $4$ 天卖出，第 $5$ 天再买入，第 $6$ 天再卖出。最终资产为 $e^2 \div e^4 \times e^5 \div e^3 \times e ^6 = e^6$ 。

输出答案为 $6$ 。