该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师是个炒股糕手，他每天都会买入或卖出股票（可以操作非整数份的股票），他想知道在初始资金为$2^k$的情况下， 每次交易后的最大资金的指数是多少

Format

Input

第一行两个数字$n,m(1 \leq n \leq m \leq 10^5)$，表示交易日股票金额和操作的日期

第二行n个整数$a_i(1 \leq 10^9)$，表示股票的的价格$2^{a_i}$

第三行一个整数$k(1 \leq k \leq 10^5)$，表示每次交易的初始资金$2^k$

接下来m行，每行一个$s,t(1 \leq s \leq t \leq n)$，表示交易的起止日期

Output

输出m行，每行一个整数，表示在这个时间段内的最大资金的指数

Samples

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

5
6

Limitation

1s, 1024KiB for each test case.