There are people standing in a circle, where person and person i+1 are neighbors for every 1\leq i<n, and person and person 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 -th person leaves the circle at time . When person 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 .
You are given queries, each containing one integer . For each query, output an integer — the maximum skill level that can be formed with people who are still present at time .
The first line contains two integers (2\leq n\leq 2\cdot 10^5) and (1\leq q\leq 2\cdot 10^5) — the initial number of people in the circle and the number of queries.
The second line contains integers a_i (1\leq a_i\leq 10^6) — the skill level values of the -th person.
The following lines contain one integer (0\leq t<n-1).
Print lines, the -th of which contains the answer to the -th query.
Example 1
Example 2
Example 3
The explanation for the first example:
The first query has t=1. Let 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.