Siri is playing a game that features a very annoying mechanic: bookshelf scoring.

Simply put, let the player's character combat power be $a$, and the total damage dealt to the boss be $d$. Before the game starts, $a = a_0$ and $d = 0$.

There are $n$ turns. In each turn, you can use one skill, choosing between an attack skill or a support skill.

1. If you use an attack skill, you deal damage to the boss equal to your current combat power, i.e., $d = d + a$.
2. If you use a support skill, your combat power increases by $a_i$, i.e., $a = a + a_i$.

Suppose you use the attack skill $x$ times and the support skill $y$ times in total. The final score is: $$d \times (x \times k_1 + y \times k_2)$$

Here, $k_1$ and $k_2$ are given constants, but different bookshelves may correspond to different $k_1$ and $k_2$.

Siri will ask you $q$ questions. Each time, you are given new values for $k_1$ and $k_2$, and you need to find the maximum possible score.

Input

The first line contains two integers $n$ and $a_0$ ($1 \le n \le 10^5$, $0 \le a_0 \le 10^6$).

The second line contains $n$ integers, where the $i$-th integer is $a_i$ ($0 \le a_i \le 10^6$), representing that using the support skill in the $i$-th turn increases combat power by $a_i$.

The third line contains an integer $q$ ($1 \le q \le 10^5$), representing the number of queries.

Each of the next $q$ lines contains two integers $k_1$ and $k_2$ ($0 \le k_1, k_2 \le 10^9$), with the meanings as described above.

Output

Output $q$ lines, each containing one integer representing the answer to each query.

Examples

Input 1

10 3
17 7 16 16 17 10 20 13 7 18
5
37 20
8 14
31 32
1 37
23 15

Output 1

110230
42224
119700
83316
72270