Little A aspires to be a master stock trader. After a long period of study, he has mastered a wealth of theoretical knowledge and has carefully selected a stock, deciding to engage in practical trading over the next $n$ trading days.

The "Stock God" has come to Little A and helped him predict the stock price for the next $n$ trading days. Since the Stock God is skilled in mathematics, all prices are given in the form of natural logarithms. That is to say, on the $i$-th day ($1 \le i \le n$), you will obtain an integer $a_i$, representing that the stock price on that day is $e^{a_i}$ yuan. It should be noted that in this problem, Little A can buy non-integer amounts of stock.

Because his initial capital is limited, Little A has decided to publicly borrow money from others, which he calls "chicken debt." For the convenience of management and profit calculation, he stipulates that every loan is a fixed amount of $e^k$ yuan.

During these $n$ days, there are $m$ lenders willing to provide "chicken debt" to Little A.

For the $i$-th lender, they will provide $e^k$ yuan to Little A before the market opens on day $s_i$, and require settlement after the market closes on day $t_i$. During this period, Little A is free to use these funds to perform any number of buy and sell operations.

Your task is: for each "chicken debt," calculate the natural logarithm $w$ of the final total assets (principal plus profit) that Little A can obtain under optimal operations, and output this integer. In other words, if Little A eventually turns $e^k$ yuan into $e^w$ yuan through his operations, you should output the integer $w$.

Input

The first line contains two integers $n$ ($1 \le n \le 10^5$) and $m$ ($1 \le m \le 10^5$), representing the number of trading days and the number of chicken debts, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where the stock price on the $i$-th day is $e^{a_i}$.

The third line contains one integer $k$ ($1 \le k \le 10^9$), representing the loan amount $e^k$ provided by each chicken debt.

The next $m$ lines each contain two integers $s_i$ and $t_i$ ($1 \le s_i \le t_i \le n$), representing the start day and the settlement day for the $i$-th chicken debt.

Output

Output $m$ lines, each containing one integer $w_i$, representing the natural logarithm of the total principal and profit for the $i$-th chicken debt, which is $e^{w_i}$ yuan.

Examples

Input 1

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

Output 1

5
6

Note

In the example, there are 6 trading days and 2 chicken debts. The stock prices for each day are $e^3, e^2, e^4, e^5, e^3, e^6$. The principal for each chicken debt is $e^2$.

For the 1st chicken debt: borrowed on day 2, returned on day 4. For the 2nd chicken debt: borrowed on day 3, returned on day 6.

For the 1st chicken debt: the stock prices for the three days are $[e^2, e^4, e^5]$. The optimal strategy is to buy on day 2 and sell on day 4. The final assets are $e^2 \div e^2 \times e^5 = e^5$. The output is 5.

For the 2nd chicken debt: the stock prices for the four days are $[e^4, e^5, e^3, e^6]$. The optimal strategy is to buy on day 3, sell on day 4, buy again on day 5, and sell on day 6. The final assets are $e^2 \div e^4 \times e^5 \div e^3 \times e^6 = e^6$. The output is 6.