Garden

Hyeonwook's garden in front of his house has $N$ trees ($1 \le N \le 3 \cdot 10^5$). Each tree height is an integer from $1$ to $10^9$, and the trees are planted so that their heights are non-decreasing. If $H_i$ is the height of the $i$-th tree, then $H_i \le H_{i+1}$ always holds.

Each day, a tree grows by $1$ if it meets both conditions:

• It is strictly shorter than the tree directly to its right ($H_i < H_{i+1}$).
• Among such trees, the height difference with the tree directly to its right is the smallest.

If several trees qualify, only the leftmost one grows. In other words, at most one tree grows per day. For example, suppose the heights are $1, 3, 4, 5, 5, 7$. The trees with the smallest difference to their right neighbor are the 2nd and 3rd trees, both with difference $1$. Of these, the leftmost is the 2nd tree, so its height grows by $1$.

Starting today, Hyeonwook wants to know the difference between the tallest and the shortest tree after $K$ days ($1 \le K \le 10^{12}$). Given $Q$ queries ($1 \le Q \le 3 \cdot 10^5$), write a program that answers each query.

The first line contains $N$ and $Q$ ($1 \le N, Q \le 3 \cdot 10^5$).

The second line contains $N$ tree heights $H_i$ separated by spaces ($1 \le H_i \le 10^9$). The input always satisfies $H_i \le H_{i+1}$.

Each of the next $Q$ lines contains one query. Every $K$ is an integer with $1 \le K \le 10^{12}$.

For each query, print on its own line the difference between the heights of the tallest and the shortest tree after $K$ days.