Problem E: Stamp

Problem E: Stamp

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 451  Solved: 116
[Submit][Status][Web Board]


During the Hundred Regiments Battle in 2020, the SUSTech clubs prepared their own booths to introduce various club activities.  In order to encourage everyone to learn more about the clubs, the Association of Clubs launched an activity to collect stamps from all clubs.  Students who collect all the stamps can get generous prizes. The rules of the activity are as follows. There are a total of \(n\) clubs lined up on Lakeside Avenue in order.  Each student needs to go to the \(1\)-st, \(2\)-nd, ......, \(n\)-th club in order to collect stamps.  At the \(i\)-th club, \(s_i\) volunteers are allocated to give stamp to students who come to the club, and the number of students that the \(i\)-th club can handle per minute is \(a_i\). Since volunteers can also help neighboring clubs, the calculation formula of \(a_i\) is as follows
s_1 + s_2 & i=1 \\
s_{n-1} + s_n & i=n \\
s_{i-1} + s_{i} + s_{i+1} & 2\leq i \leq n-1  
Without considering the time moving between clubs, we can see that the throughput of students that the whole activity can support without heavy burden is \(b\), which is equal to the minimum of the \(a_i\), that is, \(b = min_{i=1}^{n}\{ a_i\}\).

Beyond everyone's expectations, at the beginning, the flow of students participating in the activity was very large, i.e., there are \(x\) newcomers per minute. For this reason, in addition to the volunteers \(s_1, s_2...s_n\), who have already allocated to clubs, the Association of Clubs urgently dispatched another \(y\) new volunteers. Each of these new volunteers can be assigned to a club to help give stamp. Once a volunteer is assigned to club, he/she cannot modify the allocated club. 

For each pair of  \(x\) and \(y\), please help the Association of Clubs to determine whether there is a possible solution for allocating \(y\) new volunteers so that the whole activity can support the throughput of \(x\), that is, to make \(b\geq x\) ?


The first line contains two integers \(n\) and \(q\) (\(3\leq n \leq 10000, 1\leq q \leq 1000 \)), where \(n\) indicates the number of clubs, and \(q\) indicates the number of queries.  Please notice that the queries are independent of each other. 

The second line contains \(n\) integers, \(s_1, s_2 ... s_n\) (\(0\leq s_i\leq 1000000000\)), indicating the numbers of volunteers already allocated to each club.

For the next \(q\) lines, each line contains two integers \(x\) and \(y\) (\(0\leq x,y \leq 1000000000\)), indicating a query of whether there exists a solution to allocate \(y\) new volunteers among clubs to make \(b\geq x\).


For each query, if there exist a solution, output "Yes" in a line, otherwise output "No" in a line.

Sample Input

3 5 
1 5 1 
7 0
8 0
19 19
10 8
1 7 

Sample Output