It's not Time for Games

There are $n$ people standing in a circle, where person $i$ and person $i+1$ are neighbors for every $1\le i<n$, and person $1$ and person $n$ are neighbors. Each person has a skill level represented by an integer $a_i$. Neighbors form a pair with a skill level of $a_i+a_{i+1}$. Unfortunately, they are all busy people, so the $i$-th person leaves the circle at time $i$. When person $i$ leaves, the indices do not shift. That is, if there were pairs $(i-1;i)$ and $(i;i+1)$, then the pair $(i-1;i+1)$ will not be formed after the departure of person $i$.

You are given $q$ queries, each containing one integer $t$. For each query, output an integer — the maximum skill level that can be formed with people who are still present at time $t$.

Input

The first line contains two integers $n$ ($2\le n\le 2\cdot 10^5$) and $q$ ($1\le q\le 2\cdot 10^5$) — the initial number of people in the circle and the number of queries.

The second line contains $n$ integers $a_i$ ($1\le a_i\le 10^6$) — the skill level values of the $i$-th person.

The following $q$ lines contain one integer $t$ ($0\le t<n-1$).

Output

Print $q$ lines, the $i$-th of which contains the answer to the $i$-th query.

Examples

Note

The explanation for the first example:

The first query has $t=1$. Let $X$ be those who left the circle, so we have $\{X,1,4\}$. There is one pair from the second and third elements — $1+4=5$.

The second query has $t=0$. Nobody has left the circle yet, so we have $\{2,1,4\}$. There are three pairs — the first with the second, the second with the third, and the third with the first. Their skill levels are $2+1=3$, $1+4=5$, and $4+2=6$, respectively.