Around the world

Time limit5sMemory limit24 MB

Summary

For each plane range, find the fewest refueling landings to circle all airports from the best start, or report impossible.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, Two pointers
Solved: No attempts yet

Problem

After years of trying, Byteasar finally earned a pilot license. To celebrate it he decided to buy an airplane and fly once around 3-SATurn, the planet he lives on. The route follows the equator. The equator is long, so the plane has to refuel on the way. There are $n$ airports along the equator, and the plane fills its tank every time it lands at one. Each plane model has its own flight range, the greatest distance it covers on a full tank without landing.

For each of the $s$ models he is considering, Byteasar wants the smallest number of landings needed to fly around the equator. The final landing counts too. He may pick a different starting airport for each model.

Input

The first line contains the number of airports $n$ and the number of plane models $s$ , separated by a single space ( $2 \le n \le 10^6$ , $1 \le s \le 100$ ).

The second line contains the distances between neighbouring airports $l_1, l_2, \dots, l_n$ , separated by single spaces. $l_i$ is the distance between airport $i$ and airport $i+1$ , and $l_n$ is the distance between airport $n$ and airport $1$ . Every $l_i$ is a positive integer, and $l_1 + l_2 + \dots + l_n \le 10^9$ .

The third line contains the flight ranges $d_1, d_2, \dots, d_s$ , separated by single spaces ( $1 \le d_i \le l_1 + l_2 + \dots + l_n$ ). $d_i$ is the greatest distance the $i$ -th model flies before it has to land and refuel. All distances are given in kilometres.

Output

Print $s$ lines. Line $i$ contains the minimum number of flight legs needed to fly the $i$ -th model once around 3-SATurn along the equator. The number of flight legs equals the number of landings, and the journey may start at any airport. If the $i$ -th model cannot complete the journey, print NIE, the Polish word for "no".

Hint

The picture shows the airports of the first example. The thick solid line is an optimal route for the plane with flight range 4, and the dotted line is an optimal route for the plane with flight range 3.

Examples4

Example 1
Input
```
6 4
2 2 1 3 3 1
3 2 4 11
```
Expected output
```
4
NIE
3
2
```
Example 2
Input
```
3 1
3 4 3
6
```
Expected output
```
2
```
Example 3
Input
```
2 3
1 1
1 2 2
```
Expected output
```
2
1
1
```
Example 4
Input
```
7 4
1 1 1 1 1 1 1
1 2 3 7
```
Expected output
```
7
4
3
1
```