After trying hard for many years, Byteasar has finally received a pilot license. To celebrate the fact, he intends to buy himself an airplane and fly around the planet 3-SATurn (as you may have guessed, this is the planet on which Byteotia is located). Specifically, Byteasar plans to fly along the equator. Unfortunately, the equator is rather long, necessitating refuels. The flight range (on full tank) of each aircraft is known. There is a number of airports along the equator, and a plane can be refueled when it lands on one. Since buying an airplane is a big decision, Byteasar asks your help. He is about to present you with a list of different plane models he is considering. Naturally, these differ in their flight range. For each plane model, he would like to know the minimum number of landings (including the final one) he would have to make in order to complete the journey. Note that for each airplane model, the journey may start at a different airport.

Input

The first line of the standard input contains two integers n and s, separated by a single space, denoting the number of airports along the equator and the number of airplane models Byteasar is considering.

The second line contains n positive integers l_1, l_2, \ldots, l_n, separated by single spaces, specifying the distances between successive airports along the equator. The number l_i is the distance between the i-th and (i+1)-st (or n-th and first if i=n) in kilometers.

The third line contains s integers d_1, d_2, \ldots, d_s, separated by single spaces. The number d_i is the i-th airplane model's flight range in kilometers, i.e., the maximum distance it can fly before landing and refueling.

Output

Your program should print s lines to the standard output: the i-th of these should contain a single integer, namely, the minimum lumber of flight segments (and thus also landings) necessary to fly the i-th airplane around the planet 3-SATurn along the equator, starting at an airport of choice, or the word NIE (Polish for no) if it is impossible to complete the journey with this airplane.

Constraints

• 2 \le n \le 10^6
• 1 \le s \le 100
• 1 \le l_i \le 10^9
• l_1 + l_2 + \ldots + l_n \le 10^9
• 1 \le d_i \le l_1 + l_2 + \ldots + l_n

Example

For the input data:

6 4
2 2 1 3 3 1
3 2 4 11

the correct result is:

4
NIE
3
2

Explanation: The thick solid line shows the optimal journey of the plane with flight range 4, whereas the dashed line the optimal journey of the plane with flight range 3.

Task authors: Jan Kanty Milczek i Jakub Pachocki.