Xsquare has decided to win next Programming Marathon and started his preparation for the same. Xsquare's coach advised him to revise algorithmic concepts and to try twik of some standard problem. Xsquare's coach knows that it is the only best strategy to perform well at any kind of marathon.

Xsquare started following his coach's instructions and getting better and better as the day passes. One fine day, Xsquare has taken up the following standard problem.

Given a one dimensional array A of size N that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum.

Xsquare modified the above problem to make it bit more interesting .

Given a one dimensional array A of size N that may contain both positive and negative integers and an integer K, find the sum of contiguous subarray of numbers which has the largest sum such that no element in the selected array is greater than K. To make this problem a bit harder, Xsquare decided to add Q queries to this problem each containing one integer i.e K.

Input

First line of input contains two integers N and Q denoting the size of array A and number of queries respectively. Second line of each test case contains N space separated integers denoting array A. Next Q lines of each test cases contains a single integer denoting K.

Output

For each query, print the required answer.

Note

If there is no element X in the array such that X ≤ K for some K, print "No Solution" without quotes.

Constraints

• 1 ≤ N,Q ≤ 5*10⁵
• -10⁹ ≤ A_i,K ≤ 10⁹
• All test data is strictly according to constraints

Subtasks

• Subtask1 : 1 ≤ N,Q ≤ 5*10³ , 0 ≤ A_i ≤ 10⁹ (20 pts)
• Subtask2 : 1 ≤ N,Q ≤ 5*10³ , -10⁹ ≤ A_i ≤ 10⁹ (20 pts)
• Subtask3 : 1 ≤ N,Q ≤ 5*10⁵ , -10⁹ ≤ A_i ≤ 10⁹ (60 pts)